022 通过链表学Rust之为什么要非安全的单链表

介绍

视频地址：https://www.bilibili.com/video/av78062009/
相关源码：https://github.com/anonymousGiga/Rust-link-list

详细内容

前面我们都是使用安全的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来解决这个问题。