用rust实现简单的单链表

2022-03-09

作为初学者，在掌握了rust的基本语法和所有权机制，尝试写一下常见数据结构和算法，目标是为了更好的理解rust的所有权机制。受限于个人目前对rust仍处于入门阶段，因此本文代码实现不一定是最合适的，甚至可能存在问题。

今天的目标是用rust实现一个简单的单链表LinkedList，同时为此链表提供从头部插入元素(头插法)、翻转链表、打印链表的功能。

1.链表节点的定义 #

实现链表，首先是实现链表的节点，根据其他编程语言的经验，于是用rust首先写出了下面的链表节点结构体定义:

代码片段1:

1struct Node<T> {
2    data: T,
3    next: Option<Node<T>>, // recursive type `Node` has infinite size
4}

在代码片段1中，定义一个Node结构体，data字段使用了泛型类型T用于链表节点的数据。 next使用了Option枚举，即如果该节点没有下一个节点时，next是可空的，在rust中没有其他编程语言中的空值(null, nil)，而是提供了Option的解决方案，如果该链表节点的下个节点为空，则其next取值为Option::None。

遗憾的是代码片段1是无法编译通过的，报了recursive type ``Node`` has infinite size的编译错误。回顾Rust内存管理的基础知识，Rust需要在编译时知道一个类型占用多少空间，Node结构体内部嵌套了它自己，这样在编译时就无法确认其占用空间大小了。在Rust中当有一个在编译时未知大小的类型，而又想要在需要确切大小的上下文中使用这个类型值的时候，可以使用智能指针Box。将next字段的类型修改为Option<Box<Node<T>>>，这样嵌套的类型为Box，嵌套的Node将会被分配到堆上，next字段在栈上存储的只是智能指针Box的数据(ptr, meta)，这样在编译时就能确定Node类型的大小了。将代码片段1的修改如下:

代码片段2:

1struct Node<T> {
2    data: T,
3    next: Option<Box<Node<T>>>,
4}

修改完成后，可以编译通过了。根据next: Option<Box<Node<T>>>，每个链表节点Node将拥有它下一个节点Node的所有权。

2.链表的定义 #

定义完链表之后，下一步再定义一个结构体LinkedList用来表示链表，将会封装一些链表的基本操作。结构体中只需方一个链表头节点的字段head，类型为Option<Box<Node<T>>>。

代码片段3:

 1/// 单链表节点
 2#[derive(Debug)]
 3struct Node<T> {
 4    data: T,
 5    next: Option<Box<Node<T>>>,
 6}
 7
 8/// 单链表
 9#[derive(Debug)]
10struct LinkedList<T> {
11    head: Option<Box<Node<T>>>,
12}

为了便于使用，再给Node和LinkedList这两个结构体各添加一下关联函数new。

代码片段4:

 1impl<T> Node<T> {
 2    fn new(data: T) -> Self {
 3        Self { data: data, next: None }
 4    }
 5}
 6
 7impl<T> LinkedList<T> {
 8    fn new() -> Self {
 9        Self { head: None }
10    }
11}

Node的new函数用来使用给定的data数据创建一个孤零零的(没有下一个节点的)节点。

LinkedList的new函数用来创建一个空链表。

3.实现从链表头部插入节点的prepend方法 #

前面已经完成了链表和链表节点的定义，下面我们为链表实现了prepend方法，这个方法将采用头插法的方式向链表中添加节点。

代码片段5:

 1impl<T> LinkedList<T> {
 2    fn new() -> Self {
 3        Self { head: None }
 4    }
 5
 6    /// 在链表头部插入节点(头插法push front)
 7    fn prepend(&mut self, data: T) -> &mut Self {
 8        // 从传入数据构建要插入的节点
 9        let mut new_node = Box::new(Node::new(data));
10        match self.head {
11            // 当前链表为空时, 插入的节点直接作为头节点
12            None => self.head = Some(new_node),
13            // 当前链表非空时, 插入的节点作为新的头节点插入到原来的头结点前面
14            Some(_) => {
15                // 调用Option的take方法取出Option中的头结点(take的内部实现是mem::replace可避免内存拷贝), 作为新插入节点的下一个节点
16                new_node.next = self.head.take();
17                // 将新插入的节点作为链表的头节点
18                self.head = Some(new_node);
19            }
20        }
21        self
22    }
23}
24
25fn main() {
26    let mut ll = LinkedList::new();
27    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
28    print!("{ll:?}"); // LinkedList { head: Some(Node { data: 1, next: Some(Node { data: 2, next: Some(Node { data: 3, next: Some(Node { data: 4, next: Some(Node { data: 5, next: None }) }) }) }) }) }
29}

4.为链表实现Display trait定制链表的打印显示 #

前面我们实现了链表头部插入节点的prepend方法，并在main函数中构建了一个链表，以Debug的形式打印出了链表的信息。

为了使打印信息更好看，我们决定为LinkedList实现Display trait，使链表打印的格式类似为1 -> 2 -> 3 -> 4 -> 5 -> None。

代码片段6:

 1use std::fmt::Display;
 2
 3......
 4
 5impl<T: Display> Display for LinkedList<T> {
 6    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 7        if self.head.is_none() {
 8            // 如果链表为空, 只打印None
 9            write!(f, "None\n")?;
10        } else {
11            // 下面将遍历链表, 因为只是打印, 能获取链表各个节点的数据就行, 所以不需要获取所有权
12            let mut next = self.head.as_ref();
13            while let Some(node) = next {
14                write!(f, "{} -> ", node.data)?;
15                next = node.next.as_ref();
16            }
17            write!(f, "None\n")?;
18        }
19        Ok(())
20    }
21}
22
23fn main() {
24    let mut ll = LinkedList::new();
25    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
26    print!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
27}

5.为链表实现翻转链表功能的reverse方法 #

代码片段7:

 1impl<T> LinkedList<T> {
 2    ......
 3
 4    /// 翻转链表
 5    fn reverse(&mut self) {
 6        let mut prev = None; // 记录遍历链表时的前一个节点
 7        while let Some(mut node) = self.head.take() {
 8            self.head = node.next;
 9            node.next = prev;
10            prev = Some(node);
11        }
12        self.head = prev;
13    }
14}
15
16fn main() {
17    let mut ll = LinkedList::new();
18    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
19    println!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
20    ll.reverse(); // 5 -> 4 -> 3 -> 2 -> 1 -> None
21    println!("{ll}");
22}