作为初学者，在掌握了Rust的基本语法和所有权机制之后，尝试编写常用的数据结构和算法，目的是更好地理解Rust的所有权机制。由于个人所限，本人对Rust还处于入门阶段，所以本文中的代码实现可能不是最合适的，甚至可能会出现问题。今天的目标是用rust实现一个简单的单链表LinkedList，同时为这个链表提供从头部插入元素（头部插入方式）、翻转链表、打印链表的功能.1.链表节点的定义要实现一个链表，首先要实现链表节点。根据其他编程语言的经验，首先用rust编写如下链表节点结构定义：代码片段1：structNode{data:T,next:Option>,//递归类型`Node`hasinfinitesize}中代码片段1，定义一个Node结构体，data字段使用泛型T为链表节点的数据。next使用Option枚举，即如果节点没有下一个节点，next为空。在rust中，没有其他编程语言中的空值(null,nil)，而是提供了一个Option解决方案。如果链表节点的下一个节点为空，则其下一个值为Option::None。不幸的是，代码片段1无法编译，报递归类型``Node``hasinfinitesize的编译错误。回顾一下Rust内存管理的基础，Rust需要在编译时知道一个类型占用了多少空间，而Node结构将自己嵌套在里面，这样就无法在编译时确认其占用空间的大小。在Rust中，当你有一个在编译时大小未知的类型，并且你想在需要精确大小的上下文中使用这个类型的值时，你可以使用智能指针Box。将next字段的类型改为Option>>，这样嵌套类型就是Box，嵌套的Node会分配到堆上。next字段只存储栈上智能指针Box的数据（ptr，meta）。这样就可以在编译时确定Node类型的大小。修改代码片段1如下：代码片段2：structNode{data:T,next:Option>>,}修改完成后即可编译通过。根据next:Option>>，每个链表节点Node都会拥有其下一个节点Node的所有权。2.链表的定义定义了链表之后，接下来就是定义一个结构体LinkedList来表示链表，它会封装链表的一些基本操作。该结构中只需要链表头节点的一个字段head，类型为Option>>。代码片段3:///单链表节点#[derive(Debug)]structNode{data:T,next:Option>>,}///单链表#[derive(Debug)]structLinkedList{head:Option>>,}为了方便使用，在Node和LinkedList的两个结构体中新增一个关联函数。代码片段4：implNode{fnnew(data:T)->Self{Self{data:data,next:None}}}implLinkedList{fnnew()->Self{Self{head:None}}}Node的新函数用于创建一个具有给定数据数据的孤独（没有下一个节点）节点。LinkedList的新功能用于创建一个空链表。3、实现从链表头部开始插入节点的prepend方法。之前已经完成了链表和链表节点的定义。接下来我们实现链表的prepend方法。该方法将使用表头插入方法将节点添加到链表中。代码片段5：implLinkedList{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),//当前链表不为空时，插入的节点node在原头节点前面插入作为新的头节点Some(_)=>{//调用Option的take方法取出Option中的头节点（take内部实现为mem::replaceto避免内存复制），作为新插入节点的下一个节点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.实现链表的Displaytrait，自定义链表的打印显示。前面我们实现了链表prepend方法头部节点的插入，并在main函数中建立了一个链表，并以Debug的形式打印了链表的信息。为了让打印的信息更好看，我们决定为LinkedList实现Displaytrait，这样链表打印的格式就类似于1->2->3->4->5->None。代码片段6：使用std::fmt::Display;......implDisplayforLinkedList{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(){让mutll=LinkedList::new();ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);打印！（“{ll}”）;//1->2->3->4->5->None}5.反向方法的代码片段7实现链表翻转链表的功能：implLinkedList{......///翻转链表fnreverse(&mutself){letmutprev=None;//遍历链表时记录上一个节点whileletSome(mutnode)=self.head.take(){self.head=node.next;node.next=prev;prev=一些（节点）；}self.head=prev;}}fnmain(){让mutll=LinkedList::new();ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);println!("{ll}");//1->2->3->4->5->无ll.reverse();//5->4->3->2->1->无println!("{ll}");}
