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.

Brade

There are several answers below that explain this well, so I'll skip that and simply comment on one thing to note. Platforms exist where this is not supported (in fact, some exist that will eval if (ptr) as false if the pointer value is either indeterminate or did not come specifically from a "proper" allocation function or &-operator). It was often done as a way to save precious bytes, usually at the ASM level. Rarely today (usually embedded) is such a thing needed now, and does little make code difficult to read and maintain. Nice trick, good lore, now forget about it =P. – Redstone

Ah yes. I realize that this is an old, unused method. Thing is, I had read this somewhere as an interview question. Was curious on how it worked. Ofcourse today, we have no need for cramming on such small space. Nevertheless, the idea is innovative and it was purely for my understanding. – Brade

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

Sy

Very well explained Pandrei. I have understood the concept now. However, the code I will take a little time to get. I'll have to trace it I guess. Seems a little confusing at the moment. But thank you very much! This explanation was very good. Thanks all. Everyone's information helped me a little here and there to understand the concept as a whole. – Brade

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.

Minimum

Hmm. I understand. But could you elaborate on this by giving a real example(with dummy address values) for us to understand this concept more clearly please? – Brade

OK. Suppose you have a node with backward pointer 1 and forward pointer 3. The node stores 1^3 = 2. Now, if you iterate the list forwards, you get from node with address 1 to this node. 1^2 = 3 so the next node is 3. Likewise, if you iterate backwards, you get from node with address 3 to this node. Now 3^2 = 1, so the next node has address 1. – Minimum

Interesting. But it seems a little weird. Let me get a few things cleared. You say "Suppose you have a node with backward pointer and forward pointer". Doesn't that make it a doubly linked list itself? And having a backward pointer 1 and a forward pointer 3, doesn't it make the current node the one with address 2? – Brade

You are implementing a doubly linked list, so nodes will have both pointers, or at least some way to obtain them. With this trick the pointers are not stored directly, but there's still a way to compute them. The current node could have any address, it's not important, what's important is that it stores 2 which is xor of the two pointers. – Minimum

Answer 3

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.

Momentarily

Answer 4

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...

Herb

The idea is that if you are traversing the list forwards, you know prev and want next. If you are traversing backwards you know next and want prev. Either way, you know one of the XOR inputs and need to know the other. – Raddled

Ok but in the case you are provided with just a pointer on an element you are stuck. So it is an optimization with limited interest (i.e. it can be useful in very specific cases only) – Herb

In the 30+ years I spent as a professional programmer, I never encountered a situation in which the memory gain from using it was enough to justify the cost in flexibility and code clarity. I view it as a theoretical curiosity, not a useful pattern. – Raddled

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.

Cyanosis