前言#
我之前在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)。
基本上都是我们之前学过的基础知识，有些特别基础的知识，比如介绍所有权的，我这里只说一些没有说过的，因为太基础了，就不多说了。
大体学习流程#
关于为什么不建议使用链表#
这里就不多说了，写文章的老哥看样子是极其的厌恶链表，教程的介绍中大部分都是对链表的探讨，我们这里就不多说了，因为我们的目的是学习，感兴趣的老哥可以自行去看：作者的“左右互搏”
搭建环境#
直接随便新建一个文件夹，然后cargo new linked_lists_study --lib即可，当然，也不一定要用lib，不是必须的，只是为了方便后面使用miri而已，我们也可以用自带的test。
一个坏的单链栈#
我们现在src下创建一个first.rs文件，然后在src/lib.rs中引入
数据结构的基础设计#
在开始实现之前，我们要先设计下我们的数据结构，它应该是一块块存放在堆上的（搞内核的老哥请左转hush, kernel people!）相互指向的序列数据。
函数式编程的老哥一般会给出下面这种数据结构：
List a = Empty | Elem a (List a)也就是要么是指向空的，要么是指向一个链表，基于递归的思想。
一个数据存在多个类型的可能，表达一个sum type，在rust中这种观念具现则是枚举类型enum。
我们来调整下：
pub enum List {
Empty,
Elem(i32, List)
}当然，这样是过不去编译的，因为鬼知道你可以递归到哪里去，编译器压根不知道你需要多大的堆内存，说不定可以把系统内存都干爆，简单地说就是不满足Sized，所以直接给你卡住了。
那咋整呢？
用Box啊，根据我们之前学到的知识：Box可以让分配器分配一个堆内存空间并返回这个内存的指针，这样就从一整块内存空间变成一块块有关联的固定空间，因为Box<List>只是一个指向内存地址的指针，大小是固定的。
所以我们的代码调整为：
pub enum List {
Empty,
Elem(i32, Box<List>),
}但是这个结构不太好，我们简单的分析下：
[] = Stack
() = Heap
[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)
第一个因为存在的是i32的值和一个指针，所以直接被分配到栈上面去了，而后面的元素都是使用的Box<T>，所以被分配到堆上面去了，有点尴尬。
不过这个不是大问题，我们写代码的时候第一个也给它Box<T>一下即可。
最大的问题其实是这里的junk，这个在吃空间！
我们可以将结构调整为：
[ptr] -> (Elem A, ptr) -> (Elem B, *null*)这样就不会吃额外空间了。
但是！这种场景更差，为什么呢？因为我们的Empty没有分配到空间，这不会对链表的增(push)减(pop)有多大影响，但是它会对切割(splitting)和合并(merging)链表有大的影响。
比如我们可以把上面两种结构的链表切割成下面这俩：
layout 1:
[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)
split off C:
[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)
和
layout 2:
[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)
split off C:
[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)
layout2将B的指针和后面的C切割出来，并没有造成额外的空间。
（ layout1就不说了，直接多了俩junk，坏！）。
合并的情况也一样。
链表的其中一个优点是那你可以给一个元素构造一个节点，这个节点的空间位置是固定下来的，不管你是合并还是切割啥的，只需要改动指针，非常舒服。
另外还有一点就是每个节点有俩状态：“我是节点” 和 “我不是节点”，搞得像量子坍缩啥的。而且不是节点这货也在吃内存空间！
额外话题（不包含优化的情况）：rust中可以在编译阶段给枚举类型分配空间，你可能觉得很神奇，枚举类型不只有一个变体，为什么可以确定呢？其实这里很简单，简单的说直接找吃内存最大那个变体，按它的大小来分配每一个变体存在的地方，因为变体是Sized的。当然，还会加上一些其它的空间用来对齐之类的。比如enum MyEnum { VariantA(i32), VariantB(f64) }，VariantB(f64)吃的最多，那这个枚举需要的空间就固定为B需要的空间
所以如果这是个Empty，那它也得吃一个List的空间。
其实“是不是”节点也可以变成“有没有”
那么在rust中我们一般怎么表示有和没有呢？
自然就是Some和None。没有自然就不吃空间了。
不过我们现在先不用Option<T>，因为我们要搞的是一个**“坏”**的单链堆栈。
扯远了，回到我们的重点：我们要怎么调整我们的结构呢?
为了保证不存在junk，我们可以尝试下面这种：
pub enum List {
Empty,
ElemThenEmpty(i32),
ElemThenNotEmpty(i32, Box<List>),
}其中ElemThenEmpty就是上面的B和C。
看着貌似挺好，但是！这种结构挺蠢的，做个比喻就是：你写业务代码的时候发现需要用多一个状态用来控制其它状态, 然后你又加了一个状态！这种无疑就是屎山行为，逻辑复杂度直接上了一个台阶！
还有一个问题就是依旧存在ElemThenNotEmpty(0, Box(Empty))的场景，这就导致内存分配不均匀(non-uniformly allocating)
而且这种方式还有一个更大的问题：它浪费了更多的空间！因为我们前面采用的结构是一种空指针优化(null pointer optimization)
我们前面看到的枚举都有一个tag用来表示这个枚举，但是如果是下面这种：
enum Foo {
A,
B(ContainsANonNullPtr),
}这种就有空指针优化，会移除(eliminates)tag需要的空间。如果是遇到枚举变体A，那么编译器执行这段代码遇到的这个枚举就是0空间损耗。但如果遇到B，那就不能了，编译器会分配它的空间，因为它的tag不是一个空指针。
欸？这不是和我们上面说到的编译器分配枚举空间的特性有差异吗？
这其实是一种优化，其实还有挺多类型和枚举是有优化的，这也就是为什么rust中不限定枚举的布局。
这里还有一些比较复杂的布局优化，其中空指针优化是最重要的。
这就意味着像&、&mut、Box、Rc、Arc、Vec还有其它重要的类型在Option<T>中都是无开销的(no overhead)。
回到我们的问题中，我们现在需要同时满足下面几点：
- 移除额外的垃圾空间(
junk) - 均匀空间分配(
uniformly allocate) - 支持空指针优化
如果我们将元素从List中拆分出来呢？
如果我们用一个struct去包裹这个元素呢？
枚举让我们可以定义多种类型，结构体可以让我们一次性包含多个值。
我们来将我们的List分成List和Node两部分。
struct Node {
elem: i32,
next: List,
}
pub enum List {
Empty,
More(Box<Node>),
}现在它满足了我们的要求：
- 没有额外的垃圾空间，为什么呢？之前的结构
ElemThenNotEmpty(i32, Box<List>)意味着它最后一定会有一个奇怪的指针，因为它需要知道是否到达最后，而最后需要empty表示，又因为结构的问题，所以它要搭配一个奇怪的空间，也就是junk。但是现在的结构就不会，node的next指向empty的时候即到尾，没了，不需要奇怪的空间。 - 空间是均匀分配的，都是
node的空间。 - 空指针优化，不多说，看结构。
然而还不能高兴，因为我们这里还有个问题，私有化的问题，Node是没有pub的（因为Link pub了出去，如果Node不pub那就有问题了），所以它并不能在More中存放。
> cargo build
warning: private type `first::Node` in public interface (error E0446)
--> src/first.rs:8:10
|
8 | More(Box<Node>),
| ^^^^^^^^^
|
= note: #[warn(private_in_public)] on by default
= warning: this was previously accepted by the compiler but
is being phased out; it will become a hard error in a future release!
:(（老外特有的喜欢用这个表情）
不过也简单，我们pub下即可，不过基于一些开发理念，比如开发一个库，这种时候我们是不太需要把一些内部的东西暴露出去的，容易污染环境，所以我们可以改成这样：
pub struct List {
head: Link,
}
enum Link {
Empty,
More(Box<Node>),
}
struct Node {
elem: i32,
next: Link,
}这样就可以了。
new方法#
我们得有个构造链表的方法
impl List {
pub fn new() -> Self {
List { head: Link::Empty }
}
}不多说
push方法#
貌似很简单！
pub fn push(&mut self, elem: i32) {
let new_node = Node {
elem: elem,
next: ?????
};
}
等等！这个next要指向啥？？？
当然是之前的链表，即head
impl List {
pub fn push(&mut self, elem: i32) {
let new_node = Node {
elem: elem,
next: self.head,
};
}
}然而。。。。接下来要发生什么相信大家都清楚
> cargo build
error[E0507]: cannot move out of borrowed content
--> src/first.rs:19:19
|
19 | next: self.head,
| ^^^^^^^^^ cannot move out of borrowed content
当head进入♂到next里面时，head的所有权就跑去next里了，这对self来说是不行的，他是&mut self，head丢了就是所有权部分(partially)丢失。
当然，下面这种也是没门的(No dice!)
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: self.head,
});
self.head = Link::More(new_node);
}
和上面一样的错：借你不是给你！（unsafe和印度阿三除外）
当然，还是有办法的，比如mem::replace，类似的还有 swap，是直接操作内存的，所以不会有上述报错
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: mem::replace(&mut self.head, Link::Empty),
});
self.head = Link::More(new_node);
}我们先往里塞了一只”狸猫“，然后再用”太子“换。
PS：作者还搞了个图，笑死：《试图替换》（夺宝奇兵里的印第安琼斯Indiana Jones）
当然，这种写法很变扭，不过目前暂时只能这样。
本来接下来按正常开发库流程，是需要对这个方法做单元测试，但是不太容易验证，所以我们先实现pop，然后搭配来测试舒服一些。
pop方法#
看着貌似也很简单。
实际上除了和push一样的所有权问题之外，还需要考虑边界问题，比如列表是空的呢？
空和非空，实际上可以变成有还是没有，有没有我们自然第一时间想到Option<T>。
所以我们的返回值得用Option<T>包裹，没有直接返回None。
pub fn pop(&mut self) -> Option<i32> {
match self.head {
Link::Empty => {
None
}
Link::More(node) => {
// TODO
}
};
unimplemented!()
}
unimplemented!这个宏是用来表示当前函数还在TODO过程，这样IDE就不会给出报错了，当然运行的时候还是会报错
代码也是相当简单，来看下：
#[macro_export]
#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "unimplemented_macro")]
#[allow_internal_unstable(core_panic)]
macro_rules! unimplemented {
() => {
$crate::panicking::panic("not implemented")
};
($($arg:tt)+) => {
$crate::panic!("not implemented: {}", $crate::format_args!($($arg)+))
};
}展开成一个panic（另外说下，panic算是一种diverging function，简单的说就是永远不会返回东西的玩意儿）。
然后我们来实现链表不为空的时候，我们要把head拿出来，然后用下个node作为head。
pub fn pop(&mut self) -> Option<i32> {
let result;
match &self.head {
Link::Empty => {
None
}
Link::More(node) => {
self.head = node.next;
Some(node.elem)
}
};
}
注意这里我们将match self.head改成了match &self.head，因为我们是借用。
不过我们还是遇到了那个问题
> cargo build
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0507]: cannot move out of borrowed content
--> src/first.rs:35:29
|
35 | self.head = node.next;
| ^^^^^^^^^ cannot move out of borrowed content我们是借用，所以不能直接把node.next拿出来。
作者在这还搞了个颜文字，笑死：
head
desk
以头抢桌尔！
那还是老样子，先拿出来，再还回去
pub fn pop(&mut self) -> Option<i32> {
let result;
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => None,
Link::More(node) => {
self.head = node.next;
Some(node.elem)
}
};
}也是很变扭
Ok，接下来我们来测试
单元测试#
rust中写测试用例还是很舒服的
直接在first.rs文件中添加
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop(), None);
// Populate list
list.push(1);
list.push(2);
list.push(3);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);
}
}
我们前面在lib.rs中添加的first.rs就是一个mod，所以它里面还要写子模块的话就需要使用mod关键字包裹。
注意别忘了use super::List;，因为模块之间天然是不相通的，当然，你觉得麻烦可以直接use super::*。
> cargo test
warning: unused import: `super::List`
--> src/first.rs:45:9
|
45 | use super::List;
| ^^^^^^^^^^^
|
= note: #[warn(unused_imports)] on by default
Finished dev [unoptimized + debuginfo] target(s) in 0.43s
Running /Users/ABeingessner/dev/lists/target/debug/deps/lists-86544f1d97438f1f
running 1 test
test first::test::basics ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
; 0 filtered out
这里有个wanring，提示我们unused import。
实际上我们用到了，这其实是我们没有通知编译器这是个测试模块，所以我们需要在mod头上加上#[cfg(test)]。
drop#
我们在rust中一般不需要手动去实现[drop](Drop in std::ops - Rust (rust-lang.org))。然而在链表中，我们需要，比如下面这样的链表：
list -> A -> B -> C每个节点的引用都只有它前面那个节点，如果list也就是头没有引用被drop了，那么A也没有引用也被drop了，以此类推，以递归的方式drop下去，直接把栈干爆了。
所以我们很有必要自行实现drop，不过这里你可能会想，这种应该是[尾调用](Tail call - Wikipedia)吧，不会把栈干爆的。
**课外知识：**简单的介绍下尾调用，一般我们的函数执行过程中如果存在其它函数，那么会先将其它函数执行，确保执行顺序是正确的，这种数据结构自然是栈最合适，后进先出。遇到新的函数就将它压入栈中，当不再依赖这个函数的时候，这个函数就没有用了，自然就出栈。而尾调用则是一种特殊的变体：如果入栈的函数（简称为子函数）是作为依赖于它的那个函数（简称为父函数）的返回值，那么这就意味着此时父函数其实已经执行完了。那么就没必要把父函数保留在栈内，直接保留子函数即可。这么做这个栈的空间也就没有变大，所以也就不会溢出。
比如：
function f() {
let m = 1;
let n = 2;
return g(m + n);
}
f();
// 等同于
function f() {
return g(3);
}
f();
// 等同于
g(3);执行到g(3)的时候有没有f已经没差了。
不过有一点要注意，g(3)必须是最后一步，如果不是，那么就不是尾调用，比如:
function f () {
return g(3) + 1
}g(3)执行完了还有一步 + 1的操作，所以这个时候f是不能出栈的。
ok，就简单的介绍到这里，如果你感兴趣可以直接去看下阮一峰大佬的博客（也是一个面试考点哦！）：尾调用优化 - 阮一峰的网络日志 (ruanyifeng.com)
哦，忘了说了，尾递归也是尾调用，只是调用的函数比较特殊，是自己。
扯得有些远，回归正题。
你可能会想，如果是尾调用那不就没事？
然而并不是，我们来 模拟编译器给我们实现的drop。
impl Drop for List {
fn drop(&mut self) {
// NOTE: you can't actually explicitly call `drop` in real Rust code;
// we're pretending to be the compiler!
self.head.drop(); // tail recursive - good!
}
}
impl Drop for Link {
fn drop(&mut self) {
match *self {
Link::Empty => {} // Done!
Link::More(ref mut boxed_node) => {
boxed_node.drop(); // tail recursive - good!
}
}
}
}
impl Drop for Box<Node> {
fn drop(&mut self) {
self.ptr.drop(); // uh oh, not tail recursive!
deallocate(self.ptr);
}
}
impl Drop for Node {
fn drop(&mut self) {
self.next.drop();
}
}
在我们deallocating也就是手动释放内存之后，我们是没有办法去drop这个Box里的内容的，所以也就没有办法做所谓的尾递归优化。不过我们可以采用迭代的方式去drop，一样的效果，只是“逼格”没那么高。
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, Link::Empty);
// `while let` == "do this thing until this pattern doesn't match"
while let Link::More(mut boxed_node) = cur_link {
cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
// boxed_node goes out of scope and gets dropped here;
// but its Node's `next` field has been set to Link::Empty
// so no unbounded recursion occurs.
}
}
}我们并没有基于pop，因为pop的行为会影响到value，我们当前仅操作于Box，一个指针，这也算是链表的一个好处，如果我们放在数组中，并且元素的值非常大，那么数据操作就是非常昂贵的事情。
代码整合#
#![allow(unused)]
fn main() {
use std::mem;
pub struct List {
head: Link,
}
enum Link {
Empty,
More(Box<Node>),
}
struct Node {
elem: i32,
next: Link,
}
impl List {
pub fn new() -> Self {
List { head: Link::Empty }
}
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: mem::replace(&mut self.head, Link::Empty),
});
self.head = Link::More(new_node);
}
pub fn pop(&mut self) -> Option<i32> {
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => None,
Link::More(node) => {
self.head = node.next;
Some(node.elem)
}
}
}
}
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, Link::Empty);
while let Link::More(mut boxed_node) = cur_link {
cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
}
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop(), None);
// Populate list
list.push(1);
list.push(2);
list.push(3);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);
}
}
}
总结#
这个链表目前还有一定的问题，接下来我们来优化下。