How to implement a double linked list with only one pointer?

Question

How to implement a double linked list with only one pointer?

It takes O(1) time to find the prev and next Node.

struct Node
{
   int val;
   Node* p;
};

Answer 1

This sounds as if it's impossible, the way it's stated. You can't implement two pointers using only one, in general.

You might be able to squeeze two 16-bit offsets into the space used by the single (assumed 32-bit) pointer, or some other "clever hack", but in general this sounds impossible.

This article describes a trick based on XOR:ing the pointer values, but I would consider that a hack (it does bitwise arithmetic on pointer values).

Answer 2

Maybe by using a XOR linked list?

Answer 3

If sizeof(int) == sizeof(Node *) then have an intermediate node which contains a back pointer.

E.g.

(real node) -> (intermediate node) -> (read node) -> (etc)

where (real node) contains a value and a pointer to the following (intermediate node), and (intermediate node) contains in val a back pointer to the previous intermediate node and in p a forward pointer to the following (read node).

BTW, it's a stupid, stupid question. I can't see it teaches anything of value.

Answer 4

There is a classic hack: store the XOR of the 2 pointers (Prev and Next) and when traveling the list you always have 1 of those at hand (you just came from there) and you can XOR it with the stored value to get the other pointer.

Needless to say that this won't work in a GC environment.

Answer 5

One solution that has already been suggested is the XOR solution.

Another solution is the "flipping sides" solution: If your problem is phrased the following way:

You are given a pointer to the first element, and you would like to:

1. Go forward in the linked list i steps in O(i)
2. Go back in the linked list i steps in O(i)
3. Add or remove items at the current location at O(1)

So that there is always only one pointer to the linked list, and there is only one entry point (just going back and forward, like in 1 and 2), you could do the following:

• Save two pointers: p1, p2
• From the first pointer p1 you can go back, from the second pointer p2 you go forward.
• The linked list items that are before p1 point backwards, whereas the items after p2 point forward.

So your list would look like this:

                  p1 p2
                  |  |
                  V  V
i1 <- i2 <- i3 <- i4 i5 -> i6 -> i7

p1 points to the current element, p2 points to the next element, i1 ... i7 are the items in the list

Going forward is done in O(1), and so is going backward, by flipping pointers:

Forward one step:
                        p1 p2
                        |  |
                        V  V
i1 <- i2 <- i3 <- i4 <- i5 i6 -> i7


Backward one step: 
            p1 p2
            |  |
            V  V
i1 <- i2 <- i3 i4 -> i5 -> i6 -> i7

This solution is better than the XOR solution in its readability and that it is more understandable for humans. The disadvantage is that you can not have several entry points to your linked list.