Doubly Linked list using one Pointer

Problem : The question is to implement the doubly linked list. But you should maintain only one pointer per node.

Solution :
Remember how to swap the two numbers without using any third variable. XOR funda.

Same thing is applied here.
Suppose list is as below
A - B -C

What we will do is, we will main the address difference of the previous and next node in the current node in the link field.

e.g in case of B

node->link = A XOR C.

so when you want to traverse from left to right, you need left pointer .

and can find Address of c as A XOR node->link == A XOR A XOR C =c

similarly you can go back to the right to left, only thing is you need address of the right node here to traverse.


some additional info
1) You need to maintain two extra node here. start and end. start -> left = NULL
and similarly end -> right = NULL

2) you need additional node info here to travel to next node. e.g need address of A if you want to go from B to C

reference link is at

http://www.linuxjournal.com/article/6828?page=0,0