怎么用rust实现单链表

魁首哥

作者

怎么用rust实现单链表

这篇文章将为大家详细讲解有关怎么用rust实现单链表，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

前言

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

1.链表节点的定义

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

代码片段1:

structNode<T>{data:T,next:Option<Node<T>>,//recursivetype`Node`hasinfinitesize}

在代码片段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:

structNode<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)]structNode<T>{data:T,next:Option<Box<Node<T>>>,}///单链表#[derive(Debug)]structLinkedList<T>{head:Option<Box<Node<T>>>,}

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

代码片段4:

impl<T>Node<T>{fnnew(data:T)->Self{Self{data:data,next:None}}}impl<T>LinkedList<T>{fnnew()->Self{Self{head:None}}}

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

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

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

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

代码片段5:

impl<T>LinkedList<T>{fnnew()->Self{Self{head:None}}///在链表头部插入节点(头插法pushfront)fnprepend(&mutself,data:T)->&mutSelf{//从传入数据构建要插入的节点letmutnew_node=Box::new(Node::new(data));matchself.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}}fnmain(){letmutll=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:

usestd::fmt::Display;......impl<T:Display>DisplayforLinkedList<T>{fnfmt(&self,f:&mutstd::fmt::Formatter<'_>)->std::fmt::Result{ifself.head.is_none(){//如果链表为空,只打印Nonewrite!(f,"None\n")?;}else{//下面将遍历链表,因为只是打印,能获取链表各个节点的数据就行,所以不需要获取所有权letmutnext=self.head.as_ref();whileletSome(node)=next{write!(f,"{}->",node.data)?;next=node.next.as_ref();}write!(f,"None\n")?;}Ok(())}}fnmain(){letmutll=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>{......///翻转链表fnreverse(&mutself){letmutprev=None;//记录遍历链表时的前一个节点whileletSome(mutnode)=self.head.take(){self.head=node.next;node.next=prev;prev=Some(node);}self.head=prev;}}fnmain(){letmutll=LinkedList::new();ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);println!("{ll}");//1->2->3->4->5->Nonell.reverse();//5->4->3->2->1->Noneprintln!("{ll}");}