Rust实现链表（A Bad Singly-Linked Stack）

发表于 2022-09-27 更新于 2022-10-06 分类于编程语言

Learn Rust With Entirely Too Many Linked Lists 是经典的使用Rust实现链表的教程，内容浅入深出，从数据结构到方法实现通过不断试错、思考、纠正，最后得到想要的链表。

学完Rust语法基础之后，通过实现链表数据结构可以巩固知识点，提高Rust实战能力。“Learn Rust With Entirely Too Many Linked Lists” 是经典的使用Rust实现链表的教程，内容浅入深出，从数据结构到方法实现通过不断试错、思考、纠正，最后得到想要的链表。与很多文章不同的是，Too Many Linked List不仅会教读者怎么实现链表，更重要的是一步一步试错和纠正的过程，让读者能深刻的理解为什么这么做。

本节学习第一个链表：A Bad Singly-Linked Stack，主要功能包括：数据结构，Push，Pop，Drop。存储数据暂时以i32类型为例。

一、涉及知识点

枚举、结构体
包和模块
Box智能指针
Null pointer optimizaiton
实现结构体方法
所有权： self、&mut self、&self
模式匹配
流程控制
代码测试
尾递归

二、数据结构设计

2.1 使用枚举结构

一般而言，链表是分配在堆上通过指针索引的一种数据存储方式，一个链表元素要么为空要么为一个节点（由实际值和指向下个节点的指针构成）。

1 2	List a = Empty \| Elem a (List a) "A List is either Empty or an Element followed by a List"

在有null值的程序语言中（c、c#、java等），直接用结构体或者类就能得到一个链表数据结构:

// C语言 定义链表结构体
typedef struct SListNode{
	// 定义一个指向下一个节点地址的指针
	struct SListNode* next;
	// 定义一个存放数据的变量
	ElemType data;
}SListNode;

// c# java 定义链表结构体
private class Node
{
    public E e;         //结点存储的元素
    public Node next;   //下一个结点的引用(指针)
}
private Node head;      //链表中头结点的引用

但是，由于Rust语言没有null值，因此若想用一种类型既能表示null又能表示节点实体最好的办法就是使用枚举结构。很自然地，可以构造出以下数据结构：

// in first.rs

pub enum List{
    Empty,
    Elem(i32,Box<List>), // 这里需要用智能指针不然构成循环引用，Rust编译器将无法推断该结构占用内存大小
}

fn main(){
    let list::List<i32> = List::Elem(1, Box::new(List::Elem(2, Box::new(List::Empty))));
}

2.2 问题：垃圾存储、移动元素效率低

以上数据结构虽然能基本表示链表结构，但是细细琢磨可以发现在实际使用时很不合理。让我们用以下标志表示拥有两个节点的链表：

[] = Stack
() = Heap

[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)

两个问题：

最后表示空的节点，实际上并不应该为一个节点；
其中一个节点不是堆分配。

问题一会产生什么后果呢？答案是会产生垃圾存储，而这一点是由枚举结构的特性所决定：枚举节点的内存大小取决于枚举中占用内存最大的节点。因此，即使为Empty，也需要申请足够的内存大小，以保证能随时转换为Elem。以上尾节点(Empty, *junk*)实质上内存占用与Elem一致。

问题二又有什么问题呢？让我们先来看看以下两种结构的区别：

结构 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*)

结构 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*)

当我们需要分离出节点 C时，结构二只需要将节点B中的指针(ptr)拷贝到栈中，并将原始值置为空即可。而结构一则需要将节点C从堆拷贝至栈中。我们知道，链表的优点之一就是可以通过操纵指针高效地实现数据的再组织，而不用挪动数据本身，结构一反而丢失了这一特性。

2.3 改进结构

为了解决以上两个问题，尝试引入结构体，使用结构体和枚举来表示链表结构:

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

1	[List::More] -> Node(elem A, next ptr) -> Node(elem B, null)

从构建的数据可以看出，该结构不仅解决了尾节点存储垃圾的问题，也解决了节点一会儿堆分配一会儿栈分配的问题。

有好奇宝宝肯定会问，上面不是说Rust语言没有null吗？为什么这里结构体里面存储了null呢？这就涉及到Null Pointer Optimizaiton的知识点了。

枚举空指针优化：

通常的，枚举变量会包含一个用于表明子类型的tag和一块足够存储数据的内存空间。但是，当出现以下结构的枚举时，空指针优化就会发挥作用，若子类型为A，内存中就存为0000 0000，其他情况则为子类型B（因为它包含一个非零指针），不再额外使用tag表示子类型。
1
2
3
4
enum Foo {
	A,
	B(SomeNonNullPointer),
}
关于NPO的更多信息可以参考这里std::option - Rust (rust-lang.org)。

2.4 public or private

当我们尝试编译2.3的链表数据结构时，Rust编译器给出了如下提示：

> 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!

因为List需要暴露出来以供使用所以必须声明为pub，而Node为了隐藏实现默认为private 。那么问题来了，当枚举声明为pub时，其内部子类型必须都是可公开使用的。因此，为了隐藏实现不得不将List定义为结构体类型：

pub struct List{
    head:Link,
}

enum Link{
    Empty,
    More(Box<Node>),
}

struct Node{
    elem:i32,
    next:Link,
}

至此，完成了数据结构设计，代码虽然只有十几行，但是不断优化的过程包含了很多对数据结构和内存分配的思考。

三、链表方法：push、pop

现在，让我们为这个链表添加一些常用方法，首先是最基础的构造方法：

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }
}

由于在增删链表节点时，涉及到对链表结构修改，所以这里需要提前对Rust的所有权系统有基本的了解，Rust中所有权的主要形式有三种：

self - Value

&mut self - mutable reference

&self - shared reference

这里详细说一下 &mut self，特点是你可以对你拥有的可变引用的值做任何你想做的事情，只要你在做完后让它处于有效状态就可以了，但唯一不能做的是**move the value out with no replacement**。

3.1 Push方法

push方法需要向链表中添加节点，由于是模拟栈结构，所以采用头插法：首先新建一个节点，其next指向原链表头节点，然后将新节点赋值为头节点。很自然地得到以下代码：

impl List{
    pub fn push(&mut self,elem:i32){
        let new_node = Box::new(Node{
            elem:elem,
            next:self.head,
        })
        self.head = Link::More(new_node);
    }
}

编译器意料之中地报了错：

> 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

next:self.head尝试将self.head的所有权转移至next，但是编译器很显然不希望我们这么做。因为这会导致当我们完成可变借用归还所有权后，被借用的数据只有部分被初始化了（self.head中的内容没了)。正如我们之前所述，当用于可变借用的所有权时，唯一禁止做的事情是：**move the value out with no replacement!**

因此，我们需要做的就是 move the value out and give it a replacement value. 在Rust标准库中，正好提供了一个这样的方法：std::mem::replace。该函数允许使用者用另一个值替换想要”偷借”出去的值。改正后的代码变为：

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);
}

注意，记得在代码顶部引入 use std::mem;

这里附上replace源码，可以看出，函数通过unsafe实现，并返回一个拥有所有权的变量：

pub const fn replace<T>(dest: &mut T, src: T) -> T {
    // SAFETY: We read from `dest` but directly write `src` into it afterwards,
    // such that the old value is not duplicated. Nothing is dropped and
    // nothing here can panic.
    unsafe {
        let result = ptr::read(dest);
        ptr::write(dest, src);
        result
    }
}

3.2 Pop 方法

pop 方法会弹出链表中的第一个节点并返回节点值。代码逻辑为：判断链表是否为空，若为空返回Option::None；若不为空则替换头节点为其next，并返回原头节点值Some(elem)。

代码实现如下：

pub fn pop(&mut self)->Option<i32>{
    match &self.head{
        Link::Empty=> None,
        Link::More(node)=>{
            self.head = node.next;
            Some(node.elem)
        }
    }
}

尝试编译，再一次被编译器教育：

> 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转移给头节点时，发生了上一节同样的错误。这里不妨回过头仔细想想当pop不为空的链表时，我们本质上是在做哪些操作呢：

移除链表头节点
移除头节点数据elem
替换头节点为其next
返回Some(elem)

问题就出现在移除链表头节点上，当我们使用match &self.head时，匹配到的node是头节点的可变引用，因此无法直接移除。那么，不妨仍然考虑使用replace方法，先将原链表头节点置为空，然后返回得到一个拥有所有权的链表头节点node，这样就可以将其next值赋给self.head作为新的头节点了。

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)
        }
    }
}

至此，完成了push、pop两个常规方法。

四、测试模块

测试代码往往紧随功能代码之后，并通过新的命名空间作为区分，以避免与功能代码冲突。

//in 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);
    }
}

五、实现Drop方法

同C++一样，Rust使用析构函数自动清除不再使用的数据。当一个类型实现了名为 Drop 的trait时，就表示其具有析构函数。

1
2
3

pub trait Drop {
    fn drop(&mut self);
}

当定义的复合类型中的子类型都已实现了Drop时，我们就不用再为复合类型实现Drop了。因此，想要清除链表结构只需调用头节点的drop方法即可。

然而，自动清除的结果并没有预料般那么友好。让我们用下面的例子进行说明：

1	list -> A -> B -> C

当清除list时，会先自动清除A，而在清除A时，会先清除B……，整个过程是一次递归调用。然而，递归调用可能会带来栈溢出的问题，是否会在清除链表是发生呢。从调用逻辑上看，很多人可能会草率地以为“清除链表的递归属于尾递归，不会造成栈溢出”。为了搞清楚到底结果是怎样的，我们不妨手动地为所有结构实现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); // 不是尾递归的原因是在 `drop` 后还有额外的操作
    }
}

impl Drop for Node {
    fn drop(&mut self) {
        self.next.drop();
    }
}

从上面的代码和注释可以看出为 Box<Node> 实现的 drop 方法中，在 self.ptr.drop 后调用的 deallocate 会导致非尾递归的情况发生。

因此我们需要手动为 List 实现 Drop 特征:

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);
            // boxed_node 在这里超出作用域并被 drop,
            // 由于它的 `next` 字段拥有的 `Node` 被设置为 Link::Empty,
            // 因此这里并不会有无边界的递归发生
        }
    }
}

六、最终代码

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);
    }
}

好吧，通过上面的学习我们得到了一个不太优秀的单向链表。keep going~