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 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.
