XOR Linked List

Write a memory efficient Doubly Linked List with the following structure

typedef struct ListNode
{     int data;
       struct ListNode *ptrdiff;
};

where ptrdiff pointer contains the difference between the pointer to the next node and the pointer to previous node.Pointer difference is calculated using XOR operation

ptrdiff= pointer to previous node  XOR  pointer to next node

XOR List Representation:
Let us call the address variable in XOR representation npx (XOR of next and previous)
Node A:
npx = 0 XOR add(B) // bitwise XOR of zero and address of B
Node B:
npx = add(A) XOR add(C) // bitwise XOR of address of A and address of C
Node C:
npx = add(B) XOR add(D) // bitwise XOR of address of B and address of D
Node D:
npx = add(C) XOR 0 // bitwise XOR of address of C and 0

Traversal of XOR Linked List:
We can traverse the XOR list in both forward and reverse direction. While traversing the list we need to remember the address of the previously accessed node in order to calculate the next node’s address. For example when we are at node C, we must have address of B. XOR of add(B) and npx of C gives us the add(D). The reason is simple: npx(C) is “add(B) XOR add(D)”. If we do xor of npx(C) with add(B), we get the result as “add(B) XOR add(D) XOR add(B)” which is “add(D) XOR 0″ which is “add(D)”. So we have the address of next node. Similarly we can traverse the list in backward direction.

Useful Links:
http://en.wikipedia.org/wiki/XOR_linked_list
http://www.linuxjournal.com/article/6828?page=0,0
http://www.geeksforgeeks.org/archives/12367