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

Question

我想使用如下结构:

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

我想使用上面的结构来创建一个双向链表.这是可能的,如果是的话,那我怎么能实现呢？

Answer 1

是的,这是可能的,但这是一个肮脏的黑客.

它被称为XOR链表.(https://en.wikipedia.org/wiki/XOR_linked_list)

每个节点存储一个XOR next和prev一个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 2

我想提供另一个答案,归结为"是和否".

首先,如果你希望获得双链表的全部好处,每个节点只有一个指针,那就太"不可能了".

异或列表

然而,这里引用的也是XOR链表.它通过对两个指针进行有损压缩来保留一个主要的好处,这两个指针与单链表中丢失的指针相符:反向遍​​历它的能力.它只能在给定节点地址的恒定时间内从列表中间删除元素,并且能够在前向迭代中返回前一个元素并在线性时间中删除任意元素更简单,如果没有XOR列表(您同样在那里保留两个节点指针:previous和current).

性能

然而,评论中还引用了对表现的渴望.鉴于此,我认为有一些实际的替代方案.

首先,双向链表中的next/prev指针不必是64位系统上的64位指针.它可以是32位连续地址空间中的两个索引.现在你有两个指针用于一个指针的内存价格.尽管如此,尝试在64位上模拟32位寻址是非常复杂的,可能并不完全是你想要的.

但是,要获得链接结构(包括树)的全部性能优势,通常需要您重新控制节点在内存中的分配和分配方式.链接结构往往是瓶颈,因为如果你只是为每个节点使用malloc或普通operator new,例如,你就失去了对内存布局的控制.经常(并非总是如此 - 你可以根据内存分配器获得幸运,以及是否一次性分配所有节点)这意味着失去连续性,这意味着空间局部性的丧失.

这就是为什么面向数据的设计强调数组的重要性:链接结构通常对性能不是很友好.如果您要在驱逐之前访问同一块(缓存行/页面)内的相邻数据,则将块从较大内存移动到较小,较快内存的过程就像它一样.

不常被引用的展开列表

所以这里有一个混合解决方案,不经常讨论,这是展开的列表.例:

struct Element
{
    ...
};

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

展开的列表将数组和双向链表的特征组合成一个.它将为您提供大量空间局部性,而无需查看内存分配器.

它可以向前和向后移动,它可以在任何给定时间从中间移除任意元素以便宜.

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

它不是双链表的完美替代品.首先,如果您担心删除时列表中元素的现有指针无效,那么您必须开始担心将空闲空间(洞/墓碑)留在后面(可能通过关联每个展开的空闲位)节点).那时你正在处理许多类似的关于实现内存分配器的问题,包括一些小的碎片形式(例如:有一个展开的节点有31个空格并且只有一个元素占用 - 节点仍然需要留在内存中避免失效,直到它变成完全空的).

允许插入/移出中间的"迭代器"通常必须大于指针(除非在注释中指出,否则存储每个元素的附加元数据).它可以浪费内存(除非你有真正的小清单),即使你有一个只有1个元素的列表就需要32个元素的内存.实施它往往比上述任何解决方案都复杂一些.但它在性能关键的场景中是一个非常有用的解决方案,通常可能值得更多关注.这是一个在计算机科学领域没有这么多的人,因为它从算法的角度来看并没有比常规的链表更好,但是参考的位置对现实场景中的性能也有很大的影响.

Answer 3

这不是完全可能的.双向链表需要两个指针,一个用于每个方向的链接.

根据您的需要,XOR链表可以满足您的需求(参见HolyBlackCat的答案).

另一个选择是稍微解决这个限制,例如在迭代列表时记住您处理的最后一个节点.这将允许您在处理过程中返回一步,但它不会使列表双向链接.