Storing a doubly-linked list using just a single pointer field

As the article points out this technique is useful only if you have a pointer at either the head or tail of the list; if you only have a pointer in the middle of the list there's nowhere to to.

About the technique: consider the following linked list:

|0|A|0x01|<->|0x01|B|0x02|<->|0x02|C|0|

The list contains 3 nodes with values A,B,C and prev/next pointer containing hex values(addresses) of the prev/next element in the list. Value 0 is null

Istead of storing 2 pointers, we can use only one, as explained in the article:

|A|0x01|<->|B|0x03|<->|C|0x03| 

we'll call the new field link = prev XOR next. so with that in mind:

    A.link = 0^0x01 = 0x01
    B.link = 0x01^0x02 = 0x03
    C.link = 0x03^0x0 = 0x03. 

Assuming you have a pointer to the head of the list (which you know has the prev pointer set to null) here's how you iterate through the list:

 p=head; 
 prev = 0;
 while(p.link!=prev)
 {
   next = p.link^prev
   prev=p
   p=next 
 }

You go backwards in the list using the same logic