Задача - написать функции сериализации и десериализация двусвязного списка (без использования сторонних библиотек и стандартных средств сериализации), представленного в таком виде:
class ListNode
{
public ListNode Previous;
public ListNode Next;
public ListNode Random;
public string Data;
}
class ListRandom
{
public ListNode Head;
public ListNode Tail;
public int Count;
}
где public ListNode Random - ссылка на случайный элемент внутри списка.
Мое изначальное решение выглядит так:
class ListRandom
{
public ListNode Head;
public ListNode Tail;
public int Count;
private ListNode GetNodeAt(int index)
{
int counter = 0;
for (ListNode currentNode = Head; currentNode.Next != null; currentNode = currentNode.Next)
{ if (counter == index)
return currentNode;
counter++;
}
return new ListNode();
}
public void Serialize(Stream s)
{
Dictionary<ListNode, int> dictionary = new Dictionary<ListNode, int>();
int id = 0;
for (ListNode currentNode = Head; currentNode != null; currentNode = currentNode.Next)
{
dictionary.Add(currentNode, id);
id++;
}
using (BinaryWriter writer = new BinaryWriter(s))
{
for (ListNode currentNode = Head; currentNode != null; currentNode = currentNode.Next)
{
writer.Write(currentNode.Data);
writer.Write(dictionary[currentNode.Random]);
}
}
Console.WriteLine("List serialized");
}
public void Deserialize(Stream s)
{
Dictionary<int, Tuple<String,int>> dictionary = new Dictionary<int, Tuple<String, int>>();
int counter = 0;
using (BinaryReader reader = new BinaryReader(s))
{
while (reader.PeekChar() != -1)
{
String data = reader.ReadString();
int randomId = reader.ReadInt32();
dictionary.Add(counter, new Tuple<String, int>( data, randomId));
counter++;
}
Console.WriteLine("File readed");
}
Count = counter;
Head = new ListNode();
ListNode current = Head;
for (int i = 0; i < Count; i++)
{
current.Data = dictionary.ElementAt(i).Value.Item1;
current.Next = new ListNode();
if (i != this.Count - 1)
{
current.Next.Previous = current;
current = current.Next;
}
else
{
Tail = current;
}
}
counter = 0;
for (ListNode currentNode = Head; currentNode.Next != null; currentNode = currentNode.Next)
{
currentNode.Random = GetNodeAt(dictionary.ElementAt(counter).Value.Item2);
counter++;
}
Console.WriteLine("List deserialized");
}
Алгоритм следующий - при сериализации, сначала проходим по списку, и создаем словарь из элемента списка и числа, которым описываем порядковый номер этого элемента в списке, при обходе с головы. Далее, записываем в файл попарно данные из узла, и номер элемента списка, на который ссылался ListNode Random. При десериализации - создаем словарь из числа (порядковый номер будущего элемента списка), и пары String (данные элемента) и int (номер элемента списка на который будет ссылаться ListNode Random). Далее создаем сам список, заполняя его данными, но не присваивая никаких значений ListNode Random, так как он может ссылаться на элемент, которого на данный момент ещё нет. И в последнем цикле присваиваем каждому ListNode Random нужную ссылку элемент списка.
Как можно улучшить данный код/алгоритм?