XOR and double linked list

So this is a post about yet more intellectual masturbation yay! HOW TO STORE THE PREV AND NEXT POINTERS OF A NODE IN A DOUBLE LINKTED LIST IN A SINGLE ADDRESS.

Intro

In a double linked list there is the concept of a pointer to the previous and the next nodes. What we want to do here is store the addresses to the previous and next nodes in a single address using an XOR old trick.  To show you how this works we only need these two pieces of node which I got from a neat little explanation here. This code is meant for counting the nodes of the double linked list but in generally shows how to traverse the list encoding and decoding the previous and next addresses.

typedef struct node {
   struct node *diff;

   int data;
} node;

Here *diff refers to the XOR of the addresses od previous and next pointer.

unsigned long countNodes()
{
   unsigned long nodes = 0;
   node *curr, *prev, *temp;

   prev = NULL;
   curr = nodeHead;
   while (curr)
     {
	nodes ++;
	temp = curr;
	curr = XOR(prev, temp->diff);
	prev = temp;
     }

  return nodes;
}


Example

Lets say you have a linked list with nodes A, B, C.

• And Node A is at address 100000
• And diff has address XOR (prev,next)= XOR (000000, B) = XOR (000000, 101110)  = 101110. 
   

• Then we go into the loop inside countNodes() and in the first iteration this is what the state looks like :

              temp = A = 100000

              curr = XOR ( prev,  diff )  = XOR ( 000000,  101110) = 101110

              prev = temp = 100000

 

So now curr, which is the equivalent of the next node,  is pointing at B’s address ( 101110) and we have decoded this address using 2 main things:

1. The diff variable in node A that contains the XOR of prev and next of A.
2. A varibale prev that keeps track of that the previous node’s address was. 

Keep in mind that although we are using 2 variables (and thus addresses) for figuring out what next is, we really only store one as part of each node since from these 2 vars one is reused every iterations, and thats the prev var.

cool aint it? : )