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

这听起来好像是不可能的，就像它所说的那样。通常，不能仅使用一个指针实现两个指针。

您也许可以将两个 16 位偏移量压缩到单个（假定为 32 位）指针或其他一些“聪明的黑客”使用的空间中，但总的来说，这听起来是不可能的。

本文描述了一个基于异或的技巧：指针值，但我认为这是一个黑客（它对指针值进行按位算术）。

也许通过使用 XOR 链表？

如果然后有一个中间节点，其中包含一个后退指针。sizeof(int) == sizeof(Node *)

F.D.公司

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

其中包含一个值和一个指向以下节点的指针，在 val 中包含指向前一个中间节点的反向指针，在 p 中包含指向以下节点的正向指针。(real node)(intermediate node)(intermediate node)(read node)

顺便说一句，这是一个愚蠢的问题。我看不出它能教出任何有价值的东西。

有一个经典的技巧：存储 2 个指针（上一个和下一个）的 XOR，当浏览列表时，您手头总是有 1 个指针（您刚刚从那里来），您可以用存储的值进行 XOR 以获取另一个指针。

毋庸置疑，这在 GC 环境中是行不通的。

已经提出的一种解决方案是异或解决方案。

另一种解决方案是“反转”解决方案： 如果您的问题是这样表述的：

系统会为您提供指向第一个元素的指针，并且您希望：

1. 在 O（i） 中的链表 i 步长中前进
2. 返回链表 i 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 解决方案，并且对人类来说更容易理解。缺点是链表不能有多个入口点。

我最近在尼克劳斯·沃斯（Niklaus Wirth）的一本书（“算法+数据结构=程序”）中偶然发现了解决这个问题的好方法。事情是这样的......您有一个节点，类似于您建议的节点，只是它不会聚合指向下一个（或前一个）的指针。相反，您有一个成员，它表示从链中的前一个节点（指向 ）到链中的下一个节点（指向 ）的距离（例如，以 的单位表示）：Nodelinksizeof(Node)Node* pPrevNode* pNext

size_t link = pNext - pPrev;

因此，节点可能如下所示：

struct Node {
    int val;
    size_t link;
}

然后，要从当前节点继续，结合前一个节点，到下一个节点，方法是写：pCurrentpPrevNode* pNext

pNext = pPrev + pCurrent->link;

同样，您可以通过重新排列此等式来沿相反方向遍历：

pPrev = pNext - pCurrent->link;

但是，这种方法在某种程度上受到 C/C++ 指针算术的限制，因为只有当两个指针都指向同一内存块内时，两个指针的差异才能很好地定义。因此，从本质上讲，所有节点都必须包含在一个巨大的 s 数组中。Node