How would you implement serialization of a doubly linked list?

There are several approaches:

1. Simple serialization (for lists without cyclic links):

   • Iterate through the list, writing node data: value, then pointer to the next node.
   • Handle nullptr for the last node's next pointer.
   • Need to store node pointers to reconstruct back pointers during deserialization.

   // Example node structure
   struct Node {
       int value;
       Node* prev;
       Node* next;
   };
   
   // Simple serialization
   void serialize(Node* head, std::ostream& os) {
       std::unordered_map<Node*, size_t> node_to_id;
       size_t id_counter = 0;
   
       Node* current = head;
       while (current) {
           node_to_id[current] = id_counter++;
           current = current->next;
       }
   
       os << id_counter << std::endl; // Number of nodes
       current = head;
       while (current) {
           os << current->value << " ";
           os << (current->prev ? node_to_id[current->prev] : -1) << " "; // ID of previous
           os << (current->next ? node_to_id[current->next] : -1) << std::endl; // ID of next
           current = current->next;
       }
   }
   

   // Simple deserialization
   Node* deserialize(std::istream& is) {
       size_t num_nodes;
       is >> num_nodes;
   
       std::vector<Node*> nodes(num_nodes);
       std::vector<std::pair<int, std::pair<int, int>>> node_data(num_nodes);
   
       for (size_t i = 0; i < num_nodes; ++i) {
           nodes[i] = new Node{};
           is >> node_data[i].first >> node_data[i].second.first >> node_data[i].second.second;
           nodes[i]->value = node_data[i].first;
       }
   
       for (size_t i = 0; i < num_nodes; ++i) {
           int prev_id = node_data[i].second.first;
           int next_id = node_data[i].second.second;
   
           nodes[i]->prev = (prev_id != -1) ? nodes[prev_id] : nullptr;
           nodes[i]->next = (next_id != -1) ? nodes[next_id] : nullptr;
       }
   
       return num_nodes > 0 ? nodes[0] : nullptr;
   }
   

2. Serialization with handling cyclic links (e.g., using std::unordered_map for pointer mapping):

   • Assign a unique ID to each node during serialization.
   • Write the node data (value) and the IDs of the prev and next nodes.
   • During deserialization, create an array of nodes and map IDs back to node pointers.

3. Using serialization libraries:

   • Boost.Serialization
   • Cereal
   • Protocol Buffers (structured data)

   These libraries provide more reliable and versatile mechanisms, including handling complex structures and versioning.

The choice of method depends on requirements: simplicity, performance, handling cyclic links, technologies used. For a doubly linked list without cyclic links, a simple approach with node IDs is effective.