繼續 Rust 標準庫 學習系列， 這次是 LinkedList<T>。注意，實現來自 Rust stable v1.33.0.

擁有節點的雙向列表。

LinkedList 永許在常量時間內從兩端 push和pop 元素。

大多數情況最好用 Vec 或 VecDeque 替代 LinkedList。通常，基於數組的容器更快，內存效率更高，並且更好的利用 CPU 緩存。

Rust std doc

與 Vec<T> 不同的是

  1. 通過索引訪問一個元素需要對列表進行線性迭代。
  2. append is O(1)。
  3. 有趣的是 linked_list::Iter 與 linked_list::IterMut 的不同之處。IterMut的不可變性用 &mut 和 PhantomData<&a Node<T>> 確保健全性 (更多關於 PhantomData，稍後說明)。

這兒有 一本書 (如果你沒讀過這本書，我強烈建議你去閱讀它的細節) 向讀者解釋了為什麼單鏈表難以實現，而且對於 Rust 新用戶來說不是個好主意。

由於 Rust 的類型系統/所有權，實際上很難實現雙向列表。 主要原因是一個節點似乎需要來自相鄰節點的兩個所有者。然而， 不過，這對於 NonNull<T> 是可能的，我們在 Vec<T> 學習 中討論過。

這是簡化的定義

// Note: NonNull<T> does NOT own the referent
#[repr(transparent)] // <-- enforces the same type representation as *const T
struct NonNull<T: ?Sized> {
pointer: *const T,
}
struct Node<T> {
next: Option<NonNull<Node<T>>>, // Not Option<Box<Node<T>>>
prev: Option<NonNull<Node<T>>>,
element: T,
}
struct LinkedList<T> {
head: Option<NonNull<Node<T>>>,
tail: Option<NonNull<Node<T>>>,
len: usize,
marker: PhantomData<Box<Node<T>>>, // <-- sound dropck
}

為什麼不是 Option<Box<Node<T>>> ?

如果我們用 Box<Node<T>> 來代替，看看有什麼不同，這可能是個好主意。 我們討論了什麼是 Unique<T> 以及它與 NonNull<T> 有何不同，但作為一個快速提醒， Unique<T> 擁有 referent 而 NonNull<T> 沒有， 實際上， Box<T> (用於堆分配的指針類型) 包裝了 Unique<T> 提供了與 Unique<T> 交互的新的介面。

讓我們考慮 Node<T> 使用 Box (playpen link)

struct Node<T> {
prev: Option<Box<Node<T>>>,
next: Option<Box<Node<T>>>,
element: T,
}
fn main() {
let mut head_node = Node {
prev: None,
next: None,
element: 1,
};

let next_node = Node {
prev: Some(Box::new(head_node)), // <-- head_node is moved here
next: None,
element: 2,
};

head_node.next = Some(Box::new(next_node)); // Not good!
}

這要求 Use-After-Free (UAF) 所以我們直到我們不應該進一步推進 Undefined Behavior (UB) 的行為。 不過, 使用一個 non-owning NonNull<T> 可以解決以下問題 (playpen link)

use std::ptr::NonNull;
struct Node<T> {
prev: Option<NonNull<Node<T>>>,
next: Option<NonNull<Node<T>>>,
element: T,
}
fn main() {
let mut head_node = Node {
prev: None,
next: None,
element: 1,
};

let next_node = Node {
prev: NonNull::new(&mut head_node as *mut _),
next: None,
element: 2,
};

head_node.next = NonNull::new(&next_node as *const _ as *mut _);
}

但是我們如何確保這是合理的， 特別是把它用於 LinkedList<T>。確切的說

然而 PhantomData 和 dropck 有什麼關係?

我一直在試圖理解 PhantomData 和 dropck 之間的深層關係(LinkedList<T> 也是如此)，但是找不到任何明確的解釋，所以我在用戶頻道問了它並得到了一個 令人驚奇的答案 可以被推廣到 Vec, LinkedList 等。

本文翻譯自 Rust std study series: LinkedList

推薦閱讀：

相關文章