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

Question

So recently, I had read an article that showed me how to implement a doubly-linked list with just a single pointer field, i.e, like a single linked list. Something to do with storing the XOR prev and the next address in a single field. I don't get how this helps us traverse front and back? Can someone explain this to me? I had read the article over here. Can anyone explain this to me? In a little more detail? And how XOR has anything to do with these addresses.

Answer 1

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

Answer 2

XOR has this funny property: if you are given A and C = A^B, you can compute A^C = A^(A^B) = (A^A)^B = B.

In the case of linked lists, if you are given the forward pointer or the backward pointer and the XOR of the two, you can find the other pointer with a single XOR. When you are iterating the list you already have one of them, so all you need is the XOR to find the other; therefore there's no need to store both.