用太多链表写法学习Rust

有任何问题或想一次性查看所有最终代码吗？所有代码都在Github上！

说明: 本书当前版本是针对Rust 2018编写的，第一次发布是rustc 1.31 (2018-12-08) 如果你的rust工具链足够新，cargo new创造的Cargo.toml文件应该包含一行 edition = "2018"（如果你在很久以后读到这篇文章，可能看到更大的数字！）。你可以用旧版工具链，但是会解锁一个隐藏的困难模式，你会得到书里没有提到的额外的编译器报错。哇哦，有意思！

我经常被问到如何在Rust中实现链表。老实说，答案取决于你的需求是什么，要当场回答这个问题显然不是超级容易。因此，我决定写这本书来一劳永逸地全面回答这个问题。

在这个系列中，我将通过让你实现6个链表来教你基本和高级的Rust编程。在这样做的过程中，你应该学会：

下列指针类型： &, &mut, Box, Rc, Arc, *const, *mut
所有权、借用、继承可变性、内部可变性、Copy复制性
所有的关键词： struct, enum, fn, pub, impl, use, ...
模式匹配、泛型、析构器
测试
基本不安全Rust

是的，链表真是如此的可怕，以至于你在制作它们时要处理所有这些概念。

一切都在侧边栏中（在移动端可能会被折叠），但为了快速参考，这里是我们要做的：

为了使我们的得到的结果一致，我将写出所有输入终端的命令。我还将使用Rust的标准包管理器Cargo来开发这个项目。Cargo并不是写Rust程序所必需的，但它比直接使用 rustc要好得多。如果你只是想玩玩，你也可以通过play.rust-lang.org 在浏览器中运行一些简单的程序。

让我们开始做我们的项目吧：

> cargo new --lib lists
> cd lists

我们会把每个列表放在一个单独的文件中，这样我们就不会失去任何工作。

需要注意的是，真实的Rust学习经历包括写代码，让编译器对你咆哮，并试图弄清楚这些咆哮到底是什么意思。我将仔细确保这种情况尽可能频繁地发生。学会阅读和理解 Rust普遍优秀的编译器错误和文档，这对于成为一个高效的Rust程序员来说非常重要。

虽然实际上这是一个谎言。在写这本书的过程中，我遇到的编译器错误远远多于我展示的。特别是，在后面的章节中，我不会展示很多随机的"打错字（复制粘贴）"的错误，就是你会在每一种语言中都能遇到的错误。这是一次让编译器向我们尖叫的导游之旅。

我们的进度会很慢，而且老实说，整个过程中我不会很认真。我认为编程应该是有趣的，哇哈哈! 如果你是那种想要最大化信息密集、严肃、正式内容的人，这本书不适合你。我所做的一切都不适合你。你错了。

义务公益广告

我们会完全100％清楚一件事：我就是讨厌链表。恨之入骨。链表是可怕的数据结构。当然，链表有几个很好的使用案例。

你想做很多大列表的拆分或合并。很多。
你正在做一些很棒的无锁并发的事情。
你在写一个内核/嵌入式的东西，想使用一个侵入式列表。
你正在使用纯函数式语言，有限的语义和不能修改东西使得链表比较好用。
......还有更多!

但所有这些情况对于任何编写Rust程序的人来说都是超级罕见的。99%的时间你应该只使用Vec（数组栈），另外1%的时间你应该使用VecDeque（数组双端队列）。由于较少的内存分配频率、较低的内存开销、真正的随机访问和缓存定位，这些对于大多数工作负载来说都是公然优越的数据结构。

链表和Trie一样是小众而模糊的数据结构。很少有人会反驳我说Trie是一种小众结构，你们平均水平程序员在整个生产生涯中很可能永远也不用学会--然而链表却有一些奇怪的名人地位。我们教每个本科生如何写一个链表。这是唯一的小众集合 I couldn't kill from std::collections。它是 the list in C++!

作为一个社区，我们都应该对链表作为"标准"数据结构说不。它是一个很好的数据结构，有几个很好的用例，但这些用例是特殊的，而不是常见的。

有几个人显然读了这个PSA的第一段，然后就不读了。比如，他们会试图通过列举我的伟大用例列表中的一件事来反驳我的论点。就在第一段之后的那件事!

为了让我可以直接链接到详细的论点，下面是我看到的几种反驳的尝试，以及我对它们的回应。如果你只是想学习一些Rust，欢迎跳到第一章!

性能并不总是重要的

是的! 也许你的应用程序是I/O瓶颈的，或者相关代码是在一些不重要的冷门的情况下。但这甚至不是一个使用链表的论点。这是一个使用任何东西的论点。为什么要使用链表呢？使用链接的哈希图吧!

如果性能不重要，那么应用数组的自然默认值肯定是可以的。

如果你有一个指针，那么他们会有O(1)的分割-追加-插入-删除

没错! 不过正如Bjarne Stroustrup所指出的，如果获取指针所花费的时间与复制一个数组中所有元素所花费的时间完全相差无几的话，这实际上并不重要（这确实相当快）。

除非你的工作负载是以拆分和合并成本为主要开销，否则其他每个操作由于缓存效应和代码复杂度所需要的惩罚会消除任何理论上的收益。

但是是的，如果你剖析发现你的应用要花大量的时间在拆分和合并上，你可能从链表中获益。

我负担不起摊销

你已经进入了一个相当小众的领域--大多数人都能承受摊销。不过，数组在最坏的情况下也是要摊销的。仅仅因为你使用的是一个数组，并不意味着你有摊销的成本。如果你能预测你要存储多少元素（甚至有一个上限），你就可以预留所有你需要的空间。根据我的经验，能够预测你需要多少元素是很常见的。特别是在Rust中，所有的迭代器都会提供一个size_hint，正是针对这种情况。

那么push和pop将是真正的O(1)操作。而且它们会比链表上的push和pop快得多。你做一个指针偏移，写入字节，然后递增一个整数。不需要使用任何类型的分配器。

这对低延迟来说如何？

但是，是的，如果你不能预测你的负载，那么可以节省在最坏的情况下的延迟!

链表浪费的空间更少

嗯，这很复杂。一个“标准”的数组大小调整策略是增长或缩小，使最多一半的数组为空。这确实浪费了很多空间。特别是在Rust中，我们不会自动收缩集合（如果你只是要把它重新填满，那就太浪费了），所以浪费的空间可能会接近无穷大!

但这是最坏的情况。在最好的情况下，一个数组栈对整个数组只有三个指针的开销。基本上没有开销。

而链表则是无条件的浪费每个元素的空间。一个单链列表浪费一个指针，而一个双链列表则浪费两个指针。与数组不同，相对的浪费与元素的大小成正比。如果你有巨大的元素，这接近于0浪费。如果你有微小的元素（比如说，字节），那么这可能是高达16倍的内存开销（32位上是8倍）!

实际上，这更像是23倍（32位上是11倍），因为会在字节上添加填充，将整个节点的大小对齐到指针上。

这也是假设你的分配器的最佳情况：分配和取消分配节点是在密集地进行的，你不会因为碎片化而损失内存。

但是是的，如果你有巨大的元素，不能预测你的负载，并且有一个像样的分配器，就可以节省内存。

我在<函数式语言>中一直使用链表。

很好! 在函数式语言中使用链表是超级优雅的，因为你可以在没有任何改变的情况下对它们进行操作，可以递归地描述它们，而且由于惰性的魔力，还可以使用无限列表。

具体来说，链表是不错的，因为它们代表了一个迭代，而不需要任何可变的状态。下一步只是访问下一个子列表。

然而需要注意的是，Rust可以在数组上进行模式匹配，并且用slices来谈论子数组 ! 实际上，它在某些方面甚至比函数式链表更有表现力，因为你可以谈论最后一个元素，甚至“ 没有第一和最后两个元素的数组”或其他任何你想要的疯狂的东西。

的确，你不能用分片来构建一个列表。你只能把它们拆开。

为了偷懒，我们改用iterators。这些可以是无限的，你可以像函数式列表一样对它们进行映射、过滤、反转和连接，而且这一切都会同样惰性地完成。这里不奇怪：切片也可以被转换成迭代器。

但是是的，如果你限于不可变的语义，链表可以非常好。

请注意，我并不是说函数式编程一定很弱或不好。然而它从根本上讲是有语义限制的：你基本上只允许谈论事情是怎样的，而不允许谈论它们应该怎样做。这实际上是一个特点，因为它使编译器能够进行大量的怪异变换，并有可能找出最好的方法来做事情，而不用你担心。然而这是以能够担心为代价的。通常有逃生舱口，但在某些限制下，你又只是在写过程式代码。

即使是在函数式语言中，当你真正需要数据结构时，你也应该努力为任务使用合适的数据结构。是的，单链表是你控制数据流的主要工具，但它们对于实际存储一堆数据和查询数据来说是一种非常糟糕的方式。