Memory efficient doubly linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Useful Observation

As we know, a doubly-linked list requires two fields for previous and next pointers other than the data field. It ends up taking extra space for the previous pointer. In a memory-efficient doubly linked list, we only need one field with each node other than the data fields.

The memory-efficient linked list is called a XOR list. We use the concept of XOR in this implementation.

An important XOR property

If A XOR B = C, then A XOR C=B, as well as B XOR C=A

Approach

The approach is going to use the bitwise XOR operation. Using it, we can create a XOR list that requires only one field for addressing. Let us see with an example.

If the list is

Here, the address of each node will contain the XOR of the previous node address and the next node address.

  • Node A : A -> next = NULL XOR address of (B)
  • Node B : B -> next = address of (A) XOR address of (C)
  • Node C : C -> next = address of (B) XOR address of (D)
  • Node D : D -> next = address of (C) XOR NULL

Using this, we can traverse the list both in the forward and backward direction without using an extra previous pointer.

We are going to understand how the Insert at the beginning and PrintList functions work.

Insert at beginning

The new node will always be added before the head node. Now, as the previous pointer of the new node will be NULL, so the next of the new node will be NULL XOR address(head). By completing this step, the new node will point to the head.

Now, we have to update the next of the head node. The next pointer of the head node will be the address(new node) XOR address(next node). In the end, we will make the new node our new head.

Algorithm

  • Create the new node.
  • The next of the new node will be NULL XOR address(head)
  • We need to update the next of the head node. So, the next of the head node will be address(new node) XOR address(next node)
  • Finally, make the new node the head.

PrintList

In the PrintList function, we will start with a node previous, which will point to NULL, and a node current which will point to the head. Now, we will print current - > data. For the traversal, we will now need the address of the next node. We can get that by calculating the address(previous node) XOR address(next node). After getting the next node address, we will update our previous to current, and current to the next node address. This process will go on till we reach the end of the list.

Algorithm

  • Create a previous node and a current node. Previous will point to NULL and current will point to the head.
  • Print current - > data.
  • Store the address of the next node as address(previous) XOR address(current - > next).
  • Update the previous to current, and the current to the next node.
  • Keep repeating the above process till the end of the list traversal

Dry Run

Code Implementation


#include 
#include 
using namespace std;

class Node
{
    public:
    int data;
    Node* next; 
};
 
// Function to return the xor of two addresses
Node* XOR (Node *a, Node *b)
{
    return reinterpret_cast(
      reinterpret_cast(a) ^
      reinterpret_cast(b));
}

void insert(Node **head_ref, int data)
{
    Node *new_node = new Node();
    new_node->data = data;
 
    // The new node will point to NULL XOR address(head)
    new_node->next = XOR(NULL,*head_ref);

    if (*head_ref != NULL)
    {
        // head will now point to address(new node) XOR address(head - > next)
        (*head_ref)->next = XOR(new_node, (*head_ref)->next);
    }
 
    // Update the nead
    *head_ref = new_node;
}

void printList (Node *head)
{
    Node *curr = head;
    Node *prev = NULL;
    Node *next;
 
    cout << "Following are the nodes of Linked List: \n";
 
    while (curr != NULL)
    {
        // Print the current node
        cout<data<<" ";
        
        // get address of the next node by address(prev) XOR address(curr)
        next = XOR (prev, curr->next);
 
        // update prev and curr 
        prev = curr;
        curr = next;
    }
}

int main ()
{
    Node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
    printList (head);
    return (0);
}

Output
40 30 20 10

Time Complexity

Insert at beginning - O(1), as no traversal is performed.

PrintList - O(N) since we are traversing the list once.

So, in this article, we have tried to explain the implementation of an efficient doubly linked list. This implementation saves us from the hassle of storing the previous pointer every time. The efficiency of this implementation is what makes this question an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Implementing Iterator pattern of a single linked list
Next post Find the largest node in a Doubly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *