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);
    }
}      

編譯發現報錯，那麼原因是什麼呢？