6.1 数据布局

原文链接: https://rust-unofficial.github.io/too-many-lists/sixth-layout.html

我们先来研究敌人的结构。双向链表概念上很简单，但正因如此它才能欺骗、操纵你。它和我们反复见过的链表一样，只是链接是双向的。链接翻倍，邪恶也翻倍。

所以不是这种（为简洁起见，省略 Some/None）：

1

... -> (A, ptr) -> (B, ptr) -> ...

而是这种：

1

... <-> (ptr, A, ptr) <-> (ptr, B, ptr) <-> ...

这让你可以从任一方向遍历链表，或用 cursor 来回移动。

为换取这种灵活性，每个节点要存两倍指针，每次操作要修复更多指针。复杂到足以让人更容易犯错，所以我们会做大量测试。

你可能也注意到，我故意没画链表的两端。因为这里确实有一些值得辩护的实现选择。我们肯定需要两个指针：一个指向链表头，一个指向尾。

在我看来有两种主要做法：「传统」和「哑节点」。

传统做法是我们实现栈时的简单延伸——在栈上存 head 和 tail 指针：

1
2
3

[ptr, ptr] <-> (ptr, A, ptr) <-> (ptr, B, ptr)
  ^                                        ^
  +----------------------------------------+

这没问题，但有一个缺点：边界情况。链表现在有两条边，边界情况也翻倍。漏掉一个就可能出严重 bug。

哑节点做法试图通过加一个不含数据、把两端连成环的额外节点来平滑边界情况：

1
2
3

[ptr] -> (ptr, ?DUMMY?, ptr) <-> (ptr, A, ptr) <-> (ptr, B, ptr)
           ^                                                 ^
           +-------------------------------------------------+ 

这样每个节点始终有指向前驱和后继的真实指针。即使删掉最后一个元素，也只是让哑节点指向自己：

1
2
3

[ptr] -> (ptr, ?DUMMY?, ptr) 
           ^             ^
           +-------------+

我有一部分觉得这样非常令人满意、优雅。可惜它有几个实际问题：

问题 1：多一次间接访问和分配，尤其是空链表也必须包含哑节点。可能的解法：

• 直到插入元素才分配哑节点：简单有效，但会带回我们试图用哑指针避免的边界情况！

• 使用静态写时复制（COW）的空哑节点单例，配合某种巧妙方案让 COW 检查搭便车于普通检查：说真的我很心动，我真的很爱这套，但本书不能走那条黑暗之路。想看那种变态实现，去读 ThinVec 源码。

• 把哑节点放在栈上——在没有 C++ 风格移动构造函数的语言里不现实。用 pinning 或许能搞点怪招，但我们不会。

问题 2：哑节点里存什么值？整数还好，若链表存满 Box 呢？我们可能根本无法初始化这个值！可能的解法：

• 让每个节点存 Option<T>：简单有效，但也臃肿烦人。

• 让每个节点存 MaybeUninit<T>。可怕又烦人。

• 非常小心、巧妙的继承式类型双关，让哑节点不包含数据字段。同样诱人，但极其危险烦人。想看那种变态实现，去读 BTreeMap 源码。

对 Rust 这类语言，问题确实压过了便利，所以我们坚持传统布局。设计与上一章 unsafe 队列基本相同：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

pub struct LinkedList<T> {
    front: Link<T>,
    back: Link<T>,
    len: usize,
}

type Link<T> = *mut Node<T>;

struct Node<T> {
    front: Link<T>,
    back: Link<T>,
    elem: T, 
}

（既然到了双向链表双端队列，我们终于有资格自称 LinkedList，因为这才是真正的链表。）

这还不算真正的生产级布局。它还行，但还有些魔法能让 Rust 更好理解我们在做什么。要做到那点，我们得……再深入一层。