This is the Simplified Chinese translation of Learn Rust by writing Entirely Too Many linked lists.

GitBook在线阅读

通过大量的链表学习Rust

有任何issue或者想要查看所有的最终代码？它们都在Github上！

我最近经常被问到如何在Rust里实现一个链表。这个问题的答案实际上取决于你的需求，且并不是很容易立刻回答的。因此,我决定写这本书来通过易懂的方式一劳永逸的回答这个问题。

在这一系列教程中，我将会仅通过让你实现6个链表，教会你基础和高级的Rust编程。通过这么做，你应该能够学会：

  • 几种指针类型： &, &mut, Box, Rc, Arc, *const, *mut
  • 所有权，借用，可变性继承，内部可变性，Copy
  • 所有的关键词：struct, enum, fn, pub, impl, use, …
  • 模式匹配，泛型，析构器
  • 测试
  • 不安全Rust基础

没错，链表真的很糟糕，你必须用到所有这些概念才能够实现它。

作为快速参考，这是我们即将做的内容：

  1. 一个糟糕的单向链表栈
  2. 一个还行的单向链表栈
  3. 一个固定的单向链表栈
  4. 一个很糟糕但是安全的双向链表Deque
  5. 一个不安全的单向链表队列
  6. TODO：一个还行但是不安全的双向链表Deque
  7. 追加：一系列很蠢的列表

就在这页，我会写出所有我们会在控制台调用的指令。我会使用Rust的标准包管理器，Cargo，来进行项目的开发。Cargo对于开发一个Rust程序并不是必要的，但是它比直接使用 rustc 要好上太多。如果你只想随便玩玩，也可以通过 https://play.rust-lang.org/ ，在浏览器里直接运行简单的程序，尽管它不支持单元测试。

让我们开始构建我们的项目吧：

  1. > cargo new lists
  2. > cd lists

我们会把每个列表放在不同的文件里，这样便不会丢失工作。

需要注意的是，真正的Rust学习体验涉及实际编写代码，让编译器对你大吼大叫，然后尝试去找出这到底意味着什么。我会小心的保证这件事经常发生。学会阅读并理解Rust的（通常）极好的编译错误以及代码文档对成为一个有创造力的Rust程序员是极其重要的。

上面说的其实是骗人的。在写书时我遇到了比我所写出来的多得多的错误。特别的，在之后的章节中我不会指出“我打错了XXX”这类所有语言中常见的错误。这本书是一个让编译器对你大吼大叫的向导旅行。

我们将以较慢的速度前行，而且我全程都不会怎么严肃起来。我觉得编程应该是非常欢乐的，让我们搞起！如果你是那种希望大信息量、严肃和正式的内容的人，这本书不是为你准备的。我做的东西没一个是为你准备的。你错了。

义务公共服务声明

我们先100%的搞清楚这一点：我讨厌链表。沉痛的讨厌着。链表是极其糟糕的数据结构。好吧，当然这里有一些链表的重要用例：

  • 你想对大容量的列表进行大量的分隔或合并操作。大量的。
  • 你在做一些很牛逼的无锁并行计算之类的东西。
  • 你在写内核/嵌入式程序并且想要使用侵入式列表。
  • 你在使用一个纯函数式语言，链表的受限语法以及不可变性让它更容易被处理。
  • … 还有更多！

但是，对于任何写Rust程序的人，以上的所有情况都是极其稀有的。99%的时候你应该只使用 Vec（数组栈），而剩下的1%内的99%的时候你应该使用一个 VecDeque （数组双向队列）。由于较少的内存分配、更低的内存负载、真正的随机访问和缓存局部性，它们在大多数工作条件下都显然是更好的数据结构。

链表是和字典树（trie）一样用途狭窄并且模糊不清的数据结构。有的人会回避我，说字典树是一个极其特定的数据结构，像你们这样的普通程序员即便整个编程生涯不学也可以过的很开心——而链表则有着显赫的名声。我们教给每个大学毕业生如何写链表。它是我没办法从 std::collections 里干掉的唯一一个不泛用的数据结构。它也是C++里的那个list！

我们应该作为一个社群，对把链表当做一个“标准”数据结构的行为说不。它是一个有一些极好用途的还行的数据结构，但是这些用例是特殊的，不是通常的。

有些人显然只读了这段声明的第一段就停止了阅读。他们会尝试通过列出我所写的链表的重要用例中的一项来反驳我的言论。那东西可就在第一段后面啊！

我可以更详细的开始讨论这件事了，下面是一些我曾经见过的反论的尝试，以及我对它们的回应。如果你只是想学一些Rust的话，请随意跳转到结尾！

性能并不总是重要的

是的！也许你的应用程序是I/O密集的，或者要讨论的代码的运行频率太低以至于性能不重要。但是这甚至都不是使用链表的一个论据。这是使用任何东西的论据。为什么要使用一个链表呢？用一个链式哈希表（linked hash map）吧！

如果性能不重要，那选择采用数组的自然特性当然是可以的。

如果你拥有一个链表指针，那么分割-附加-插入-删除操作的时间复杂度都是O(1)

嗯哼！虽然Bjarne Stroustrup所说的是正确的，但如果获取指针所用的时间远远超出了简单的拷贝数组内所有元素的时间（它真的很快），那这其实根本不重要。

除非你的程序负载完全由分割和合并操作的时间消耗所主导，其他每一个操作由于缓存不友好和代码复杂度带来的时间损失会消除任何理论上的好处。

但是没错，如果你对应用程序进行性能剖析（profiling），发现它花了大量的时间在分割和合并上，使用链表可能让你节省时间。

我没法忍受复杂度均摊（armortization）

你已经进入到一个十分狭窄的空间——大多数人都能忍受复杂度均摊。数组只在最坏情况下进行复杂度均摊。使用数组也并不意味着你一定要进行均摊。如果你可以预测有多少元素要存储（或者有一个上界），你可以预先分配好所有需要的空间。在我的经验里，能够预测需要的元素数量是非常常见的。对于Rust来说，所有的迭代器都为这种情况提供了一个 size_hint。

在这种情况下，push和pop就会真正成为 O(1) 操作。而且它们将会比在链表上的 push和 pop 高出一个数量级。你进行一次指针偏移，写入字节，递增一个整数。不需要访问任何的内存分配器。

如果你要求低延迟的话，这样不是更好么？

但是没错，如果你无法预测你的工作负载，那最坏情况下的延迟降低也要考虑在内！

链表浪费的空间更少

呃，这东西比较复杂。一个“标准”的数组大小重分配策略会将数组增长或缩小，来保证最多只有一半空间是空的。这确实会很多浪费的空间。尤其是在Rust中，我们不会自动缩减集合的内存占用（如果你要把它填充回去，这只会造成浪费），因此浪费程度可以达到正无穷！

但这是最坏情况的状态。在最优情况下，一个数组栈管理整个数组只需要三个指针的额外开销——基本可以忽略。

而链表则对每个元素都无条件的浪费内存空间。一个单向链表的元素浪费了一个指针，而双向链表浪费两个。和数组不一样，链表的相对浪费量和元素数量呈正比。如果一个元素所占空间非常巨大，浪费会趋近于0。如果每个元素所占空间很小（例如，比特），这可能造成最多16倍的内存浪费（如果是32位，8倍）！

实际的数字应该更接近23倍（或者32位时的11倍），因为那一个字节需要进行位对齐，让整个节点的大小对齐到一个指针。

这也是在对内存分配器进行最优条件假设的前提下得出的结论：节点的内存分配和释放会紧密的进行，并且你不会因为内存碎片化而丢失空间。

但是没错，如果每个元素所占空间巨大，你无法预测负载，并且拥有一个高效的内存分配器，那这确实可以节省内存！

我在 <键入函数式语言名称> 中一直使用链表

棒极了！在函数式语言中使用链表是非常优雅的，因为你可以在不涉及任何可变性的情况下操作它们，可以递归的描述它们，甚至可以借助惰性求值的魔法来操作无穷大列表。

特别的，链表因为无需任何可变状态就可以表示迭代而显得特别优雅。迭代的下一步就是访问下一个子列表而已。

不过应该注意的是，Rust可以对数组进行模式匹配，并且使用切片来处理子数组！从某些角度来说，它甚至比一个函数式列表更富表达力，因为你可以专门处理最后一个元素或者甚至“没有第一个和最后两个元素的数组”或者任何你想要的疯狂的东西。

你不能通过切片来构造一个列表倒是真的。你只能把它们撕成小片。

对于惰性求值，我们有迭代器作为替代。它可以是无穷的，而你可以像对待一个函数式列表一样对它们 map, filter, reverse 和 concatenate，这些操作都会被惰性的执行。不必说，数组切片也可以被转换（coerce）成一个迭代器。

不过没错，如果你只限制于使用不可变的语义，链表是很好用的。

注意我并没有说函数式编程一定是弱的或糟糕的。然而它确实是从根本上语义受限的：你很大程度上只被允许讨论事情是怎么样，而非它们应该如何被完成。这实际上是一个特性，因为它让编译器得以进行成吨的诡异变换来找出潜在的最佳工作方式而不需要你去担心它。然而，这也带来了完全无法去担心它的代价。通常的情况下可以找到应急出口，但到达某个限度后你又会开始写过程式的代码了。

即便在函数式语言中，你也应该在确实需要用到数据结构时选择恰当的数据结构。没错，链表是操作控制流的主要工具，但是如果要在里面存储一堆数据并且查询的话，它们是非常糟糕的。

在构建并行数据结构时，链表是很好用的！

没错！尽管如此，实现一个并行数据结构真的是另一个很大的话题，不应该被轻视。这显然都不是很多人会考虑去做的事。当它实际被实现以后，你也真的不会真的选择使用链表。你会选择使用一个MPSC队列或者其他什么东西。在这个情况下实现策略实际上已经在考虑范围之外了！

不过没错，链表是无锁并行开发的暗黑领域的绝对王者。

呃。。内核。。嵌入式。。用了。。侵入式链表。。。

这很用途狭窄。你在讨论这个的时候甚至没有使用你所用语言的运行时。这难道不是你正在做一些奇怪的事的警告信号么？

这也是非常不安全（unsafe）的。

但是当然了。在栈上构建你的碉堡的零内存分配列表吧。

无关的插入和删除不会让迭代器失效

你在跳一支危险的舞。尤其是在你没有垃圾收集器的时候。根据细节，我应该会争论说你的控制流和所有权模式恐怕有点纠缠的太紧了。

但是没错，你可以用cursor做一些非常酷的东西。

它们很简单并且容易用于教学！

呃，是啊。你就在读一本以此作为前提写的书。 好吧，单向链表是相当简单的。双向链表则会变得比较麻烦，我们马上就会看到。

喘口气

Ok，这个问题解决了。让我们开始写一大堆链表吧。