前言

我之前在timsort那块说过用rust来刷算法是不合适的，但我自己刷了几十道题之后发现其实只是部分场景不适合，比如今天要说的：链表。这货因为自身的特性和所有权是冲突的，所以导致我们不得不写一大堆unsafe代码来解决冲突。

所以我们今天来跟着Learning Rust With Entirely Too Many Linked Lists这个教程一步一步的从零开始学习如何在rust中实现一个链表。

然后我发现了这个：

关于本书 - Rust语言圣经(Rust Course)，翻译的很好！（但是省略了一些内容，当然并不影响学习）

实际上这篇文章包含了很多我所不理解的知识，导致很多地方看不懂。。。强力建议看原文

为什么要费大力气在rust中实现链表

其实我们绝大多数情况下不一定是需要使用链表的，一般可以用其它数据结构来替代。

之所以写这篇文章，主要是里面涉及到的点很多，比如智能指针，原始指针这些，都是我们不熟悉但是得用到的，而链表的实现就需要借助于这些。

前提

在开始学之前，我们需要具备以下的基本知识了解：

• &、&mut、Box、Rc、Arc、*const、*mut、NonNull(?)这些指针类型
• 所有权，借用，遗传可变性(inherited mutability)，内部可变性(interior mutability)以及Copy
• 所有关键字
• 模式匹配，泛型以及析构器(destructors)
• 基于[miri](GitHub - rust-lang/miri: An interpreter for Rust's mid-level intermediate representation)来测试
• unsafe，原始指针(raw pointer)，别名(aliasing)，堆叠式借用(stacked borrows)，UnsafeCell，变体(variance)。

基本上都是我们之前学过的基础知识，有些特别基础的知识，比如介绍所有权的，我这里只说一些没有说过的，因为太基础了，就不多说了。

大体学习流程

1. 实现一个错误的单链栈
2. 实现一个正确的单链栈
3. 持久单链栈
4. 一个错误但是安全的双链队列
5. 一个不安全的单链队列
6. TODO：一个不安全的双链队列
7. 其它让人难顶的链表

关于为什么不建议使用链表

这里就不多说了，写文章的老哥看样子是极其的厌恶链表，教程的介绍中大部分都是对链表的探讨，我们这里就不多说了，因为我们的目的是学习，感兴趣的老哥可以自行去看：作者的“左右互搏”

搭建环境

直接随便新建一个文件夹，然后cargo new linked_lists_study --lib即可，当然，也不一定要用lib，不是必须的，只是为了方便后面使用miri而已，我们也可以用自带的test。

一个坏的单链栈

我们现在src下创建一个first.rs文件，然后在src/lib.rs中引入

数据结构的基础设计

在开始实现之前，我们要先设计下我们的数据结构，它应该是一块块存放在堆上的（搞内核的老哥请左转hush, kernel people!）相互指向的序列数据。

函数式编程的老哥一般会给出下面这种数据结构：

也就是要么是指向空的，要么是指向一个链表，基于递归的思想。

一个数据存在多个类型的可能，表达一个sum type，在rust中这种观念具现则是枚举类型enum。

我们来调整下：

当然，这样是过不去编译的，因为鬼知道你可以递归到哪里去，编译器压根不知道你需要多大的堆内存，说不定可以把系统内存都干爆，简单地说就是不满足Sized，所以直接给你卡住了。

那咋整呢？

用Box啊，根据我们之前学到的知识：Box可以让分配器分配一个堆内存空间并返回这个内存的指针，这样就从一整块内存空间变成一块块有关联的固定空间，因为Box<List>只是一个指向内存地址的指针，大小是固定的。

所以我们的代码调整为：

但是这个结构不太好，我们简单的分析下：

第一个因为存在的是i32的值和一个指针，所以直接被分配到栈上面去了，而后面的元素都是使用的Box<T>，所以被分配到堆上面去了，有点尴尬。

不过这个不是大问题，我们写代码的时候第一个也给它Box<T>一下即可。

最大的问题其实是这里的junk，这个在吃空间！

我们可以将结构调整为：

这样就不会吃额外空间了。

但是！这种场景更差，为什么呢？因为我们的Empty没有分配到空间，这不会对链表的增(push)减(pop)有多大影响，但是它会对切割(splitting)和合并(merging)链表有大的影响。

比如我们可以把上面两种结构的链表切割成下面这俩：

和

layout2将B的指针和后面的C切割出来，并没有造成额外的空间。

（ layout1就不说了，直接多了俩junk，坏！）。

合并的情况也一样。

链表的其中一个优点是那你可以给一个元素构造一个节点，这个节点的空间位置是固定下来的，不管你是合并还是切割啥的，只需要改动指针，非常舒服。

另外还有一点就是每个节点有俩状态：“我是节点” 和 “我不是节点”，搞得像量子坍缩啥的。而且不是节点这货也在吃内存空间！

额外话题（不包含优化的情况）：rust中可以在编译阶段给枚举类型分配空间，你可能觉得很神奇，枚举类型不只有一个变体，为什么可以确定呢？其实这里很简单，简单的说直接找吃内存最大那个变体，按它的大小来分配每一个变体存在的地方，因为变体是Sized的。当然，还会加上一些其它的空间用来对齐之类的。比如enum MyEnum { VariantA(i32), VariantB(f64) }，VariantB(f64)吃的最多，那这个枚举需要的空间就固定为B需要的空间

所以如果这是个Empty，那它也得吃一个List的空间。

其实“是不是”节点也可以变成“有没有”

那么在rust中我们一般怎么表示有和没有呢？

自然就是Some和None。没有自然就不吃空间了。

不过我们现在先不用Option<T>，因为我们要搞的是一个**“坏”**的单链堆栈。

扯远了，回到我们的重点：我们要怎么调整我们的结构呢?

为了保证不存在junk，我们可以尝试下面这种：

其中ElemThenEmpty就是上面的B和C。

看着貌似挺好，但是！这种结构挺蠢的，做个比喻就是：你写业务代码的时候发现需要用多一个状态用来控制其它状态, 然后你又加了一个状态！这种无疑就是屎山行为，逻辑复杂度直接上了一个台阶！

还有一个问题就是依旧存在ElemThenNotEmpty(0, Box(Empty))的场景，这就导致内存分配不均匀(non-uniformly allocating)

而且这种方式还有一个更大的问题：它浪费了更多的空间！因为我们前面采用的结构是一种空指针优化(null pointer optimization)

我们前面看到的枚举都有一个tag用来表示这个枚举，但是如果是下面这种：

这种就有空指针优化，会移除(eliminates)tag需要的空间。如果是遇到枚举变体A，那么编译器执行这段代码遇到的这个枚举就是0空间损耗。但如果遇到B，那就不能了，编译器会分配它的空间，因为它的tag不是一个空指针。

欸？这不是和我们上面说到的编译器分配枚举空间的特性有差异吗？

这其实是一种优化，其实还有挺多类型和枚举是有优化的，这也就是为什么rust中不限定枚举的布局。

这里还有一些比较复杂的布局优化，其中空指针优化是最重要的。

这就意味着像&、&mut、Box、Rc、Arc、Vec还有其它重要的类型在Option<T>中都是无开销的(no overhead)。

回到我们的问题中，我们现在需要同时满足下面几点：

1. 移除额外的垃圾空间(junk)
2. 均匀空间分配(uniformly allocate)
3. 支持空指针优化

如果我们将元素从List中拆分出来呢？

如果我们用一个struct去包裹这个元素呢？

枚举让我们可以定义多种类型，结构体可以让我们一次性包含多个值。

我们来将我们的List分成List和Node两部分。

现在它满足了我们的要求：

1. 没有额外的垃圾空间，为什么呢？之前的结构ElemThenNotEmpty(i32, Box<List>)意味着它最后一定会有一个奇怪的指针，因为它需要知道是否到达最后，而最后需要empty表示，又因为结构的问题，所以它要搭配一个奇怪的空间，也就是junk。但是现在的结构就不会，node的next指向empty的时候即到尾，没了，不需要奇怪的空间。
2. 空间是均匀分配的，都是node的空间。
3. 空指针优化，不多说，看结构。

然而还不能高兴，因为我们这里还有个问题，私有化的问题，Node是没有pub的（因为Link pub了出去，如果Node不pub那就有问题了），所以它并不能在More中存放。

:(（老外特有的喜欢用这个表情）

不过也简单，我们pub下即可，不过基于一些开发理念，比如开发一个库，这种时候我们是不太需要把一些内部的东西暴露出去的，容易污染环境，所以我们可以改成这样：

这样就可以了。

new方法

我们得有个构造链表的方法

不多说

push方法

貌似很简单！

等等！这个next要指向啥？？？

当然是之前的链表，即head

然而。。。。接下来要发生什么相信大家都清楚

当head进入♂到next里面时，head的所有权就跑去next里了，这对self来说是不行的，他是&mut self，head丢了就是所有权部分(partially)丢失。

当然，下面这种也是没门的(No dice!)

和上面一样的错：借你不是给你！（unsafe和印度阿三除外）

当然，还是有办法的，比如mem::replace，类似的还有 swap，是直接操作内存的，所以不会有上述报错

我们先往里塞了一只”狸猫“，然后再用”太子“换。

PS：作者还搞了个图，笑死：《试图替换》（夺宝奇兵里的印第安琼斯Indiana Jones）

当然，这种写法很变扭，不过目前暂时只能这样。

本来接下来按正常开发库流程，是需要对这个方法做单元测试，但是不太容易验证，所以我们先实现pop，然后搭配来测试舒服一些。

pop方法

看着貌似也很简单。

实际上除了和push一样的所有权问题之外，还需要考虑边界问题，比如列表是空的呢？

空和非空，实际上可以变成有还是没有，有没有我们自然第一时间想到Option<T>。

所以我们的返回值得用Option<T>包裹，没有直接返回None。

unimplemented!这个宏是用来表示当前函数还在TODO过程，这样IDE就不会给出报错了，当然运行的时候还是会报错

代码也是相当简单，来看下：

展开成一个panic（另外说下，panic算是一种diverging function，简单的说就是永远不会返回东西的玩意儿）。

然后我们来实现链表不为空的时候，我们要把head拿出来，然后用下个node作为head。

注意这里我们将match self.head改成了match &self.head，因为我们是借用。

不过我们还是遇到了那个问题

我们是借用，所以不能直接把node.next拿出来。

作者在这还搞了个颜文字，笑死：

head

desk

以头抢桌尔！

那还是老样子，先拿出来，再还回去

也是很变扭

Ok，接下来我们来测试

单元测试

rust中写测试用例还是很舒服的

直接在first.rs文件中添加

我们前面在lib.rs中添加的first.rs就是一个mod，所以它里面还要写子模块的话就需要使用mod关键字包裹。

注意别忘了use super::List;，因为模块之间天然是不相通的，当然，你觉得麻烦可以直接use super::*。

这里有个wanring，提示我们unused import。

实际上我们用到了，这其实是我们没有通知编译器这是个测试模块，所以我们需要在mod头上加上#[cfg(test)]。

drop

我们在rust中一般不需要手动去实现[drop](Drop in std::ops - Rust (rust-lang.org))。然而在链表中，我们需要，比如下面这样的链表：

每个节点的引用都只有它前面那个节点，如果list也就是头没有引用被drop了，那么A也没有引用也被drop了，以此类推，以递归的方式drop下去，直接把栈干爆了。

所以我们很有必要自行实现drop，不过这里你可能会想，这种应该是[尾调用](Tail call - Wikipedia)吧，不会把栈干爆的。

**课外知识：**简单的介绍下尾调用，一般我们的函数执行过程中如果存在其它函数，那么会先将其它函数执行，确保执行顺序是正确的，这种数据结构自然是栈最合适，后进先出。遇到新的函数就将它压入栈中，当不再依赖这个函数的时候，这个函数就没有用了，自然就出栈。而尾调用则是一种特殊的变体：如果入栈的函数（简称为子函数）是作为依赖于它的那个函数（简称为父函数）的返回值，那么这就意味着此时父函数其实已经执行完了。那么就没必要把父函数保留在栈内，直接保留子函数即可。这么做这个栈的空间也就没有变大，所以也就不会溢出。

比如：

执行到g(3)的时候有没有f已经没差了。

不过有一点要注意，g(3)必须是最后一步，如果不是，那么就不是尾调用，比如:

g(3)执行完了还有一步 + 1的操作，所以这个时候f是不能出栈的。

ok，就简单的介绍到这里，如果你感兴趣可以直接去看下阮一峰大佬的博客（也是一个面试考点哦！）：尾调用优化 - 阮一峰的网络日志 (ruanyifeng.com)

哦，忘了说了，尾递归也是尾调用，只是调用的函数比较特殊，是自己。

扯得有些远，回归正题。

你可能会想，如果是尾调用那不就没事？

然而并不是，我们来 模拟编译器给我们实现的drop。

在我们deallocating也就是手动释放内存之后，我们是没有办法去drop这个Box里的内容的，所以也就没有办法做所谓的尾递归优化。不过我们可以采用迭代的方式去drop，一样的效果，只是“逼格”没那么高。

我们并没有基于pop，因为pop的行为会影响到value，我们当前仅操作于Box，一个指针，这也算是链表的一个好处，如果我们放在数组中，并且元素的值非常大，那么数据操作就是非常昂贵的事情。

代码整合

总结

这个链表目前还有一定的问题，接下来我们来优化下。