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

How to implement a double linked list with only on开发者_如何学Goe pointer?

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

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

---

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

---

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.

---

Maybe by using a XOR linked list?

---

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.

---

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.

---

I recently stumbled on a nice approach to this problem in a book by Niklaus Wirth ("Algorithms + Data Structures = Programs"). It goes like this... You have a node, similar to the one you suggested, except that it does not aggregate a pointer to the next (nor to the previous) Node. Instead, you have a single member link that represents the distance (e.g. in units of sizeof(Node)) from the previous node (pointed to by Node* pPrev) in the chain to the next node (pointed to by Node* pNext) in the chain:

size_t link = pNext - pPrev;

So the node could look something like this:

struct Node {
    int val;
    size_t link;
}

Then, to proceed from the present node, pCurrent, combined with the previous node pPrev, to the next Node* pNext by writing:

pNext = pPrev + pCurrent->link;

Similarly, you can traverse in the opposite direction by rearranging this equation:

pPrev = pNext - pCurrent->link;

However, this approach is somewhat restricted by C/C++ pointer arithmetic because the difference of two pointers is only well defined if both point inside of the same memory block. So essentially, all of your nodes will have to be contained inside one huge array of Nodes.