作者经常被问及，如何在Rust中实现链表。这个问题不是几句话就能说清楚的，作者写了这本书来回答这个问题。本书通过实现6个链表来教大家如何进行Rust编程，内容包括：

    • 指针类型：&、&mut、Box、Rc、Arc、_const、_mut
    • 所有权、借用、继承的可变性（inherited mutability）、内生的可变性（interior mutability）、复制
    • 所有关键字：struct、enum、fn、pub、impl、use等
    • 测试
    • 不安全的rust

    链表很难写，需要上述那么多概念才可以搞定。

    • 阅读和理解编译器错误消息，对提升编程能力很重要
    • 链表和字典树（trie）一样，是比较小众（niche）、模糊（vague）的数据结构。链表有很多伟大的使用案例，但rust编程中，99%的场合应该使用Vec(数组栈），剩下1%的场合应该使用VecDeque（数组双队列，array deque）。对多数工作负载来说，这两种数据结构更合适，因为更少的内存分配、更低的内存开销、真正的随机访问，以及缓存局部性（cache locality）。
    • 以下是应该使用链表的原因，以及作者的反驳（不应该使用链表的原因）
      • 性能问题：为了解决性能问题，应该使用链表？错！应该使用链接的哈希表（linked hash map）。如果性能不是问题，则通常应该使用数组。
      • 对切分-添加-插入-移除操作，链表有O(1)性能：除非工作负载真的有很多切分、合并开销，通常情况下，其他为克服缓存效果的操作（other operation takes due to caching effects），以及增加的代码复杂性会抹平使用链表得到的好处。
      • 开销（amortization）问题：通常可以预测需要多少个元素，预先分配所需内存空间就可以了。这样，数组的push、pop是真正的O(1)操作，通常还比链表的push、pop操作要快。
      • 链表占用空间更少？
        • 标准的数组调整策略会增加、减小数组大小，最多只有一半的空间是空的。这当然浪费了大量空间。特别是在Rust中，通常不会自动减小数组空间。
        • 但这些都只是最坏的情况。最好的情况下，整个数组的额外开销只是三个指针，几乎是没有开销。
        • 而链表中，每个元素都有额外的内存开销。单链表中，每个元素浪费一个指针的空间；双链表中，每个元素浪费两个指针的空间。相对浪费程度与元素大小相关：元素个头大时，浪费度趋近于零；元素很小时（如单个字节），则额外空间开销是16倍（64位系统，32位系统中是8倍）。考虑到内存对齐，实际的额外空间开销更可能是23倍（32位系统中是11倍）。这还是最好的情况。
      • 函数式语言中总是使用链表？
        • 函数式语言中的链表很优雅
          • 可以不可变地进行操作
          • 可以递归地描述
          • 可以处理无限大的链表：惰性求值
          • 可以处理迭代，而不需要可变状态：下一步就是访问下一个子链表
        • Rust也很不错
          • 可以用切片描述子数组
          • 可以用模式匹配处理数组，甚至比函数式语言中的链表更有表达力：可以表示数组的最后一个元素、去掉第一个和最后两个元素的数组等。
          • 对惰性求值，Rust有迭代器：可以是无限的，可以映射、过滤、颠倒、串接。切片可以用作迭代器。
        • 基础语义的不同
          • 函数式语言只能让你描述事情应该是怎样的，而不能描述怎样变成预期的样子：编译器帮你做了很多事，编译器知道做事的最佳方式。通常这很好，但是在有些限制下，你还是要写过程式代码。
          • 函数式语言中，真需要数据结构时，还是得选择最合适的数据结构。单链表是处理控制流的主要工具，但却不是存储、查询大量数据的最佳方式。
      • 链表适合构建并发数据结构？
        • 写并发的数据结构很难，并不是很多人想象的那样。真开始写了，你会使用MPSC队列或者其他东西。
      • 内核使用了链表
        • 内核是小众玩的东西，一般人玩不了。
      • 无关的插入/移除操作不会更新迭代器
        • 这个问题，通常表示你的控制流、所有权模式可能太复杂。