我们可以使用单个指针实现双向链表吗？

Question

我想使用这样的结构：

struct node {
   char[10] tag;
   struct node *next;
};

我想用上面的结构来创建一个双向链表。这可能吗？如果是的话，我该如何实现？

Answer 1

这不是完全可能的。双重 linked 列表需要两个指针，每个方向一个指向 link。

根据您的需要，异或 linked 列表可能会满足您的需要（参见 HolyBlackCat 的回答）。

另一种选择是通过做一些事情来稍微解决这个限制，例如在循环访问列表时记住您处理的最后一个节点。这将让您在处理过程中返回一个步骤，但不会使列表加倍 linked。

Answer 2

您可以声明并支持两个指向节点 head 和 tail 的初始指针。在这种情况下，您将能够将节点添加到列表的两端。

这样的列表有时称为双向列表。

但是列表本身将是一个转发列表。

使用这样的列表，您可以模拟一个队列。

Answer 3

是的，这是可能的，但这是一个肮脏的 hack。

叫做异或链表。 (https://en.wikipedia.org/wiki/XOR_linked_list)

每个节点将 next 和 prev 的 XOR 存储为 uintptr_t。

这是一个例子：

#include <cstddef>
#include <iostream>

struct Node
{
    int num;
    uintptr_t ptr;
};

int main()
{
    Node *arr[4];
    // Here we create a new list.
    int num = 0;
    for (auto &it : arr)
    {
        it = new Node;
        it->num = ++num;
    }
    arr[0]->ptr =                     (uintptr_t)arr[1];
    arr[1]->ptr = (uintptr_t)arr[0] ^ (uintptr_t)arr[2];
    arr[2]->ptr = (uintptr_t)arr[1] ^ (uintptr_t)arr[3];
    arr[3]->ptr = (uintptr_t)arr[2];

    // And here we iterate over it
    Node *cur = arr[0], *prev = 0;
    do
    {
        std::cout << cur->num << ' ';
        prev = (Node *)(cur->ptr ^ (uintptr_t)prev);
        std::swap(cur, prev);
    }
    while (cur);
    return 0;
}

它按预期打印 1 2 3 4。

Answer 4

我想提供一个备选答案，归结为 "yes and no"。

首先，"sort of impossible" 如果您想获得每个节点只有一个指针的双向链表的全部好处。

异或表

这里还引用了异或链表。它通过将两个指针有损压缩到一个你用单链表丢失的指针中来保留一个主要好处：反向遍历它的能力。它不能做一些事情，比如在给定节点地址的情况下，在恒定时间内从列表中间移除元素，并且能够在前向迭代中返回到前一个元素，并在线性时间内移除任意元素，如果没有XOR 列表（您同样在此处保留两个节点指针：previous 和 current）。

性能

然而，评论中还提到了对性能的渴望。鉴于此，我认为有一些实用的替代方案。

首先，双向链表中的 next/prev 指针不一定是 64 位系统上的 64 位指针。它可以是一个 32 位连续地址的两个索引 space。现在你得到了一个指针的内存价格的两个索引。然而，尝试在 64 位上模拟 32 位寻址是非常复杂的，可能不是您想要的。

但是，要获得链接结构（包括树）的全部性能优势，通常需要您重新控制节点在内存中的分配和分布方式。链接结构往往是瓶颈，因为如果您只对每个节点使用 malloc 或普通 operator new，例如，您将失去对内存布局的控制。通常（不总是——取决于内存分配器，以及是否一次分配所有节点，您可能会很幸运）这意味着连续性的丢失，这意味着空间局部性的丢失。

这就是为什么面向数据的设计比其他任何东西都更强调数组：链接结构通常对性能不是很友好。如果您要在逐出之前访问同一块（缓存 line/page，例如）中的相邻数据，那么将块从较大的内存移动到较小、更快的内存的过程会很受欢迎。

不常被引用的展开列表

所以这里有一个不常被讨论的混合解决方案，即展开列表。示例：

struct Element
{
    ...
};

struct UnrolledNode
{
    struct Element elements[32];
    struct UnrolledNode* prev;
    struct UnrolledNode* next;
};

展开列表结合了数组和双向链表的特点。它会给你很多空间局部性，而无需查看内存分配器。

它可以向前和向后遍历，它可以在任何给定时间以便宜的方式从中间删除任意元素。

并且它将链表开销减少到绝对最小值：在这种情况下，我硬编码了一个展开的数组大小，每个节点有 32 个元素。这意味着存储列表指针的成本已缩减至其正常大小的 1/32。从列表指针开销的角度来看，这甚至比单链表更便宜，而且遍历速度通常更快（因为缓存局部性）。

它不是双向链表的完美替代品。首先，如果您担心删除时指向列表中元素的现有指针失效，那么您必须开始担心空置的 spaces (holes/tombstones) 会被回收（可能通过关联每个展开节点中的空闲位）。那时你正在处理实现内存分配器的许多类似问题，包括一些次要形式的碎片（例如：有一个展开的节点有 31 个空 spaces 并且只有一个元素被占用 - 该节点仍然有留在内存中以避免失效，直到它完全变空。

它的 "iterator" 允许 insertion/removal to/from 中间通常必须大于指针（除非如评论中所述，您在每个指针中存储额外的元数据元素）。它可能会浪费内存（通常没有实际意义，除非你有非常小的列表）要求，比如说，32 个元素的内存，即使你有一个只有 1 个元素的列表。与上述任何解决方案相比，它的实施往往要复杂一些。但它在性能关键场景中是一个非常有用的解决方案，而且通常可能值得更多关注。它在计算机科学中并没有被提及太多，因为从算法的角度来看，它并没有比常规链表做得更好，但引用的位置对性能以及现实世界场景中的性能都有重大影响。

Answer 5

如果不调用未定义的行为，就不可能以可移植的方式： Can an XOR linked list be implemented in C++ without causing undefined behavior?

我们可以使用单个指针实现双向链表吗？

Can we implement a doubly-linked list using a single pointer?

c

c++

logic

data-structures