如何只用一个指针实现双链表？

Question

如何只用一个指针实现双链表？

找到prev和next节点需要O(1)时间.

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

Answer 1

这听起来似乎是不可能的,就像它说的那样.通常,您不能仅使用一个指针来实现两个指针.

您可能能够将两个16位偏移量压缩到单个(假定的32位)指针或其他一些"聪明的黑客"所使用的空间中,但通常这听起来不可能.

本文描述了一个基于XOR的技巧:指针值,但我会考虑一个hack(它对指针值进行逐位算术).

Answer 2

有一个经典的黑客:存储2个指针(上一个和下一个)的XOR,当你在列表中旅行时,你手边总有一个(你刚从那里来)并且你可以用存储的值对其进行异或来获得其他指针.

不用说,这在GC环境中不起作用.

Answer 3

也许通过使用XOR链表？

Answer 4

已经提出的一个解决方案是XOR解决方案.

另一种解决方案是"翻转方"解决方案:如果您的问题采用以下方式:

您将获得指向第一个元素的指针,并且您希望:

1. 在链接列表中前进我在O(i)中的步骤
2. 返回链接列表我在O(i)中的步骤
3. 在O(1)的当前位置添加或删除项目

因此,始终只有一个指向链接列表的指针,并且只有一个入口点(只需返回和转发,如1和2),您可以执行以下操作:

• 保存两个指针:p1,p2
• 从第一个指针p1你可以返回,从第二个指针p2你前进.
• p1之前的链表项向后,而p2之后的项指向前.

所以你的列表看起来像这样:

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

p1指向当前元素,p2指向下一个元素,i1 ... i7是列表中的项目

前进是在O(1)中完成的,因此通过翻转指针向后移动:

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

该解决方案在可读性方面优于XOR解决方案,并且对于人类来说更容易理解.缺点是您的链表不能有多个入口点.