用 Rust 写点啥：数据结构篇——单向链表

关注

发布于: 2021 年 01 月 13 日

文前记：

如果说，从我开始投身于程序开发的工作和学习当中以来，遇到的哪个编程语言对我来说，是非常有吸引力的，至少从目前来看，一定是 Rust 语言，援引 Rust 语言官方的说法，Rust 是一门“赋予每个人构建可靠且高效软件能力的语言”，高性能、高可靠度、强生产力，使得 Rust 实至名归成为现代编程语言的优秀分子。

但是，作为一门编程语言，Rust 并非没有缺点，很多人就诟病编译太慢、学习曲线太陡、新人不友好之类，到了真正写的时候，又会出现各种“这个竟然会报错”“写链表太难了”的吐槽，骂声反正也是不绝于耳。

我还记得一开始自学编程的时候，在数据结构上花了不少周折，仍然记得被严奶奶那本《数据结构》里伪代码支配的恐惧，而且那本书里 C 语言实现那些东西看得实在眼花缭乱。最近也是因为开始求职，不断接到面试邀请，每次都会考到相应的点，又发现市面上类似《数据结构与算法分析》这样的资料，很少有以 Rust 语言描述的，所以萌生出用 Rust 实现数据结构的想法，因此，我尝试写文章，把这些东西用 Rust 语言实现出来，当然因个人水平有限，尽管大部分 Rust 实现代码是 safe Rust，部分仍然会用到 unsafe Rust，还请诸位读者海涵指正。

闲言少叙，我们正式开始。

本文描述对象

实现一个单向链表，在这个单向链表里，我将实现一个新链表的创建，如何在一个已有的链表的头、尾添加新的结点，以及如何删除第一个结点。

代码与解说

我们要实现一个链表，首先实现结点，因为我们并不确定创建结点用到的数据是什么类型的，所以用泛型，按其他语言里的写法，用 Rust 自然会写出如下的伪代码：

struct Node<T> {  	value: T,  	Next: Node<T>,//有人会写成Box<Node<T>>,也可以}

复制代码

考虑到 Rust 的所有权机制，以及我们并不会确定一个结点后续有没有新的结点，我们对上述的代码进行一些改进，并且实现创建新结点，代码如下：

type CoreNode<T> = Rc<RefCell<Node<T>>>;type LinkNode<T> = Option<CoreNode<T>>;
#[derive(Debug)]struct Node<T> {    data: T,    next: LinkNode<T>,}
impl<T> Node<T> {    fn new(value: T) -> CoreNode<T> {        Rc::new(RefCell::new(Node {            data: value,            next: None,        }))    }}

复制代码

接下来，完成了结点的定义之后，我们就可以开始定义我们的单向链表了：

#[derive(Debug)]struct LinkedList<T> {    length: i32,    head: LinkNode<T>,    tail: LinkNode<T>,}

复制代码

当然，为了能够保证我们正确地删除链表的第一个结点，我们在创建新的链表的时候，会有一个头结点，因此，创建新链表的函数是这样的：

fn new() -> Self {        LinkedList {            length: 0,            head: None,            tail: None,        }    }

复制代码

这样，我们创建了一个新的链表，接下来，我们就可以逐步实现我们前面提到的三个事情：在一个已有的链表的头、尾添加新的结点，以及删除第一个结点。

首先，我们来看如何在头部加一个结点：

fn prepend(&mut self, data: T) {        let node = Node::new(data);  			//此处，创建的新结点后续指向现有头结点        node.borrow_mut().next = self.head.take();        match self.tail.take() {            Some(here) => self.tail = Some(here),            None => self.tail = Some(node.clone()),        };        self.length += 1;        self.head = Some(node);}

复制代码

与在头部添加结点类似，我们可以写出尾部添加结点的代码：

fn append(&mut self, data: T) {        let node = Node::new(data);        match self.tail.take() {            Some(here) => old.borrow_mut().next = Some(node.clone()),            None => self.head = Some(node.clone()),        };        self.length += 1;        self.tail = Some(node);}

复制代码

最后，我们可以写出，删除第一个结点的代码，删除第一个结点的代码，这里使用了映射，并且考虑到链表创建后可能没有结点接入，因此这里选用 Option 判断：

fn pop(&mut self) -> Option<T> {        self.head.take().map(|head| {            if let Some(next) = head.borrow_mut().next.take() {                self.head = Some(next);            } else {                self.tail.take();            }            self.length -= 1;            Rc::try_unwrap(head)                .ok()                .expect("Something is terribly wrong")                .into_inner()                .data        })}

复制代码

总结

以上，我们利用 Rust，编写创建了一个单向链表，并完成了在一个已有的链表的头、尾添加新的结点，以及删除第一个结点，对于单向链表，还有其他的操作，因个人水平有限，暂未能继续实现相应的函数，关于单向链表相关的后续，读者可通过如下的 github 地址及时跟进相关代码的更新，同时您也可以提出您的解决方案，感谢您的批评指正：

https://github.com/Mika-Lahtinen/ds_basis.git

发布于: 2021 年 01 月 13 日阅读数: 112

原文链接:【http://xie.infoq.cn/article/dd5ae8a3f9975b52e431f2074】。

Kurtis Moxley

关注

Console.WriteLine("Never say die"); 2020.07.16 加入

学化工的码字员，函数式真是个好东西

发布

暂无评论

创作场景

用 Rust 写点啥：数据结构篇——单向链表

本文描述对象

代码与解说

总结

Kurtis Moxley

评论