Rust 链表

原创 Eagle1949 技术源泉

思考了很久，决定还是写下来，写一个系列的数据结构Rust实现。今天先开始链表。链表我们在学数据结构时已经知道，它有一个特性就是先进先出。

我们先定义节点结构：


type Link = Option<Rc<RefCell<Node>>>;#[derive(Clone)]struct Node {    pub value: String,    next: Link,}

节点的next指向下一个节点，下一个节点可能为空，也可能为一个节点。所以这里使用Option进行包装，但是为啥必须使用Rc，首先，Rc是智能指针，它为引用计数的缩写，引用计数意味着记录一个值引用的数量来知晓这个值是否仍在被使用。如果某个值有零个引用，就代表没有任何有效引用并可以被清理。Rc<T> 用于当我们希望在堆上分配一些内存供程序的多个部分读取，而且无法在编译时确定程序的哪一部分会最后结束使用它的时候。如果确实知道哪部分是最后一个结束使用的话，就可以令其成为数据的所有者，正常的所有权规则就可以在编译时生效。RefCell<T> 允许在运行时执行不可变或可变借用检查。它们只能在单线程中使用。

我们定义链表的结构：

struct LinkList {    head: Link,    tail: Link,    pub length: u64,}

head，和tail都指向一个节点。从tail中添加一个新节点，从head中获取一个节点。

我们实现节点和链表。先实现节点，创建一个新节点：

impl Node {// 这里可以确定的创建一个节点，所以直接使用这个类型，而不加Option    fn new(value: String) -> Rc<RefCell<Node>> {        Rc::new(RefCell::new(Node {            value: value,            next: None,// 可以为空的        }))    }}

然后实现链表：


impl LinkList {// 创建一个空的链表    pub fn new_empty()->LinkList{        LinkList { head: None, tail: None, length: 0 }    }// 从尾部插入一个节点    pub fn append(&mut self,value:String){        let new = Node::new(value); // 创建一个新节点        // 查看尾部是否有节点，有节点则将该节点指向新的节点，        // 没有节点代表是第一个节点，头部也要指向该节点。        match self.tail.take(){            Some(old)=>old.borrow_mut().next=Some(new.clone()),            None=>self.head=Some(new.clone())        };        // 将节点的数量加1        self.length+=1;        // 将尾部也指向这个新的节点        self.tail=Some(new);    }// 从头部取出一个节点    pub fn pop(&mut self)->Option<String>{    // 从头部取出一个节点，使用闭包函数    // 将头部的数据获取后，检查该节点的下一个节点是否为空，    // 如果为空，代表最后一个节点，tail也需要释放引用。    // 如果不为空，则将头部的引用指向这个节点。    // 然后将头部的节点数据返回。        self.head.take().map(|head|{            if let Some(next)=head.borrow_mut().next.take(){                self.head = Some(next);            }else{                self.tail.take();            }
            self.length -=1;
            Rc::try_unwrap(head).ok().expect("Something is terribly wrong").into_inner().value        })    }}

这里的take()方法多说两句，take方法将Option中的值取出，留下None，取出来的值如果使用必须为mut类型。

链表的使用方法：

fn main() {// 创建一个空链表，然后插入数据，再弹出数据。    let mut list = LinkList::new_empty();    list.append(String::from("A"));    list.append(String::from("B"));    list.append(String::from("C"));    list.append(String::from("D"));
    let value = list.pop();    println!("the value is {:?}",value);    let value = list.pop();    println!("the value is {:?}",value);    let value = list.pop();    println!("the value is {:?}",value);    let value = list.pop();    println!("the value is {:?}",value);    let value = list.pop();    println!("the value is {:?}",value);    let value = list.pop();    println!("the value is {:?}",value);
}

很简单的链表实现，如果你有好的想法和建议，欢迎留言！

继续滑动看下一个