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 search for the previous and next Node.

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

Answer 1

It sounds like it's impossible, as it was said. You cannot implement two pointers using only one.

You may be able to squeeze two 16-bit offsets into the space used by a single (supposed 32-bit) pointer or other smart hack, but in general this sounds impossible.

This article describes an XOR-based trick: pointer values, but I would have thought it was hacking (it's bitwise arithmetic on a value pointer).

Answer 2

There is a classic hack: save the XOR from two pointers (Prev and Next), and while traveling on the list, you always have one of them (you just came from there), and you can XOR it with the saved value to get another pointer.

Needless to say, this will not work in a GC environment.

Answer 3

Perhaps using a linked XOR list ?

Answer 4

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

Another solution is the solution to the "flip side": If your problem is formulated as follows:

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

• Go to the linked list i steps in O (i)
• Return to the linked list of i steps in O (i)
• Add or remove items at current location at point O (1)

So, there is always only one pointer to a linked list, and there is only one entry point (only to go back and forth, as in 1 and 2), you can do the following:

• Save two pointers: p1 , p2
• You can go back from the first pointer p1 , from the second pointer p2 , which you are moving forward.
• Items in a linked list that point backward before p1 , while items after p2 point forward.

So your list will look like this:

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

p1 indicates the current element, p2 indicates the next element, i1 ... i7 are the elements in the list

Going forward is performed in O (1), and so it goes backward, turning the pointers:

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

This solution is better than the XOR solution in its readability, and that it is more understandable to people. The disadvantage is that you cannot have multiple entry points on your list.

Answer 5

If sizeof(int) == sizeof(Node *) , then there is an intermediate node that contains a back pointer.

eg.

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

where (real node) contains the value and a pointer to the next (intermediate node) , and (intermediate node) contains in val a backward pointer to the previous intermediate node and in the pointer pa forward to the next (read node) .

By the way, this is a stupid, stupid question. I don’t see this teach anything valuable.

Answer 6

I recently came across a good approach to this problem in a book by Nicklaus Wirth ("Algorithms + Data Structures = Programs"). It looks like this ... You have a node similar to the one you proposed, except that it does not aggregate a pointer to the next (or previous) Node . Instead, you have a single link member that represents the distance (for example, in units of sizeof(Node) ) from the previous node (which Node* pPrev ) in the chain to the next node (which Node* pNext ) in the chain:

 size_t link = pNext - pPrev; 

So node might look something like this:

 struct Node { int val; size_t link; } 

Then, to move from the current node, pCurrent , in combination with the previous node pPrev , to the next Node* pNext , writing:

 pNext = pPrev + pCurrent->link; 

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

 pPrev = pNext - pCurrent->link; 

However, this approach is somewhat limited by the arithmetic of pointers to C / C ++, since the difference of two pointers is only well defined if both points are inside the same memory block. In fact, all your nodes should be contained within one huge array of Node s.