Memory Efficient doubly linked list

Implement doubly linked list which has only one pointer (may not be directly of apointer data type) per node. An ordinary doubly linked list will require 2 pointers per node, one pointing to the previous node and another pointing to the next node in the list as shown below.

Doubly linked list looks like below

Where blue arrow is indicating the next pointer and red arrow is indicating the previous pointer. Note that the Previous pointer of first node and the next pointer of last nodes are NULL. This implementation of linked list has 2 pointer per node. Your question is, Implement doubly linked list using only one pointer per node. (Note that you should be able to navigate in both forward and backward direction using the single pointer.)

Solution:

We have only one pointer and that pointer will act as both the forward and the backward pointer. This is where XOR comes into play:

The basic operations on XOR (as also used in this post), has some interesting facts like,

if
 A ^ B = C
Then
 C ^ A = B and C ^ B = A

i.e If we have C & A, then we can compute B and if we have C & B, then we can compute A.

We will use this property of XOR operator.

For each Node we will not store either the previous or next pointer, but we will store the XOR of previous & next pointer.

So if we have the below linked list

and if a1, a2, a3, a4 are the addresses of each node respectively, then the XOR list will store

If you are traversing in the forward direction then, you will get the address of next node as below:

Current Node	Next Node	Value of Pointer =(Add of Prev Node) ^ (Link of Current Node)	Address of Next Node
list	a1	Directly	-
a1	a2	NULL ^ Link of a2	NULL^NULL^a2 = a2
a2	a3	a1 ^ Link of a2	a1^a1^a3 = a3
a3	a4	a2 ^ Link of a3	a2^a2^a4 = a4
a4	NULL	a3 ^ Link of a4	a3^a3^NULL = NULL

Hence at each point, you have to store the address of previous node to compute the address of next node.

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

Similarly to compute the address of previous node you need to know the address of next node.

Address of Previous Node = Address of Next Node ^ pointer in the current Node

Advantage:

1. We save a lot of memory space. For each node we are saving one pointer, if there are n nodes then our memory consumption is reduced by O(n).
2. If we want to reverse the doubly linked list (pre will become next & vice-versa) it is O(n) operation (pointers need to be changed for each node). In the above implementation, since we are storing XOR of prev & next it will remain unchanged, and only the head pointer need to be changed to point to last node.

Disadvantage:

1. Traversing requires more operations. It is not just going to the next pointer but, performing XOR.

References:

http://www.linuxjournal.com/article/6828?page=0,0 The C++ implementation of this is available here…