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.

Answer 3

As far as I understand it relies on the properties of the XOR operator, say:

A XOR A = 0

When using doubly-linked list you have to save both "next" and "prev" adresses in your structure. The author says that to save space you can just store :

next XOR prev

And browse your list by doing:

next = current XOR prev

next = (next XOR prev) XOR prev

next = next XOR (prev XOR prev)

But I don't really get the point since in this example you still have to know "prev" to do your computation...

Answer 4

Its this way:

You are at some node. You need to go to the next one. But you have a single variable which needs to store the value of two pointers. How is this possible?

We make use of the fact that when we traverse the list we know the node address of the previously visited node. But How?

So, the question boils down to this:

We need to store two values in a single variable. At any point, we know any one of them. We need to find the other one. Is it possible?

The answer is YES.

v = a^b;
then v^b = a and v^a = b

Now, apply this concept to the DLL.

Store the XOR of previous and next node's addresses in the current node

When you wish to traverse to the next node, XOR the previous node's address with the value stored in the current node. You can traverse to the next one. Similarly one can traverse in the backward direction.

Answer 5

Nice explanation by nitish. This explanation makes it very easy to understand this concept.

I will make it simpler then it would be more useful. Suppose you have 3 nodes namely A,B and C. Address stored in A is 1(i.e. 01 in binary), in B is 2(i.e. 10 in binary), in C is 3(i.e. 11 in binary). It is clearer in this manner.

A    B    C
01   10   11  --->>this 01,10,11 are addresses. 

Now, XOR property shows that when bits are the same we get 0, otherwise 1. So, when your current node is B (i.e. at address 10), and you want to move forward. Meaning that what you have to do is A XOR B or 01 XOR 10, i.e.

     01
xor  10
    =11 i.e by doing xor of 01 and 10 it will make you reach at 11 address that is C. 

similarly when you do 10 xor 11 answer is 01 i.e. A.