XOR Linked List: Overview and Implementation in C/C++

In this post, we will discuss about XOR linked list which is used to reduce memory requirements of a doubly linked lists using bitwise XOR operator.


 

We know that each node of a doubly linked list requires two pointer fields to store the addresses of its previous and next node. On the other hand, each node of XOR linked list requires only single pointer field which doesn’t store the actual memory addresses but stores the bitwise XOR of address for its previous and next node.

To illustrate, let’s consider the following doubly linked list.

 
Doubly Linked List

 
Here the link field for equivalent XOR linked list stores the below values:

link(A) = NULL ^ addr(B)        // bitwise XOR of NULL with address of node B
link(B) = addr(A) ^ addr(C)     // bitwise XOR between address of node A and C
link(C) = addr(B) ^ addr(D)     // bitwise XOR between address of node B and D
link(D) = addr(C) ^ NULL        // bitwise XOR of address of node A with NULL

 

How this helps?

We know that XOR has below properties:

X^X = 0
X^0 = X
X^Y = Y^X

 
We can easily traverse the XOR linked list in either direction using above properties:

 

1. Traversing the list from left to right:
Since we’re traversing the list for left to right, say we store the address of previous node in some variable. Now since previous node information is available, we can get address of the next node by XORing the value in the link field with address of the previous node.

For example, suppose we’re at node C, we can get address of node D as shown below.

  addr(B) ^ link(C)
= addr(B) ^ (addr(B) ^ addr(D))
= 0 ^ addr(D)
= addr(D)

 
The XOR operation cancels addr(B) appearing twice in the equation and all we are left with is the addr(D). Similarly, to get address of first node A in the list, we can XOR the value in the link field with NULL.

  NULL ^ link(A)
= NULL ^ (NULL ^ addr(B))
= 0 ^ addr(B)
= addr(B)

 

2. Traversing the list from right to left:
Following the similar logic, to get address of last node D in the list, XOR the D’s link field value with NULL

  NULL ^ link(D)
= NULL ^ (addr(C) ^ NULL)
= 0 ^ addr(C)
= addr(C)

 
For any middle node, say node C, we can get address of previous node B as

  addr(D) ^ link(C)
= addr(D) ^ (addr(B) ^ addr(D))
= 0 ^ addr(B)
= addr(B)

 
Consider below program which constructs a XOR linked list and traverses it in forward direction using properties of bitwise XOR operator. To traverse the complete list, we maintain three pointers prev, curr, and next to store the current node address, the previous node address and next node address respectively. Each iteration of the loop moves these pointers one position forward or backwards depending upon which direction we’re traversing the list.

C

Download   Run Code

Output:

1 -> 2 -> 3 -> 4 -> 5 -> NULL

C++

Download   Run Code

Output:

1 -> 2 -> 3 -> 4 -> 5 -> nullptr

 

Drawbacks of XOR linked list:

 
A XOR linked list is simlar to a doubly linked list but not completely equivalent to a doubly linked list. There are several disadvantages of a XOR linked list over doubly linked list which are discussed below:

  1. A doubly linked list is easy to code and maintain but the code is little complex for a XOR linked list.
     
  2. XOR linked list is not supported by several languages such as Java where conversion between pointers and integers is undefined.
     
  3. If a pointer to an existing middle node in a XOR linked list is provided, we can’t delete that node from the list or insert a new node before or after it. On the other hand, this can be done easily with a doubly linked list.

 
References: XOR linked list – Wikipedia

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us^ Please spread the word and help us grow. Happy coding 🙂
 

Leave a Reply

avatar
  Subscribe  
Notify of