memory-efficient doubly linked list

Introduction

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, address of the next node, and address of the previous node.

The node of a Doubly linked list:

It occupies an extra space for the address of the previous node compared to a simple linked list node as the doubly linked list node contains both the addresses of the previous and the next node. This article will learn about the memory-efficient doubly linked list or XOR linked list, which has only one address or pointer per node using the property of bitwise XOR.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Memory-efficient doubly linked list

A node of an ordinary doubly linked list contains two addresses: the address of the previous node and the address of the next node, but a node of the memory-efficient doubly linked list contains only one address, the bitwise XOR of the previous and next address. It can be used as two addresses using an important property of bitwise XOR.

An interesting property of bitwise XOR :

If X ^ Y = Z then Y ^ Z = X and X ^ Z = Y

From the above property, if we have X and Y, we can compute Z. If we have Y and Z, we can compute X, and if we have X and Z, we can compute the value of Y.

We use this property in our doubly linked list for storing the address. Instead of keeping the next and previous addresses, we store the XOR of next and previous addresses.

Address of the Next Node = Address of Previous Node ^ Address of the current Node.
Address of the Previous Node = Address of Next Node ^ Address of the current Node.

So if we have a linked list like this:

Nodes of the memory-efficient linked list after using the property of XOR will look like this;

Node n1: n1->next = NULL(0) XOR address of (n2)
Node n2: n2->next = address of (n1) XOR address of (n3)
Node n3: n3->next = address of (n2) XOR address of (n4)
Node n4: n4->next = address of (n3) XOR NULL(0)

We can traverse the list in both directions in the linked list without any extra previous pointer.

Inserting a node

We first create a new node.
Make the next of the new nodes the NULL XOR address(head), i.e. address of the previous node XOR address of the next node.
Now, we update the addresses of the next nodes after the head node to the address of the previous node XOR address of the next node.
Finally, we make the new node the head of the list.

Printing the list

We create a previous node pointing to NULL and a current node pointing to the head of the list.
Now, keep repeating the below processes till the end of the list.
Print the current->data.
Now, we store the address of the next node as the address of the previous node XOR address of the next node(current->next).
We update the previous node to the current node and the current node to the next node of the list.

Read about Bitwise Operators in C here.

Code in C++

#include <bits/stdc++.h>
#include <cinttypes>
using namespace std;

class Node
{
public:
    int data;
    Node* next;
};

Node* XOR(Node* n1, Node* n2)
{
    return reinterpret_cast<Node*>(
              reinterpret_cast<uintptr_t>(n1)
              ^ reinterpret_cast<uintptr_t>(n2));
}

void insert_node(Node** head, int new_node_data)
{
    Node* newNode = new Node();
 
    newNode->data = new_node_data;

    newNode -> next = *head;

    if (*head != NULL) {

        (*head)-> next = XOR(newNode, (*head) -> next);
    }

    *head = newNode;
}


void print_linked_list(Node* head)
{
    Node* current = head;

    Node* previous = NULL;

    Node* next;

    while (current != NULL) {

        cout << current -> data << " ";

        next = XOR(previous, current -> next);

        previous = current;

        current = next;
    }
}

int main()
{
    Node* head = NULL;
    insert_node(&head, 5);
    insert_node(&head, 10);
    insert_node(&head, 15);
    insert_node(&head, 20);
    insert_node(&head, 25);

    print_linked_list(head);

    return (0);
}

Output

25 20 15 10 5

Complexity Analysis

Time complexity: The time complexity of the insert_node function is O(1), as we haven’t traversed the list.

The time complexity of the print_linked_list function: O(n), where n is the number of nodes in the list, traversing the whole list.

Space complexity: The space complexity of the above solution is O(1) as we need constant extra space.

Check out this problem - Reverse Nodes In K Group

Frequently Asked Questions

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.

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.

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.

Conclusion

So, this article discussed the doubly linked list and how we can use the property of bitwise XOR to optimize the space of a Doubly Linked List by removing an extra previous pointer with examples and implementing a memory-efficient doubly linked list.

You can learn more about the linked lists and also practice similar problems on Coding Ninjas Studio.

Memory-efficient Doubly Linked List