有什么问题吗，或者想立刻查看所有最终代码？一切'；在Github上！
注：本书的最新版本是针对Rust 2018编写的，该版本首次与rustc 1.31一起发布（2018年12月8日）。如果你的铁锈工具链足够新，货物。cargo new创建的toml文件应该包含Line edition="；2018" （或者如果你'；在遥远的未来重读这篇文章，也许会有更多的人！）。使用一个旧的工具链是可能的，但是解锁一个秘密的硬模式，在那里你会得到额外的编译器错误，这些错误在本书的正文中完全没有提到。哇，听起来很有趣！
我经常被问到如何在Rust中实现链表。答案实际上取决于你的要求是什么，它'；很明显，当场回答这个问题并不容易。因此我'；I’我决定写这本书是为了一劳永逸地全面回答这个问题。
在本系列中，我将通过让您实现6个链表来教您基本和高级的Rust编程。这样做，你应该学会：
是的，链表真的很糟糕，以至于你要处理所有这些概念，把它们变成现实。
一切'；侧边栏中的s（在移动设备上可能会折叠），但为了快速参考，这里'；这就是我们'；我们要做的是：
就这样我们'；我们都是同一页，我'；我会把输入终端的所有命令都写出来。我'；我们还将使用锈#39；s标准包装经理Cargo负责开发该项目。货物不是'；没有必要编写一个Rust程序，但它'；这比直接使用rustc要好得多。如果你只是想玩，你也可以通过play在浏览器中运行一些简单的程序。rust-lang.org。
在后面的章节中，我们'；将使用"；生锈"；安装额外的防锈工具。我强烈建议您使用Rustop安装所有防锈工具链。
我们'；我会把每一份清单放在一个单独的文件里，这样我们就不会'；不要丢掉我们的工作。
需要注意的是，真正的生锈学习体验包括编写代码、让编译器对你大喊大叫，以及试图弄清楚这到底意味着什么。我将认真确保这种情况尽可能频繁地发生。学习阅读和理解锈迹'；对于一个高效的程序员来说，优秀的编译器错误和文档非常重要。
尽管事实上'；这是谎言。在写这篇文章时，我遇到了比我所展示的更多的编译器错误。尤其是在后面的章节中，我赢得了'；展示了很多随机的#34；我打字（复印粘贴）不好"；你可能会在每种语言中遇到的错误。这是一个有导游带领的旅行，让公司向我们尖叫。
我们'；我们会走得很慢，而我'；老实说，我不会一直非常认真。我觉得编程应该很有趣，该死！如果你'；你是那种想要信息密度最大化、内容严肃正式的人，这本书不适合你。我不会为你做任何事。你错了。
就这样我们'；你完全清楚：我讨厌链表。带着激情。链表是糟糕的数据结构。现在当然有了'；S链接列表的几个重要用例：
你需要对大列表进行大量拆分或合并。很多
你'；重新使用纯函数式语言，以及有限的语义和不存在变异，使得链表更容易使用。
但所有这些情况对于编写Rust程序的人来说都是极为罕见的。99%的时间你应该只使用Vec（数组堆栈），99%的时间你应该使用VecDeque（数组堆栈）。由于分配频率较低、内存开销较低、真正的随机访问和缓存局部性，这些数据结构对于大多数工作负载来说都是明显的优越数据结构。
链表和trie一样，在数据结构中是小众和模糊的。几乎没有人会因为我声称trie是一个小众结构而感到不安，你的普通程序在整个富有成效的职业生涯中都不会愉快地学习到这一点——但链接列表却有一些奇怪的名人身份。我们教每一个本科生如何写一份清单。它'；这是我唯一看不到的利基系列'；从std:：collections中杀人。它'；是C++中的列表！
作为一个社区，我们所有人都应该拒绝链表作为"；标准"；数据结构。它'；这是一个很好的数据结构，有几个很好的用例，但这些用例都是例外，并不常见。
有几个人显然读了这篇PSA的第一段，然后停止了阅读。就像，字面上他们'；I’我试着通过列出我的优秀用例列表中的一个内容来反驳我的论点。就在第一段之后！
为了让我能直接链接到一个详细的论点，这里有几个我见过的反论点，以及我对它们的回应。如果你只是想学习一些知识，请随意跳过第一章！
对也许您的应用程序是I/O绑定的，或者所讨论的代码是在某种冷情况下不'；没关系。但这不是'；甚至连使用链表的理由都没有。这是一个使用任何东西的论点。为什么要建立一个链表？使用链接的哈希映射！
如果表现不佳'；没关系，那么它'；应用数组的自然错误当然没问题。
是的！尽管正如比亚恩·斯特劳斯鲁普所指出的那样，这并不意味着'；实际上，如果获取指针所需的时间完全超过了在数组中复制所有元素所需的时间（这真的很快），那么我就不在乎了。
除非您的工作负载主要由拆分和合并成本控制，否则由于缓存效果和编解码器复杂性，每一个其他操作都会受到惩罚，这将消除任何理论收益。
但是是的，如果你'；重新分析应用程序以花费大量时间进行拆分和合并，在链表中可能会有所收获。
你'；我已经进入了一个相当小的领域——大多数人都负担得起摊销。不过，阵列在最坏的情况下也会摊销。就因为你'；重复使用anarray，不'；这并不意味着你已经摊销了成本。如果你能预测你有多少人'；如果你要储存（甚至有一个上限），你可以预先预订所有你需要的空间。以我的经验来看'；这是很常见的能够预测多少元素你'；我需要。尤其是铁锈，头韵为这种情况提供了一个大小提示。
然后推送和弹出将是真正的O（1）操作。他们'；我们将比链表上的推送和弹出要快得多。执行pointeroffset，写入字节，然后递增一个整数。不需要去找任何分配者。
但是是的，如果你能'；Don’不要预测你的工作量，最糟糕的情况是节省时间！
这很复杂。A"；标准"；调整数组大小的策略是增大或缩小数组，使其最多有一半为空。这确实是浪费了很多空间。尤其是在生锈的时候，我们不'；t自动缩小收藏（如果你再把它填满，那就是浪费），所以wastagecan接近无穷大！
但这是最坏的情况。在最好的情况下，一个数组堆栈对于整个数组只有三个开销指针。基本上没有开销。
另一方面，链表无条件地浪费每个元素的空间。单链表浪费一个指针，而双链表浪费两个指针。与阵列不同，相对损耗与元素的大小成正比。如果你有巨大的元素，这接近零浪费。如果你有很小的元素（比如字节），那么这可能是16倍的内存开销（32位上是8倍）！
实际上是'；s更像23x（32位上的11x），因为填充将被添加到字节以对齐整个节点'；它的大小是指针的大小。
这也是为您的分配器假设的最佳情况：分配和释放节点是密集进行的，而您'；我们不会因为破碎而失去记忆。
但是是的，如果你有巨大的元素，可以'；不要预测你的负载，并有一个合适的分配器，有节省内存！
太棒了链表在函数式语言中使用起来非常优雅，因为你可以在不进行任何变异的情况下对它们进行操作，可以递归地描述它们，而且由于懒惰的魔力，它还可以处理无限多的列表。
具体来说，链表很好，因为它们代表了一个迭代，不需要任何可变状态。下一步就是访问下一个子列表。
Rust大多数都使用迭代器来完成这类工作。它们可以是无限的，你可以像一个函数列表一样映射、过滤、反转和连接它们，而这一切都将同样缓慢地完成！
Rust还可以让您轻松谈论带有切片的子阵列。在函数式语言中，通常的头/尾分割只是切片。在_mut（1）处拆分。很长一段时间以来，Rust有一个在芯片上进行模式匹配的实验系统，这个系统非常酷，但是当它稳定下来后，这个特性就被简化了。不过，基本的切片图案还是很整洁的！当然，切片可以变成迭代器！
注意我'；我并不是说函数式编程一定很弱。然而，它在语义上是有限的：you'；我们基本上只被允许谈论事情是怎样的，而不是应该怎样做。这实际上是一个特性，因为它使编译器能够进行大量的Exotic转换，并可能找出最好的方法来完成这些工作，而无需担心。然而，这是以能够担心它为代价的。通常会有逃生舱口，但在一定程度上你'；我们又在写程序代码了。
即使在函数式语言中，当您实际需要数据结构时，也应该努力为工作使用适当的数据结构。是的，单链表是控制流程的主要工具，但它们'；实际上，存储和查询大量数据的方法非常糟糕。
对尽管编写并发数据结构实际上是一个完全不同的东西，而且不是'；这不是一件应该掉以轻心的事情。当然也不是很多人会考虑做的事情。一次'；已经写好了，你'；我们也不是真的选择使用链表。你'；重新选择使用MPSC队列或其他什么。在这种情况下，实施策略相去甚远！
它'；这是一个利基市场。你'；你说的是一种你'；你甚至不用你的语言'；它的运行时间。这不是你'；你在做什么奇怪的事？
那'；这是一支精致的舞蹈，你'；我们在玩。尤其是如果你没有'；我没有垃圾收集器。我可能会说，根据细节，您的控制流和所有者模式可能有点太复杂了。
嗯，是的。你'；重新阅读一本关于这个前提的书。单链表非常简单。双链接列表会变得有点粗糙，就像我们'；我看看。