Optimizing Doubly LinkedList in terms of space.

I recently came to know that doubly linked list can be optimized in terms of space which is very fascinating. Keep reading till the end to know exactly how it is done.

Note: — The calculation made in this article is based on 32 bit architecture.

A conventional Doubly linked list node looks like the following :

struct Node {
    struct Node* prev;
    int val;
    struct Node* next;
};

In this as we need to keep track of the previous and next node to traverse the doubly linked list back and forth. This takes more space than the singly linked list node because of the overhead of storing the previous pointer too. It is normal for the small dataset if you want store millions or billions of data it is going to increased a lot.

For example let’s say in singly linked list we store data and the next pointer which will take approximately 8 bytes ( this keeps changing depending on the architecture 32-bit or 64 bit and language/ compiler.)

int -> 4 bytes
next -> 4 bytes
total -> 8 bytes ~ 64 bits

Now if we want to store the in doubly linked list then we know that it contains data , pointer to the previous and next node. So , this is going to take approximately 12 bytes so if we calculate for millions of pointer then it for singly linked list node it is 8MB ~ 7.63 MB and for doubly linked list it 12MB ~ 11.44MB. This is a big difference.

To overcome this overhead a journal(Sinha) has presented an alternative approach for this which reduces the space significantly.

So, the new proposed alternative for doubly linked list ADT looks like the following:

struct Node {
    int val;
    struct Node* npx;
};

This is also called XOR Linked List. In this method we don’t keep track of previous and next pointer , instead of that we store the pointer difference. What? How? pointer difference amazing right. So, in this approach we don’t do simple arithmetic difference we do XOR and store that difference in one pointer in the above structure we’re doing that in the pointer npx.

In npx we store the diffrence between previous node and next node.

npx = previous node ⊕ next node

But just storing the pointer difference how we can do froward and backward before diving deep in to that first understand properties of XOR.

X ⊕ X = 0

X ⊕ 0 = X

X ⊕ Y = Y ⊕ X

(X ⊕ Y) ⊕ Z = X ⊕ (Y ⊕ Z)

refer to this if you like to know more about XOR Link

Above diagram shows how linked list are stored let’s calculate the next pointer of each node:

A -> npx = NULL ⊕ B ( previous node ⊕ next node)
B -> npx = A ⊕ C
C -> npx = B ⊕ D
D -> npx = C ⊕ NULL

XOR Function

Node XOR(struct Node *a, struct Node *b){
  return (Node *)((uintptr_t)a ^ (uintptr_t)b);
}

Traversal of XOR Linked List

At first it may seems impossible to traverse just by storing single pointer instead of next and prev. But if you know the properties of XOR this is straight forward.

Traversing in forward direction

Let’s say you are at each node: —

next = prev ⊕ curr.npx
A = NULL⊕ B = B
B = A ⊕ A ⊕ C=  C
C = B ⊕ B ⊕ D = D
D = C ⊕ C ⊕ NULL= NULL  

Node *curr = head;
Node *prev = NULL;
Node *next;
while (curr!=NULL){
  printf("%d", curr.data);
  next = XOR(prev, curr.next);
  prev = curr;
  curr = next;
}

Traversing in backward direction

D = C ⊕ NULL ⊕ NULL = D ⊕ NULL = C
C = B ⊕ D ⊕ D = B
B = A ⊕ C ⊕ C = A
A = NULL ⊕ B ⊕ B = NULL

Node * curr = tail;
Node * next = NULL;
Node * prev;

while (curr!=NULL){
  printf("%d", curr.data);
  prev = XOR(next,curr.npx);
  next = curr;
  curr = prev;
}

Insert Operation in XOR LinkedList

i) Insert at head.

void insertAtHead(int data){
    struct Node* newNode = malloc(sizeof(struct(Node)));
    newNode.data = data;
    newNode.npx = XOR(NULL, head);
    if (head != NULL){
        sturct Node *next = XOR(NULL, head);
        head->npx = XOR(newNode, next);
    }
    head = newNode;
}

ii) Insert at tail.

void insertAtTail(int data){
  struct Node* newNode = malloc(sizeof(struct(Node)));
  newNode.data = data;

  if (head == NULL){
    newNode.npx = XOR(NULL, head);
    return;
  }

  struct Node* curr= tail;
  newNode.next = XOR(curr, NULL);
  curr.npx = XOR(newNode, NULL);
  tail = newNode;
}

Delete Operation in XOR LinkedList

i) Delete Head

int deleteHead() {
    if (head == NULL) {
        printf("List is empty\n");
        return -1;
    }

    struct Node* curr = head;
    struct Node* next = XOR(NULL, curr->npx);

    if (next != NULL) {
        struct Node* nextNext = XOR(curr, next->npx);
        next->npx = XOR(NULL, nextNext);
    } else {
        tail = NULL;
    }

    head = next;
    int data = curr->data;
    free(curr);

    return data;
}

ii ) Delete tail

int deleteTail() {
    if (head == NULL) {
        printf("List is empty\n");
        return -1;
    }

    struct Node* curr = tail;
    struct Node* prev = XOR(curr->npx, NULL);

    if (prev != NULL) {
        struct Node* prevPrev = XOR(prev->npx, curr);
        prev->npx = XOR(prevPrev, NULL);
        tail = prev;
    } else {
        head = tail = NULL;
    }

    int deletedValue = curr->data;
    free(curr);
    return deletedValue;
}

Conclusion:-

The XOR Linked List provides an efficient way to traverse a linked list while optimizing space, something traditional doubly linked lists fail to achieve. Instead of storing separate prev and next pointers, it stores the XOR of both pointers, enabling traversal in both forward and backward directions. However, due to its complexity and reliance on low-level pointer manipulation, this approach is not suitable for all programming languages.

Reference:-

1. Narasimha Karumanchi, Data Structures and Algorithms Made Easy, CareerMonk Publications & Technology [Link]