XOR linked list

XOR Linked Lists, also known as Memory Efficient Doubly Linked Lists, offer a memory-efficient implementation compared to traditional Doubly Linked Lists. While a regular Doubly Linked List requires two location fields to store the addresses of the previous and next nodes, an XOR Linked List optimizes memory usage by using just one space for the address field in each node. This memory efficiency is achieved by utilizing bitwise XOR operations to store and retrieve addresses in a compact manner. As a result, XOR Linked Lists provide an alternative approach to saving space while maintaining the functionality of a Doubly Linked List.

          

In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.

In a double-linked list:

Node A: prev = NULL, next = add(B) // previous is NULL and next is address of B

Node B: prev = add(A), next = add(C) // previous is the address of A and next is the address of C

Node C: prev = add(B), next = add(D) // previous is the address of B and next is the address of D

Node D: prev = add(C), next = NULL // previous is address of C and next is NULL

In XOR List:

Node A:

0 XOR add(B) // bitwise XOR of zero and address of B

Node B:

add(A) XOR add(C) // bitwise XOR of address of A and address of C

Node C:

 add(B) XOR add(D) // bitwise XOR of address of B and address of D

Node D:

add(C) XOR 0 // bitwise XOR of the address of C and 0

XOR List traversal:

XOR Linked List can be traversed in both forward and reverse direction. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node’s address. For example, when we are at node C, we must have the address of B. The reason is simple: the address stored at C is “add(B) XOR add(D)”. If we do xor of “add(B) XOR add(D)” with add(B), we get the result as “add(B) XOR add(D) XOR add(B)” which is “add(D) XOR 0” which is “add(D)”. So we have the address of the next node. Similarly, we can traverse the list in a backward direction.