用Rust写一个链表，非常详细，一遍看懂

前言

在Rust里写一个链表可不是一件容易的事，涉及到很多的知识点，需要熟练掌握之后才能写出一个不错的链表。这篇文章主要介绍了如何写一个Rust链表，并且补充了涉及到的很多的额外知识点，尤其是所有权问题。
首先，你需要明白，为什么Rust链表难写，同样的为什么C实现简单一点呢？
只能有一个引用！！！这是最关键的，然后就是Rust中是没有NULL指针的，这就需要用到Option枚举，在编译阶段必须知道类型的大小，这就需要使用Box智能指针。
在C语言实现一个简单的链表，可以这样写：

Node* new_node =create_new_node(v);
new_node->next = head;
head = new_node;

这段代码里面，head和new_node->next指向了同一个节点，这个在C语言里面没事，但是在Rust不允许，因为指针类型为Box，Box对象同一时刻只能有一个可变引用，而在上面的插入过程中，第2行，有两个指针指向同一个头结点。

预先知识点

Option枚举及其所有权问题

1.最简单的Option枚举就是，里面有Some和None，对于枚举大家一定要了解，他是等于其中一个的，并不是包含关系，这一点一定要理清楚，不然代码会很难理解。None可以替代C语言中的NULL。

pubenumOption<T>{Some(T),None,}

2.unwrap()方法：
在确认Option不为None的情况下，可以用unwrap方法拆解出其中的值，并获取值的所有权，如果为None，就会引发panic。这里要强调的是，unwrap会消费Option本身的值，后面就不能再用了。

let a =Some(Box::new(5));let d = a.unwrap();// println!("{:?}", a); // cannot use 'a' again.println!("{:?}", d);

但这里有一个所有权的限制，因为涉及到其内部值的所有权的转移，所以只有Option原始变量本身可以调用unwrap方法，其引用（包括可变引用）均不可调用。这和unwrap的实现方法有关系，因为其消费了原始变量。下方代码不可编译：

letmut a =Some(Box::new(5));let b =&mut a;let c = b.unwrap();// Error! cannot move out of `*b` which is behind a mutable reference

下面是unwrap源码：传入self，会转移所有权。

pubconstfnunwrap(self)->T{matchself{Some(val)=> val,None=>panic!("called `Option::unwrap()` on a `None` value"),}

3.take()方法：
take方法可以从Option中取出值，为原来的Option变量留下None值，但原来的变量还有效（但实际上没什么用处了，因为只剩下None了）。take方法的原始值或者引用必须为mut类型。强调一下，借用情况下可以调用take方法。或者说指向Option的可变引用（指针）可以调用take方法。

fnmain(){letmut a =Some(Box::new(5));letmut b =&mut a;let c =&mut b;let d = c.take();println!("{:?}", c);//Noneprintln!("{:?}", d);//Some(5)println!("{:?}", a);//None}

4.as_ref()方法：
但上面这两个方法，都改变了Option变量本身。如果不改变或受到限制无法改变Option本身时，只想借用或可变借用其中unwrap的值应该怎么办呢？这也是在实现链表时遇到的让人掉坑的问题。幸好Option提供了 as_ref 和 as_mut方法。

fnas_ref(&self)->Option<&T>//接受一个不可变引用，不获取所有权，返回一个Option枚举，其中的T为不可变引用类型，不获取所有权。

该方法将对Option的引用变为对Option所包含对象的不可变引用，并且返回一个新的Option。对这个新的Option进行unwrap操作，可以获得原Option所包含的对象的不可变引用。原始Option变量及其引用，均可调用as_ref方法，有点克隆的味道。例如：

let a =Some(Box::new(5));let b = a.as_ref();let c = b.unwrap();println!("{:?}", a);//Some(5)println!("{:?}", b);//Some(5)println!("{:?}", c);//5

5.as_mut()方法
与as_ref类似，as_mut只是返回了Option包含的数据的可变引用，

fnmain(){letmut a =Some(Point{ x:5, y:5});// let b = a.as_mut();let b =&mut a;let c = b.as_mut();// c is a new Option;let d = c.unwrap();
    d.x +=10;let e =&mut d.y;*e +=20;println!("{:?}", d.x);//15// println!("{:?}", c); // c is not available because of method call of "unwrap".println!("{:?}", b);//Some(Point { x: 15, y: 25 })println!("{:?}", a);//Some(Point { x: 15, y: 25 })}

通过以上代码可以看出，在未改变Option变量a的情况下，通过as_mut方法，改变了其包含的数据的值。这个能力对于编写链表时，尤其是节点的插入、删除时，可以灵活的操作指向下一个节点的指针。
说明一点，调用as_mut方法时，Option变量本身或其引用，必须为可变的，即mut类型。
简单类型的一个例子：这里注意原来的5已经改变成15。

fnmain(){letmut a =Some(5);let b = a.as_mut().unwrap();*b +=10;println!("b = {:?}", b);//b = 15println!("a = {:?}", a);//a=Some(15)}

if let和while let还有？操作符

ifletSome(a_T)= a_option {//a_T生命周期仅在花括号内生效。//当a_option不为None时满足条件。}whileletSome(a_T)= a_option {//当a_option 为None时退出循环。}

？操作符的作用就是简化Result枚举的，举个例子：

let f =File::open("username.txt");letmut f =match f {Ok(file)=> file,Err(e)=>returnErr(e),};//有了？运算符，就可以改成下面一行话letmut f =File::open("username.txt")?;

Rust方法和关联函数

具体可以看https://blog.csdn.net/cacique111/article/details/126311569，说的很详细。

如何编写一个链表

链表的定义

链表比较绕圈子，回顾Rust内存管理的基础知识，Rust需要在编译时知道一个类型占用多少空间，Node结构体内部嵌套了它自己，这样在编译时就无法确认其占用空间大小了。 在Rust中当有一个在编译时未知大小的类型，而又想要在需要确切大小的上下文中使用这个类型值的时候，可以使用智能指针Box。

/// 单链表节点#[derive(Debug)]structNode<T>{
    val:T,
    next:Option<Box<Node<T>>>,}/// 单链表#[derive(Debug)]structLinkedList<T>{
    head:Option<Box<Node<T>>>,
    size:usize,}

上面的代码定义之后，在Rust里面经常使用New函数，所以下面写上面结构体的new方法，

impl<T>LinkedList<T>{pubfnnew()->Self{SimpleLinkedList{
            head:None,
            size:0,}}

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

常用的链表操作

pubfnis_empty(&self)->bool{self.size ==0}pubfnlen(&self)->usize{self.size
    }//头插法pubfnpush(&mutself, data:T)->&mutSelf{let node =Box::new(Node::<T>{
            val: data,
            next:self.head.take(),//如果是空链表的话，直接为None，要不然就是Some(T)。为什么这里不用self.head?//看上去一样，但是如果不take，就会出现多个指针指向同一个节点，不符合所有权规则，可变引用可以进行take//take之后就会释放，变成None});self.head =Some(node);//将“头指针”指向新插入的节点self.size +=1;self}

//pop会从头节点开始删除节点，返回例如Some(5),Option<T>,T的所有权转移，删除转移也没啥。pubfnpop(&mutself)->Option<T>{ifself.is_empty(){returnNone;}let head =self.head.take().unwrap();//取出Some里面的值self.head = head.next;//head指向下一个节点self.size -=1;Some(head.val)}//peek返回头节点，是T的引用，不转移所有权。pubfnpeek(&self)->Option<&T>{ifself.is_empty(){returnNone}returnSome(&self.head.as_ref().unwrap().val)//这里确实，只是返回一个引用，不能对原来的链表造成任何影响。}pubfnpeek_mut(&mutself)->Option<&mutT>{ifself.is_empty(){returnNone}//这里就是as_mut,外部改变T的值，链表里面的值也会受到改变。returnSome(&mutself.head.as_mut().unwrap().val)}

pubfnrev(mutself)->SimpleLinkedList<T>{letmut rev_list =SimpleLinkedList::<T>::new();while!self.is_empty(){
            rev_list.push(self.pop().unwrap());}
        rev_list
    }

main函数部分，其中迭代器部分下期会有详细的解答。

fnmain(){letmut list=SimpleLinkedList::new();
    list.push(3);
    list.push(2);
    list.push(1);
    list.len();// println!("{list:?}");// for val in list.from_iter() {//     println!("{}",val);// }// for val in list.iter_mut() {//     *val += 1;//     println!("{}",val);// }for val in list.into_iter(){println!("{}",val);}//println!("{:?}",list.pop());//list.pop();//println!("{list:?}");//println!("{}",list.len());}