rust实现单链表
架构小白 人气:0前言
作为初学者,在掌握了rust的基本语法和所有权机制,尝试写一下常见数据结构和算法,目标是为了更好的理解rust的所有权机制。 受限于个人目前对rust仍处于入门阶段,因此本文代码实现不一定是最合适的,甚至可能存在问题。
今天的目标是用rust实现一个简单的单链表LinkedList,同时为此链表提供从头部插入元素(头插法)、翻转链表、打印链表的功能。
1.链表节点的定义
实现链表,首先是实现链表的节点,根据其他编程语言的经验,于是用rust首先写出了下面的链表节点结构体定义:
代码片段1:
struct Node<T> { data: T, next: Option<Node<T>>, // recursive type `Node` has infinite size }
在代码片段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:
struct Node<T> { data: T, next: Option<Box<Node<T>>>, }
修改完成后,可以编译通过了。根据next: Option<Box<Node<T>>>,每个链表节点Node将拥有它下一个节点Node的所有权。
2.链表的定义
定义完链表之后,下一步再定义一个结构体LinkedList用来表示链表,将会封装一些链表的基本操作。 结构体中只需方一个链表头节点的字段head,类型为Option<Box<Node<T>>>。
代码片段3:
/// 单链表节点 #[derive(Debug)] struct Node<T> { data: T, next: Option<Box<Node<T>>>, } /// 单链表 #[derive(Debug)] struct LinkedList<T> { head: Option<Box<Node<T>>>, }
为了便于使用,再给Node和LinkedList这两个结构体各添加一下关联函数new。
代码片段4:
impl<T> Node<T> { fn new(data: T) -> Self { Self { data: data, next: None } } } impl<T> LinkedList<T> { fn new() -> Self { Self { head: None } } }
Node的new函数用来使用给定的data数据创建一个孤零零的(没有下一个节点的)节点。
LinkedList的new函数用来创建一个空链表。
3.实现从链表头部插入节点的prepend方法
前面已经完成了链表和链表节点的定义,下面我们为链表实现了prepend方法,这个方法将采用头插法的方式向链表中添加节点。
代码片段5:
impl<T> LinkedList<T> { fn new() -> Self { Self { head: None } } /// 在链表头部插入节点(头插法push front) fn prepend(&mut self, data: T) -> &mut Self { // 从传入数据构建要插入的节点 let mut new_node = Box::new(Node::new(data)); match self.head { // 当前链表为空时, 插入的节点直接作为头节点 None => self.head = Some(new_node), // 当前链表非空时, 插入的节点作为新的头节点插入到原来的头结点前面 Some(_) => { // 调用Option的take方法取出Option中的头结点(take的内部实现是mem::replace可避免内存拷贝), 作为新插入节点的下一个节点 new_node.next = self.head.take(); // 将新插入的节点作为链表的头节点 self.head = Some(new_node); } } self } } fn main() { let mut ll = LinkedList::new(); ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1); 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 }) }) }) }) }) } }
4.为链表实现Display trait定制链表的打印显示
前面我们实现了链表头部插入节点的prepend方法,并在main函数中构建了一个链表,以Debug的形式打印出了链表的信息。
为了使打印信息更好看,我们决定为LinkedList实现Display trait,使链表打印的格式类似为1 -> 2 -> 3 -> 4 -> 5 -> None。
代码片段6:
use std::fmt::Display; ...... impl<T: Display> Display for LinkedList<T> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { if self.head.is_none() { // 如果链表为空, 只打印None write!(f, "None\n")?; } else { // 下面将遍历链表, 因为只是打印, 能获取链表各个节点的数据就行, 所以不需要获取所有权 let mut next = self.head.as_ref(); while let Some(node) = next { write!(f, "{} -> ", node.data)?; next = node.next.as_ref(); } write!(f, "None\n")?; } Ok(()) } } fn main() { let mut ll = LinkedList::new(); ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1); print!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None }
5.为链表实现翻转链表功能的reverse方法
代码片段7:
impl<T> LinkedList<T> { ...... /// 翻转链表 fn reverse(&mut self) { let mut prev = None; // 记录遍历链表时的前一个节点 while let Some(mut node) = self.head.take() { self.head = node.next; node.next = prev; prev = Some(node); } self.head = prev; } } fn main() { let mut ll = LinkedList::new(); ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1); println!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None ll.reverse(); // 5 -> 4 -> 3 -> 2 -> 1 -> None println!("{ll}"); }
注意事项
只有一个可变引用
在C里面,如果要在链表的头部插入元素,可以这样写
Node* new_node = create_new_node(v); new_node->next = head; head = new_node;
但是在Rust里面你不能这样做。
在Rust中,常见的指针是Box<T>,和其他对象一样,Box<T>对象同一时刻只能有一个可变引用,而在上面的插入过程中,第2行,有两个指针指向同一个头结点,这个在Rust中是有问题的。
那在Rust里面,要实现在头部插入的功能,首先得把指针从head里面拿出来,然后再放到新的结点里面去,而不是直接复制,这里需要用到Option中的take方法,即把Option中的东西取出来。
总结
加载全部内容