Memory efficient doubly linked list

Last Updated on November 28, 2022 by Prepbytes

Doubly linked lists data structure are a type of linked lists that can be traversed in both directions, i.e. forward (head to the last node) and backward direction (last node to head). The node of the doubly linked list has three fields: data, the address of the next node, and the address of the previous node. Let us understand the approach for a better understanding of a memory efficient doubly linked list.

Useful Observation of memory efficient doubly linked list

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 of memory efficient doubly linked list

The approach is going to use the bitwise XOR operation. Using it, we can create an 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 of memory efficient doubly linked list

• 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 of memory efficient doubly linked list

• 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 of memory efficient doubly linked list

Code Implementation of memory efficient doubly linked list

#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 of memory efficient doubly linked list

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

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

Conclusion

So, in this article, we have tried to explain the implementation of an efficient memory 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 is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQs related to memory efficient doubly linked list

1. What is a linked list?
A linked list is a dynamic data structure in which each element (called a node) consists of two components: data and a reference (or pointer) to the next node. A linked list is a collection of nodes, each of which is linked to the next node by a pointer.

2. How is the linked list implemented in memory?
LinkedList, unlike Arrays, is not stored in a contiguous memory location. Each element in the list is distributed across memory and is linked by pointers in the Node. As a result, separate memory space is allocated large enough to store both the key and the pointer to the next element whenever a new element is added.

3. What is the use of a doubly linked list?
It is used in navigation systems where both forward and backward navigation is required. The browser uses a back and forward button to implement backward and forward navigation of visited web pages. It is also used to represent a traditional card game deck.