用rust搞个数据结构--链表1

最近一直在看 rust 相关的内容，之前也用 rust 写了面向对象的课设。但是当时并没有用到太多 rust 的特性来写。比如字符串为了规避生命周期的问题，直接采用了保留所有权的 String 类型等等。

所以为了弥补下上次的缺憾，也是为了加深学习，这次我要用rust来写一个简单的链表。

首先写几个结构体用于实现大致的内存布局。

pub struct Node<T> {
    elem: T,
    next: Option<Box<Node<T>>>,
}

pub struct List<T> {
    head: Option<Box<Node<T>>>,
}

注意这里的 next 字段类型是 Option<Box<Node>>，Box 是 rust 中最常见的智能指针，用来将数据分配到堆内存上，而 Option 则是一个泛型枚举，用于表示可能不存在的数据。

标准库的定义就像这样

pub elem Option<T> { //枚举是 sum type, 所以内容物只能是其定义中包含的类型之一
    Some(T), 
    None, //表示空类型
}

接下来来实现链表的初始化,为了简单考虑，接下来只会考虑实例化为储存 i32 类型的链表。

fn new(elem: i32) -> Self {
    List {
        head: Some(Box::new(Node {
            elem: elem,
            next: None,
        })),
    }
}

然后是最重要的部分，为链表实现添加和删除元素的方法。

单纯的链表可以有很多种增删元素的方式，比如头插、尾插或者指定位置插入，弹出元素也是类似的

push()和 pop()方法，先来看看 push()。

fn push(&mut self, elem: i32) {
    let mut new_node = Box::new(Node{
        elem: elem,
        next: self.head,
    });
    self.head = Some(new_node);
}

理想很丰满，现实很骨感，虽然上面这段代码符合逻辑，但是这过不了编译，运行下 cargo check,来看看编译器在抱怨什么。

Checking chain_table v0.1.0 (/home/ooj2003/VSCodeProjects/rust/chain_table)
error[E0507]: cannot move out of `self.head` which is behind a mutable reference
  --> src/main.rs:33:19
   |
33 |             next: self.head,
   |                   ^^^^^^^^^ move occurs because `self.head` has type `Option<Box<Node<i32>>>`, which does not implement the `Copy` trait
   |
help: consider borrowing the `Option`'s content
   |
33 |             next: self.head.as_ref(),
   |                            +++++++++

For more information about this error, try `rustc --explain E0507`.
error: could not compile `chain_table` due to previous error

不太对劲，我们只是想在所有权的链条中插入一环，但是为什么编译器在抱怨我们没有给Option<Box<Node>> 实现 Copy trait？？？

这里就是 rust 与很多语言并不一致的地方，rust的自定义类型和内建的在堆上分配数据的类型在赋值时并不会发生拷贝（深克隆），而是默认采用了和c++11差不多的移动语义。由于rust的所有权模型还没有聪明到理解我们的行为，它在这种情形下只会笨笨的期望得到一个原链表的拷贝，所以这里我们采用一种偷天换日的方法来实现我们的想法。

fn push(&mut self, elem: i32) {
    let mut new_node = Box::new(Node::new(elem));
    new_node.next = std::mem::replace(&mut self.head, None);
    self.head = Some(new_node);
}

标准库中的 replace() 就是专为这种情形而生的。

以下下是标准库内 replace() 的函数签名。

pub fn replace<T>(dest: &mut T, src: T) -> T

大致意思是其接受一个可变引用，并用 src 去替换并返回其所有物。

在我们的 push() 方法的实现中，我们用 None 替换了头结点的 head字段，并将这个字段的内容转移给了我们新节点的next字段，最后将 new_node 包装在 Option 枚举中并转移给头结点的head字段。

好的，现在 push() 方法能过编译了，接下来来处理 pop()方法

fn pop(&mut self) -> Option<i32> {
        match std::mem::replace(&mut self.head, None) {
            Some(x) => {
                self.head = x.next;
                Some(x.elem)
            }
            None => None,
        }
    }

如果头结点持有的链表为空，就直接返回 None, 不为空时相对复杂些。

用 H 代表头节点，则原先的所有权关系大致如图（箭头代表持有所有权） \[ self :H \rightarrow a \rightarrow b \rightarrow \dots \] 现在我要取出 a 并返回，首先用 mem::replace() 函数将a的持有物置换为 None 并将置换所得绑定到一个新变量 new 上，此时所有权结构如下 \[ self: H, \quad new: a\rightarrow b \rightarrow\dots \] 注意H的类型签名是 List ，a、b等小写字母（表示节点）的类型签名是 Node,

接下来用 Option 包装并返回 a 的 elem 字段内容物，并将 a 的 next 字段内容物的所有权移交给 H ，此时所有权结构如下。 \[ self: H \rightarrow b \rightarrow \dots \] 此时 a 和 new 在完成操作后生命周期结束并自动调用析构函数被销毁。

其实到这里这个简单的链表其实已经做的差不多了，虽然文章标题是链表，但是完全就只是做了个链栈。。。

最后来收尾下整体的析构函数（不是节点的析构函数）。

一般来说， rust 中是不需要自己考虑编写析构函数的。rust 里面除了 unsafe 部分基本上全部的指针都是引用和智能指针，配合默认的移动语义，不特殊考虑的话基本上程序已经自动实现了 RAII ，但是这在处理链表的时候会遇到一些问题。

对于所有基本类型，rust 都已经实现了 Drop trait 即析构函数，自定义的结构体则会在生命周期结束时递归的为每个字段调用 drop 方法。当面对链表时，自动生成的析构函数则会递归的去找到表尾并销毁，然而是表尾前一个元素，然后再前一个，以此类推。

如果这个链表非常的长的话，不出预料的，程序会爆栈，所以我们要手动的为我们的链表实现 Drop trait 。

impl Drop for List {
    fn drop(&mut self) {
        let mut a = std::mem::replace(&mut self.head, None);
        loop {
            match a {
                None => return,
                Some(mut x) => a = std::mem::replace(&mut x.next, None),
            }
        }
    }
}

首先用 replace() 函数将 self 的 head 字段用 None 替换，返回值绑定到变量 a 上，然后对 a 进行模式匹配，如果是 None 则表示链表为空或者已经匹配到表尾的 next 字段。如果不是， 则将匹配项的 next 字段重新绑定到 a 上， 注意这时原先 a 持有的内容物在这一操作后生命周期已经结束，编译器会自动为其调用 drop() 方法。这么一番操作下来，函数调用栈就不会被递归撑爆了。

以下为完整代码。

pub struct Node {
    elem: i32,
    next: Option<Box<Node>>,
}

pub struct List {
    head: Option<Box<Node>>,
}

impl List {
    fn new(elem: i32) -> Self {
        List {
            head: Some(Box::new(Node {
                elem: elem,
                next: None,
            })),
        }
    }

    fn push(&mut self, elem: i32) {
        let mut new_node = Box::new(Node::new(elem));
        new_node.next = std::mem::replace(&mut self.head, None);
        self.head = Some(new_node);
    }

    fn pop(&mut self) -> Option<i32> {
        match std::mem::replace(&mut self.head, None) {
            Some(x) => {
                self.head = x.next;
                Some(x.elem)
            }
            None => None,
        }
    }
}

impl Node {
    fn new(elem: i32) -> Self {
        Node {
            elem: elem,
            next: None,
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut a = std::mem::replace(&mut self.head, None);
        loop {
            match a {
                None => return,
                Some(mut x) => a = std::mem::replace(&mut x.next, None),
            }
        }
    }
}