使用Rust完成单向链表

    最近闲下来了，看到一门语言Rust兴起，工资也可观，linux听说有部分也开始用rust写了，但听说学习有曲线，当时本人是不信邪的，学了之后才知道是真的有曲线。。。光是链表就搞了好几天，主要国内这方面的文章还太少，甚至给我一种rust还不成熟的错觉。不过既然写linux大佬都在用，且号称集各种语言优势的现代化语言，我就不由得想尝试一下。

    先给大家分析一下为什么难，为什么有些人会觉得比C/C++“难”。

1. 概念多
   因为rust集百家之长，所以吸收了很多先进的思想，多了许多的概念，最直观的体现在对于占用的释放。多了很多在其他语言没有的概念，比如生命周期，所有权等。

2. 规则多
   对于C++，大家都是自己申请，自己释放或者由栈帮助释放。对于java、python等语言，其占用由语言自己管理，gc（垃圾回收）经常被诟病，说是全局暂停。rust确保安全，将不安全的可能扼杀在编译期，对于程序员来说需要了解更多的规则，比如堆栈、回收机制等，在不使用unsafe的情况下，这些规则新手（我）是难以察觉的。

3. 国内资料少
   国内rust还在起步阶段，写的不错的教程都是由社区提供的，知乎上的 rust圣经系列 写的就非常不错，但是因为还在更新的原因，感觉不够全面，也不太适合纯新手去学。

    说说我自己的感受吧，本人学过大量的主流编程语言，其中C++用来写acm，主要体现逻辑思维，（当时觉得自己是会C++的），没有对底层有很深刻的了解。python、java写过很多项目，虽然都不大，但是都和rust关注的点不太一样。这样的我去学rust，被群里的rust大佬说是纯没学过编程的新手（哭），可见rust学习梯度是很大的，请后来者一定要做好准备，不懂就多问会的人。下面正式开始：

问题重述

    使用rust实现单向链表，方法为add和show。add用来在尾部增加一个节点，show用来循环展示链表内部的内容。

    群里的前辈说rust实现链表是很烦的，建议我直接用unsafe，但是我认为熟悉一门语言最好的方式就是数据结构的练习，如果数据结构能写得出，那基本上根据自己想法实现别的安全的代码了。所以我仍是写了链表。

数据结构

    主要是两个数据结构，一个是链表节点Node，存储了值和next；一个是链表本身，存储了head和tail。

    结构如下

#[derive(Debug)]
pub struct Node<T>{pub value:T,next:Option<Rc<RefCell<Node<T>>>>,
}
#[derive(Debug)]
pub struct List<T>{head:Option<Rc<RefCell<Node<T>>>>,tail:Option<Rc<RefCell<Node<T>>>>
}

方法

    对于List类需要实现add、show方法。

    add方法

impl<T> List<T>{pub fn new()->Self{List{head:None,tail:None}}pub fn add(&mut self,value:T){let new_node=Rc::new(RefCell::new(Node{value:value,next:None}));match self.tail.take(){Some(V)=>{(*V).borrow_mut().next=Some(Rc::clone(&new_node));},None=>{self.head = Some(Rc::clone(&new_node));}}self.tail = Some(new_node);}}

    show方法

impl<T:Display> List<T>{pub fn show(&mut self){let mut now;if let Some(v)=&self.head{now=Rc::clone(v);}else { return; }loop{let old=now;println!("{}",(*old).borrow().value);if let Some(v)=&(*old).borrow().next{now=Rc::clone(v);}else{return;};}}
}

    C语言数据结构学的好的同学，就会觉得我写的很麻烦，但是我之后会讲我为什么这么写，其他写法行不行。虽然不一定是最佳写法，但是凭个人的天资，还找不到人指导的情况下，我只能这么写了。如果有更好的方法，或是觉得我说的不对，欢迎私信。

    需要注意的是，对于println!需要T实现Display，由于我这里测试的是i32，故是实现Display的，所以T:Display。

主函数

fn main() {let mut list:List<i32>=List::new();list.add(32);list.add(54);list.show();//println!("{:#?}",list);}

    运行则可以看到链表数据被输出。

遇到的问题与分析

数据结构

    一开始数据结构我想的是和c一样，直接传入引用就行，也就是&Node。要分配在堆上改为Box<Node>,为解决所有权问题，改为Rc<Node>,因为需要add或对数据修改，改为Rc<Refcell<Node>>,然后存在空指针的情况，改为Option<Rc<Refcell<Node>>>，最终形成数据结构的类型。

关于show

    我在写代码的时候遇到最大的问题就是show，我一开始的写法是

pub fn show(&mut self){let mut now=&self.head;while let Some(v)=now{now=&(**v).borrow().next;}}

    这代码相信写过c语言的，乍一看都没觉得有问题，简短且明了。

    代码一跑，错误一片

error[E0716]: temporary value dropped while borrowed--> src/My_Link_List.rs:51:18|
51 |             now=&(**v).borrow().next;|                  ^^^^^^^^^^^^^^     -|                  |                  ||                  |                  temporary value is freed at the end of this statement|                  |                  ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, Node<T>>`|                  creates a temporary which is freed while still in use|                  a temporary with access to the borrow is created here ...|= note: consider using a `let` binding to create a longer lived value

    意思是这个refcell的borrow方法，返回的ref类型在分号结束就会被回收，这我倒是第一次知道，也不知道是啥原理，反正就告诉你延长这个ref的生命周期就行。遂改之

pub fn show(&mut self){let mut now=&self.head;while let Some(v)=now{let t=(**v).borrow();now=&t.next;}}

    这波延长到这一次循环结束，看起来也没错。再跑

error[E0597]: `t` does not live long enough--> src/My_Link_List.rs:52:18|
52 |             now=&t.next;|                  ^ borrowed value does not live long enough
53 |         }|         -|         ||         `t` dropped here while still borrowed|         borrow might be used here, when `t` is dropped and runs the destructor for type `Ref<'_, Node<T>>`

    说是t还活的不够长，t会在本次循环之后被调用。？？？虽然不太理解，但是就让他活长点就行是吧。

pub fn show(&mut self){let mut now=&self.head;let mut t;while let Some(v)=now{t=(**v).borrow();now=&t.next;}}

    这回获得够长了吧？

error[E0506]: cannot assign to `t` because it is borrowed--> src/My_Link_List.rs:52:13|
52   |             t=(**v).borrow();|             ^|             ||             assignment to borrowed `t` occurs here|             borrow later used here
53   |             now=&t.next;|                  - borrow of `t` occurs here|= note: borrow occurs due to deref coercion to `Node<T>`

    好家伙？出了新的错误，意思是说t是一个ref，now借用了t，如果t被重新赋值，就违反了“本体借用存在时，本体不能被重新赋值”的原则。那咋整？

    思考一下，如果我的循环中now每一次都要被赋值，而且必然是循环内部的某个变量的引用，而那个变量也是在变化的，那必然每次都报这个错误，因为下一轮必然修改那个被借用的变量。到这里我是山穷水尽了。在一阵瞎调试之后，我发现出现这个问题的原因：因为我的now是一个引用，她必然引用循环中的某个变化的变量，如果我的now不是引用，而是一个实体呢，他就不会引用其他变量，而是由其他数值组成的一个新变量，就能破开这个问题了。

    思考到此，我想将now的类型改为Option<Rc<Refcell<Node>>>，self.head是不能直接作为初值的，因为会造成所有权转移，所以我们只要把Option里面的东西提取出来再包裹一份Some就可以了。思考到这，我发现里面的东西本来迭代就要用到，我何必多此一举拿出来存进去又拿出来呢。。。。所以now的类型我定为Rc<Refcell<Node>>，第一步就是把head的now提取出来，之后对now进行循环，因为next是带option的，想要把值赋给now，还要把next的Option拿掉。故写出

    pub fn show(&mut self){//提取nowlet mut now;if let Some(v)=&self.head{now=Rc::clone(v);}else { return; }//如果head是none 就不用遍历了//循环输出loop{let next=&(*now).borrow().next;if let Some(v)=next{now=Rc::clone(v);}else { return; }}}

run！
惊喜

error[E0506]: cannot assign to `now` because it is borrowed--> src/My_Link_List.rs:61:17|
59   |             let next=&(*now).borrow().next;|                       ---------------|                       | ||                       | borrow of `now` occurs here|                       a temporary with access to the borrow is created here ...
60   |             if let Some(v)=next{
61   |                 now=Rc::clone(v);|                 ^^^ assignment to borrowed `now` occurs here
...
65   |         }|         - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, Node<T>>`|= note: borrow occurs due to deref coercion to `RefCell<Node<T>>`

    怎么还是类似的错误。。。再仔细看看，这次是now被人引用了，但是！now是本体，而非引用，我们可以把对now的引用转给别人，now失去所有权后，就能专心赋值了。加一个let old=now就可以把所有权转移了，遂得到上面的代码。

总结

    正如我上面所说，我对其中的原理并不是很理解，但是我根据报错不断进行修改代码，最终使得可以运行，具体原因我还要深究，毕竟不能总是出现问题再考虑怎么办，如有错误或者正确的理解，请私信我！