介绍

视频地址：www.bilibili.com/video/av78062009/

相关源码：github.com/anonymousGiga/Rust-link...

详细内容

前面我们都是使用安全的Rust编程来实现链表，但是实现的时候难度确实比较大。从本节开始，我们开始用非安全编程的方式来实现链表。

栈和队列的区别是，栈是先进后出，队列是先进先出。对应到两者的push和pop函数，区别如下：

复制
//栈
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
 
stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)
 
stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
 
 
//队列
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
 
flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
 
flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

我们发现，当用链表分别实现栈和队列时，pop和push函数可能就需要遍历。那么如何来提升效率，减少遍历呢？答案就是我们分别记录链表的头和尾。

尝试更加完善的单链表

为了把链表的尾部也记录下来，我们重新定义我们的链表，如下：

复制
ub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, //自己指向自己，都是可变引用，不允许存在
}
 
type Link<T> = Option<Box<Node<T>>>;
 
struct Node<T> {
    elem: T,
    next: Link<T>,
}
 
impl<'a, T> List<'a, T> {
    pub fn new() -> Self {
        List { head: None, tail: None }    
    }
 
    pub fn push(&'a mut self, elem: T) {let new_tail = Box::new(Node {
            elem: elem,
            next: None, 
        });
 
        let new_tail = match self.tail.take() {Some(old_tail) => {
                old_tail.next = Some(new_tail);
                old_tail.next.as_deref_mut()}None => {
                self.head = Some(new_tail);
                self.head.as_deref_mut()}}; 
 
        self.tail = new_tail;}
 
    pub fn pop(&'a mut self) -> Option<T> {
        self.head.take().map(|head| {let head = *head;
            self.head = head.next;
 
            if self.head.is_none() {
                self.tail = None;}
 
            head.elem
        })}
}

存在的问题

当我们把带有记录尾部位置的单链表实现后，编译发现是没有问题的。下面我们来添加测试代码：

复制
#[cfg(test)]
mod tests {
    use super::List;
 
    #[test] 
    fn basics() {let mut list = List::new();
        assert_eq!(list.pop(), None);
        list.push(1);
        list.push(2);
        list.push(3);
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));
        list.push(4);
        list.push(5);
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);}
}

编译发现报错，那么原因是什么呢？

原来我们在list中，定义的tail，是一个可变的，而定义的list也是可变的，tail又是链表的一部分，相当于可变引用指向自己，自己本身又是可变的，相当于多个可变引用指向同一个东西，所以报错。

按照我们的分析，这个问题似乎误解，那我们怎么解决呢？

所以引出unsafe来解决这个问题。