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

Сериализация двусвязного списка подразумевает сохранение данных и структуры связей между узлами в линейный формат (например, файл или поток). Основная сложность — корректно сохранить и восстановить двунаправленные указатели, избежав зацикливания.

Стратегия: Вместо сохранения указателей (адресов памяти) мы сохраняем индексы узлов в последовательности обхода. При десериализации мы восстанавливаем узлы и связываем их по этим индексам.

Пример реализации сериализации и десериализации:

#include <vector>
#include <unordered_map>
#include <fstream>
#include <iostream>

struct ListNode {
    int data;
    ListNode* prev;
    ListNode* next;
    ListNode(int d) : data(d), prev(nullptr), next(nullptr) {}
};

// Сериализация в вектор целых чисел
void serialize(ListNode* head, std::vector<int>& out) {
    std::unordered_map<ListNode*, int> nodeToId;
    ListNode* current = head;
    int id = 0;

    // Первый проход: сохраняем данные и присваиваем узлам ID
    while (current) {
        nodeToId[current] = id++;
        out.push_back(current->data); // Сохраняем данные
        current = current->next;
    }

    // Второй проход: сохраняем связи в виде ID соседей
    current = head;
    while (current) {
        int prevId = (current->prev) ? nodeToId[current->prev] : -1;
        int nextId = (current->next) ? nodeToId[current->next] : -1;
        out.push_back(prevId);
        out.push_back(nextId);
        current = current->next;
    }
}

// Десериализация из вектора целых чисел
ListNode* deserialize(const std::vector<int>& in) {
    if (in.empty()) return nullptr;

    // Количество узлов = общий размер / 3 (data, prevId, nextId на узел)
    size_t nodeCount = in.size() / 3;
    std::vector<ListNode*> nodes(nodeCount, nullptr);

    // Первый проход: создаем узлы с данными
    for (size_t i = 0; i < nodeCount; ++i) {
        nodes[i] = new ListNode(in[i]);
    }

    // Второй проход: восстанавливаем связи по сохраненным ID
    for (size_t i = 0; i < nodeCount; ++i) {
        int prevId = in[nodeCount + i*2];     // Индекс prev
        int nextId = in[nodeCount + i*2 + 1]; // Индекс next

        if (prevId != -1) nodes[i]->prev = nodes[prevId];
        if (nextId != -1) nodes[i]->next = nodes[nextId];
    }

    return nodes[0]; // Возвращаем голову
}

// Вспомогательная функция для записи/чтения в/из файла
void serializeToFile(ListNode* head, const std::string& filename) {
    std::vector<int> serializedData;
    serialize(head, serializedData);

    std::ofstream file(filename, std::ios::binary);
    if (file) {
        size_t size = serializedData.size();
        file.write(reinterpret_cast<const char*>(&size), sizeof(size));
        file.write(reinterpret_cast<const char*>(serializedData.data()), size * sizeof(int));
    }
}

ListNode* deserializeFromFile(const std::string& filename) {
    std::ifstream file(filename, std::ios::binary);
    if (!file) return nullptr;

    size_t size = 0;
    file.read(reinterpret_cast<char*>(&size), sizeof(size));
    std::vector<int> serializedData(size);
    file.read(reinterpret_cast<char*>(serializedData.data()), size * sizeof(int));

    return deserialize(serializedData);
}

Альтернативные подходы:

• Сериализация в текстовый формат (JSON, XML): Использовать библиотеки вроде nlohmann/json. Удобно для отладки и взаимодействия.
• Бинарная сериализация с сохранением смещений: Сохранять не индексы, а смещения в файле, что эффективнее для прямого доступа.
• Использование boost::serialization: Готовая библиотека, поддерживающая сложные графы объектов и версионность.