Как сериализовать двунаправленный список?

Сериализация двунаправленного списка

Двунаправленный список (doubly linked list) содержит указатели как на следующий, так и на предыдущий элемент. При сериализации основная сложность — это циклические ссылки и необходимость восстановить обе связи при десериализации.

Подходы к сериализации

1. Сериализация только значений (рекомендуемый подход)

Сохраняем только данные элементов в порядке обхода, восстанавливаем связи при десериализации:

// Сериализация
void serializeDoublyList(const DoublyLinkedList& list, std::ofstream& file) {
    int count = list.size();
    file.write(reinterpret_cast<char*>(&count), sizeof(count));
    
    for (const auto& node : list) {
        int value = node->data;
        file.write(reinterpret_cast<char*>(&value), sizeof(value));
    }
}

// Десериализация
void deserializeDoublyList(DoublyLinkedList& list, std::ifstream& file) {
    int count;
    file.read(reinterpret_cast<char*>(&count), sizeof(count));
    
    for (int i = 0; i < count; ++i) {
        int value;
        file.read(reinterpret_cast<char*>(&value), sizeof(value));
        list.insertBack(value);
    }
}

2. JSON сериализация (для обмена данными)

Идеален для JSON API и человеко-читаемого формата:

#include <nlohmann/json.hpp>
using json = nlohmann::json;

json serializeDoublyListJSON(const DoublyLinkedList& list) {
    json j = json::array();
    
    for (const auto& node : list) {
        j.push_back({
            {"value", node->data},
            {"index", std::distance(list.begin(), 
                      std::find(list.begin(), list.end(), node))}
        });
    }
    return j;
}

DoublyLinkedList deserializeDoublyListJSON(const json& j) {
    DoublyLinkedList list;
    
    for (const auto& item : j) {
        list.insertBack(item["value"].get<int>());
    }
    return list;
}

3. Сохранение структуры с индексами

Если нужна максимальная верность (например, для позиций):

struct SerializedNode {
    int data;
    int nextIndex;   // -1 if nullptr
    int prevIndex;   // -1 if nullptr
};

void serializeStructured(const DoublyLinkedList& list, std::ofstream& file) {
    std::vector<SerializedNode> nodes;
    int index = 0;
    auto* current = list.getHead();
    
    std::unordered_map<Node*, int> nodeToIndex;
    
    // Первый проход: собираем индексы
    while (current) {
        nodeToIndex[current] = index++;
        current = current->next;
    }
    
    // Второй проход: сохраняем данные
    current = list.getHead();
    while (current) {
        SerializedNode sn;
        sn.data = current->data;
        sn.nextIndex = current->next ? nodeToIndex[current->next] : -1;
        sn.prevIndex = current->prev ? nodeToIndex[current->prev] : -1;
        nodes.push_back(sn);
        current = current->next;
    }
    
    int count = nodes.size();
    file.write(reinterpret_cast<char*>(&count), sizeof(count));
    for (const auto& node : nodes) {
        file.write(reinterpret_cast<char*>(&node), sizeof(node));
    }
}

Ключевые моменты

• Избегай сохранения указателей напрямую — адреса памяти не сохраняются между сеансами
• Обход только в одном направлении — достаточно для восстановления всей структуры
• Проверь целостность — при десериализации убедись, что связи восстановлены корректно
• Производительность — сохранение только значений быстрее и компактнее

Лучшая практика

Для большинства случаев используй первый подход (сохранение только значений) — это просто, надёжно и эффективно. Сложные варианты нужны только при специфических требованиях (восстановление позиций, кэширование структуры и т.д.).