implementing doubly linked list using single pointer

The problem with single linked list is that, we cant back traverse, only forward traversal is allowed because current node contains the address of the next node.  To traverse back wards we need another pointer to store the previous address and that concept is called doubly linked list.

We can implement back traversal by storing previous and next node address in the single pointer. For this we need to use the concept of XOR operation.

XOR Operations: let’s see the beauty of XOR operation.

If you perform XOR operation on any two input values, you will get some result. And if you perform again XOR operation with result and any one of the two input values, you will get other input value. We are going to use this logic to store the prev and next node values. See the example below.

  a ^ b = c

  c ^ b = a

  c ^ a = b

So while creating the linked list, we need to perform XOR operation to get the next node value.  The key point in this process is, we need to maintain the prev node value to make the XOR operation.

Creating and storing the next pointer value:  The value which we are going to store in the next pointer is the XOR operation of prev and new nodes. So next pointer of the node should not points to the next node, instead of that, its having some value which is a combination of prev and next nodes as shown in the picture. For complete code click here.

If the list contains single node, as prev pointer value is initially NULL, so there wont be any problem.

Forward traversing: to move the pointer from current node to next node, the sample code is given below. For complete C implementation click here.

current = current->next ^ prev

Before Operation:

After Operation:

After executing above statement, the current node moves to the next node as shown below.

Backward traversal:  Assume that below is the scenario and we are at current node and we know the address of temp, so to get the prev node of the current node, the sample code is below. For complete C code click here.

while(temp!=h)
 {
   printf("%d->",temp->info);
   prev = prev->next ^ temp;
   temp = tempPrev;
   tempPrev = prev;
 }

Before operation:

After operation:

In this way, we  need to do the operations to get the prev node and next node addresses. And there are more statements to maintain prev and next node pointers. Click here for the complete working C Implementation.

Note: XOR operation can be performed only on integer or char data type. And XOR is not allowed on structure as it is user defined data type. To perform the XOR operation, we need to type cast it to long int.