Save a doubly linked list using just one index field

Question

Recently, I read an article that shows how to implement a doubly linked list with only one pointer field, i.e. as one linked list. Something is related to saving XOR prev and the next address in one field. I don’t understand how it helps us overcome the front and back? Can someone explain this to me? I read the article over here . Can anyone explain this to me? A little more detail? And how does XOR have anything to do with these addresses.

Answer 1

As noted in the article, this method is only useful if you have a pointer to the head or tail of a list; if you only have a pointer in the middle of the list, there’s nowhere to go.

About the method: 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 the prev / next pointer containing the hexadecimal values ​​(addresses) of the previous / next element in the list. 0 is null

Instead of storing two pointers, we can use only one, as described in the article:

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

we will name the new field link = prev XOR next. therefore, with this in mind:

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

Assuming you have a pointer to a list header (which, as you know, has a prev pointer that is null) here, how do you iterate over a list:

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

You go back 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 calculate A ^ C = A ^ (A ^ B) = (A ^ A) ^ B = B.

In the case of linked lists, if you are given a forward pointer or a back pointer and an XOR of the two, you can find another pointer with one XOR. When you repeat the list, you already have one of them, so all you need is XOR to find another; therefore there is no need to store both.

Answer 3

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

A XOR A = 0

When using a doubly linked list, you need to save both the “nearest” and “pre” addresses in your structure. The author says that to save space, you can simply save:

next XOR prev

And browse the list by following these steps:

next = current XOR prev

next = (next XOR prev) XOR prev

next = next XOR (prev XOR prev)

But I really don't understand, because in this example you still need to know "prev" in order to perform your calculations ...

Answer 4

Thus:

You are in some node. You need to move on to the next one. But you have one variable that should store the value of two pointers. How is this possible?

We use the fact that when we cross the list, we know the node address of the previously visited node. But how?

So, the question boils down to the following:

We need to store two values ​​in one variable. At any moment, we know any of them. We need to find another. Is it possible?

Answer YES .

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

Now apply this concept to a DLL.

Save XOR of previous and next node addresses in the current node

If you want to go to the next node, XOR previous node address with the value stored in the current node. You can go to the next one. Similarly, you can move in the opposite direction.