学习 Rust，体验海量链表
7 分钟阅读
原文链接: https://rust-unofficial.github.io/too-many-lists/index.html
有问题，或想一次看完全部最终代码？ 一切都在 Github 上！
注意：本书当前版本针对 Rust 2018 编写， Rust 2018 随 rustc 1.31（2018 年 12 月 8 日）首次发布。若你的 Rust 工具链够新，
cargo new创建的Cargo.toml里应有edition = "2018"这一行（若你在遥远的未来读这本书，也许是更大的数字！）。用更老的工具链也可以，但会解锁秘密困难模式：会出现本书正文完全没提到的额外编译错误。哇，听起来很好玩！
我经常被问如何在 Rust 里实现链表。老实说答案取决于你的需求，现场回答显然不容易。所以我决定写这本书，一劳永逸地把问题讲清楚。
在本系列里，我会完全通过让你实现 6 种链表来教你 Rust 的基础与进阶。在此过程中，你应该学到：
- 以下指针类型：
&、&mut、Box、Rc、Arc、*const、*mut、NonNull（？） - 所有权、借用、继承可变性、内部可变性、
Copy - 各种关键字：
struct、enum、fn、pub、impl、use、…… - 模式匹配、泛型、析构函数
- 测试、安装新工具链、使用
miri - Unsafe Rust：裸指针、别名、stacked borrows、
UnsafeCell、型变
没错，链表糟糕到让你在做出来的时候不得不碰遍这些概念。
一切都在侧边栏（手机上可能折叠），快速参考的话，我们要做的是：
为了大家同一页，我会写出输入终端的所有命令。我也会用 Rust 标准包管理器 Cargo 来开发项目。写 Rust 程序不一定需要 Cargo，但比直接用 rustc 好太多了。若只想随便玩玩，也可以在 play.rust-lang.org 上在浏览器里跑一些简单程序。
后面章节会用「rustup」安装额外 Rust 工具。我强烈建议用 rustup 安装你所有的 Rust 工具链。
开始创建项目：
| |
每个链表放在单独文件里，这样不会丢工作。
值得一提的是，正宗的 Rust 学习体验是：写代码、被编译器吼、然后琢磨那到底是什么意思。我会仔细确保这尽可能频繁发生。学会阅读和理解 Rust 通常很出色的编译器错误和文档，对成为高效的 Rust 程序员极其重要。
虽然其实这是谎话。写这本书时我遇到的编译器错误远多于文中展示的。尤其后面章节我不会展示很多随手「打错（粘贴错）」的错误——每种语言都会遇到。这是编译器对我们大吼的导览。
我们会走得相当慢，老实说大部分时间我都不会太严肃。我觉得编程应该好玩，该死的！ 若你想要信息密度最大、严肃、正式的内容，这本书不适合你。我做的东西没有一样适合你。你错了。
不得不做的公开声明
说清楚：我讨厌链表。带着激情讨厌。链表是糟糕的数据结构。当然链表有几个绝佳使用场景：
- 你要对很大的链表做大量拆分或合并。大量。
- 你在做很酷的免锁并发东西。
- 你在写内核/嵌入式，想用侵入式链表。
- 你在用纯函数式语言，有限的语义和没有 mutation 让链表更好用。
- ……还有更多！
但这些场景对写 Rust 程序的人来说超级罕见。99% 的时候你应该用 Vec（数组栈），剩下 1% 里的 99% 你应该用 VecDeque（数组双端队列）。对大多数工作负载，它们明显是更优数据结构：分配更少、内存开销更低、真随机访问、缓存局部性更好。
链表作为数据结构，和 trie 一样小众且模糊。若我说 trie 是小众结构、普通程序员一辈子不学也能高效工作，大概没人反对——可链表却有某种古怪的名人地位。我们教每个本科生写链表。它是 std::collections 里我没能杀掉的唯一小众集合。它是 C++ 的那个 list！
我们整个社区都应该对把链表当作「标准」数据结构说不。它是不错的数据结构，有几个绝佳场景，但那些场景是例外，不是常态。
显然有人只读这段 PSA 的第一段就不往下读了。字面意义上他们会试图反驳我，列我列的绝佳使用场景之一。就在第一段后面那串东西！
为了能直接链到详细论证，下面是我见过的几种反驳，以及我的回应。若你只想学 Rust，可以直接跳到第一章！
性能并不总是重要
对！也许你的应用受 I/O 限制，或相关代码在根本不重要的冷路径上。但这甚至不是在论证该用链表。这是在论证随便用什么都行。为何将就链表？用链表哈希表！
若性能不重要，那用数组这种自然默认也完全没问题。
若你手上有指针，拆分-追加-插入-删除是 O(1)
对！不过正如 Bjarne Stroustrup 指出，若拿到那个指针的时间完全压过在数组里拷贝所有元素的时间（其实相当快），这其实并不重要。
除非你的工作负载主要由拆分合并成本主导，否则其他操作因缓存效应和代码复杂度受到的惩罚会抹平任何理论收益。
但若你 profiling 发现应用大量时间在拆分合并上，链表可能有收益。
我负担不起摊销
你已经进入相当小众的领域——大多数人负担得起摊销。不过数组在最坏情况下也是摊销的。用数组并不意味着一定有摊销成本。若能预测要存多少元素（或有上界），可以预分配所需全部空间。以我的经验，非常常能预测需要多少元素。尤其在 Rust 里，所有迭代器都提供 size_hint 正是为此。
那样 push 和 pop 就是真正的 O(1)。而且会比链表上的 push 和 pop 快得多。你做指针偏移、写字节、整数加一。不必去找任何分配器。
低延迟怎么样？
但若你无法预测负载，最坏情况延迟上确实有节省！
链表浪费更少空间
嗯，这很复杂。「标准」数组扩缩策略是增长或收缩，使得最多一半数组为空。这确实浪费很多空间。尤其在 Rust 里，我们不会自动收缩集合（若你马上又要填满，收缩是浪费），浪费可能接近无穷！
但这是最坏情况。最好情况下，数组栈整个数组只有三个指针的开销。基本上没开销。
链表则无条件每个元素浪费空间。单链表浪费一个指针，双链表浪费两个。与数组不同，相对浪费与元素大小成正比。元素巨大时浪费接近 0。元素很小（比如字节）时，内存开销可达 16 倍（32 位上 8 倍）！
其实更接近 23 倍（32 位上 11 倍），因为会对字节加 padding，把整个节点大小对齐到指针。
这也假设分配器处于最好情况：节点分配释放密集进行，不会因碎片丢内存。
但若元素巨大、无法预测负载、且有不错的分配器，确实有内存节省！
我在 <函数式语言> 里一直用链表
很好！在函数式语言里链表非常优雅，因为可以不 mutation 地操作、递归描述，还能因惰性魔法处理无限列表。
具体来说，链表好在它们表示一种迭代，而不需要任何可变状态。下一步就是访问下一个子列表。
Rust 大多用迭代器做这类事。它们可以无限，你可以像函数式列表一样 map、filter、reverse、concatenate，而且都同样惰性！
Rust 还让你用*切片*轻松谈论子数组。函数式语言里常见的 head/tail 拆分在 Rust 里就是 slice.split_at_mut(1)。有段时间 Rust 有实验性的切片模式匹配，超酷，但稳定时功能简化了。不过基本切片模式仍然很巧妙！当然切片也能变成迭代器！
但若你受限于不可变语义，链表可以非常好。
注意我不是说函数式编程必然弱或差。然而它在语义上从根本上受限：你多半只能谈论事物是什么，不能谈论怎么做。这其实是特性，因为让编译器能做大量高级变换，可能在不让你操心的情况下找出最佳做法。代价是你能够操心。通常有逃生舱，但到了某个极限你又在写过程式代码。
即使在函数式语言里，当你真正需要数据结构时，也应努力用合适的数据结构。没错，单链表是你控制流的主要工具，但用来实际存一堆数据并查询真的很差。
链表很适合构建并发数据结构！
对！不过写并发数据结构完全是另一回事，不该轻率对待。肯定也不是很多人甚至会考虑做的事。一旦有人写好，你也不是真的在选链表。你在选 MPSC 队列或别的。实现策略在这种情况下离得很远！
但若如此，链表是免锁并发黑暗世界里事实上的英雄。
咕哝咕哝内核嵌入式侵入式什么的。
很小众。你在谈论甚至不用语言运行时的情况。这难道不是你做事很奇怪的红旗吗？
也极其 unsafe。
但若如此，在栈上构建你的零分配链表吧。
迭代器不会因无关的插入/删除而失效
那是你在跳的微妙舞蹈。尤其若没有垃圾收集器。我可能会说，取决于细节，你的控制流和所有权模式可能有点太缠在一起。
但若如此，你可以用游标做一些真的很酷很疯的东西。
它们简单，很适合教学！
嗯，对。你正在读一本专门为此前提写的书。 嗯，单链表挺简单。双链表可以变得相当棘手，我们后面会看到。
喘口气
好。说完了。我们来写无数条链表。