單向鏈結串列是鏈結串列家族中最簡單的版本，特色是每兩個節點間只有一個單向的鏈結。
head
|
v
+--------+ +--------+ +--------+
| | | | | |
| node 0 |-->| node 1 |-->| node 2 |--> NULL
| | | | | |
+--------+ +--------+ +--------+
比起 雙向鏈結串列，單向鏈結串列少了一個額外的指標開銷，在基本操作的花費也較低。在不需要雙向疊代情形下單向鏈結串列很適用。
此外，單向鏈結串列也支援 tail-sharing，也就是共享 sublist。藉由共享 sublist，單向鏈結串列很容易實作 persistent data structure，再配合 immutable 特性，使得單向鏈結串列幾乎成為函數式程式語言最常見的集合型別之一。可以參考這篇 persistent immutable stack 實作文章。
本次實作的程式碼置於
rust_algorithm_club::collections::SinglyLinkedListAPI 文件中。
先建立最基本的節點 Node。
// cannot compile
struct Node<T> {
elem: T,
next: Node<T>,
}Node.elem 很直觀地儲存實際資料。而 Node.next 則是指向下個 Node。但這樣編譯不會成功，Rust 編譯時需要決定每個型別該配置多少記憶體空間，這種遞迴型別使得編譯器無限循環，無法決定配置大小。
很簡單，我們使用 Box<T> 這個智慧指標，直接將 Node 配置在記憶體 heap 上。如此以來，編譯器就會知道 next 只佔了一個指標的空間。
struct Node<T> {
elem: T,
next: Box<Node<T>>,
}
由於 Rust 沒有 null pointer，但照鏈結串列的定義，Node.next 可以是 NULL，因此我們使用 Option<T> 模擬 null pointer 的行為。最後，Node 的定義如下：
{{#include mod.rs:node_layout}}在開始實作各種增刪節點的操作之前，我們需要建立一個 struct 存放指向鏈結串列 head 的指標，同時，各種操作也會實作在這個 struct 上。事實上，這個 struct 就是對外公開的資料結構。
{{#include mod.rs:list_layout}}選擇把操作串列的函式寫在另一個 struct 而非 Node 上有幾個原因，1）外部並不需知道串列內部如何實作，公開 Node 會暴露實作。2）每個 Node 都帶有成員函式的話，函式指標會佔用太多額外資源。
串列的基本操作如下：
new：初始化一個空串列。push_front：新增節點到開頭的位置。pop_front：將開頭第一個節點移除。insert_after：在指定索引位置後插入一個新節點。remove：移除任意索引下的節點。clear：清除所有節點。is_empty：檢查串列是否沒有任何節點。reverse：反轉整個串列（head 變成 tail）。
實做初始化與清除資料非常直觀。其中清除其實就只是將 self 指向新的串列實例。
impl<T> SinglyLinkedList<T> {
{{#include mod.rs:list_new}}
{{#include mod.rs:list_clear}}
}你可能會想，在清除所有資料時，資源需不需要手動釋放？
和 C++ 的 RAII 一樣，Rust 有一個名叫 drop 的解構式，只要程式執行離開了資源擁有者的可視範圍（out of scope），就會自動呼叫 drop。我們在 Drop trait 一節會再深入探討。
單向鏈結串列在第一個節點前增加新節點，或是刪除第一個節點，都可以在常數時間完成。新增節點 push_front 的概念很簡單，1）建立新的節點，並把新節點 next 指標指向串列第一個節點。2）把串列的 head 指向新建立的節點。
{{#include mod.rs:list_push_front}}- 釋放 SinglyLinkedList 對第一個節點的所有權
- 建立一新節點，並將原本第一個節點所有權轉移給新節點。再將新節點所有權轉移到串列本身。
刪除第一個節點 pop_front 的實作步驟如下：首先取得第一個節點的所有權，再將 head 指向第一個節點 Node.next 下一個節點，再返回第一個節點的資料給呼叫端。
{{#include mod.rs:list_pop_front}}- 取得第一個元素的所有權，若無首個元素，表示串列為空，此處利用
?運算子直接回傳None。 - 將 head 指向下一個節點。
- 返回即將刪除節點的資料。
鏈結串列新增和刪除第一個節點都可以在
實作插入 insert_after 分為幾個步驟：
{{#include mod.rs:list_insert_after}}- 找到對應索引值的節點 A，若找不到則回傳這個串列的資料長度。
- 先取得節點 A 的所有權，才能修改它的值。
- 建立新節點 B，同時將節點 B 的
next指向 A 的後一個節點。 - 將新節點 B 做為節點 A 後一個節點
next。 - 把修改過的節點 A，重新賦值給指向節點 A 的指標
curr（可視為歸還所有權）。
而實作刪除任意索引下的節點 remove 和插入非常相似。
{{#include mod.rs:list_remove}}- 找到對應索引值的節點 A，若找不到則回傳
None。 - 先取得節點 A 的所有權，才能修改它的值。
- 把節點 A 的後一個節點 B 賦值給原本指向節點 A 的指標
curr。 - 回傳節點 A 的值。
反轉鏈結串列是工作面試時很常見的考題，這裡來實作看看。
{{#include mod.rs:list_reverse}}- 先建立一個暫時變數
prev，儲存疊代時的前一個節點。 - 從串列 head 取得第一個節點的所有權。
- 依序疊代整個串列
- 將節點 A 的後一個節點 B 暫存起來。
- 節點 A 的
next指向暫存在變數prev的節點 P。 - 節點 A 暫存在變數
prev內，保留到下一個疊代使用。 - 將節點 B 儲存在變數
curr內。此時
prev：節點 A，A 的next指向 P，
curr：節點 B，B 的next指向 A。
- 最後一次疊代時，變數
prev會儲存原始串列末端節點，這時轉移所有權到 head，完成反轉。
除了基本操作，SinglyLinkedList 實作了許多 trait，使用上更方便更符合 Rust 的慣例。
如果一個 struct 有許多成員，則會遞迴呼叫 struct 的 drop 成員函式。因此，一個串列的解構式很可能發生深層的巢狀遞迴：
# a linked list
a -> b -> c -> x -> y -> z
# call stack when `drop` being called
(a.drop
(b.drop
(c.drop
(x.drop
(y.drop
(z.drop
(z.dropped
(y.dropped
(x.dropped
(c.dropped
(b.dropped
(a.dropped
如果節點一多，肯定會 stack overflow，太可怕了！
既然如此，那麼就透過 Drop trait，實作一個疊代版本的解構式，消弭可怕的 call stack 吧。
{{#include mod.rs:list_drop}}- 取得 head 的所有權。
- 透過 pattern matching 取得 Node 裡面 Box 的所有權。
- 取得下一個 Node 的所有權，並將它指向共用的變數
link。 - 離開了
node的 scope，node呼叫drop釋放自身資源。
詳細思路過程可查看 Learning Rust With Entirely Too Many Linked Lists 的 Drop 章節，該章完整闡述為什麼不能用 tail recursive 來實作，但最大的原因是 Rust core team 暫時延緩實踐 tail call optimization。
實際上，透過呼叫 pop_front()，不斷移除第一個節點，並使用 is_some() 檢查是否仍有節點，幾乎可以達到同樣的 drop 效果，而且更簡潔易懂。差別僅在於，相較於前個實作自己處理 call stack，這個實作每次移除元素都需要 pop_front() 與 is_some() 的 stack，多了些微小的開銷，雖然可透過 #[inline] attribute 提示編譯器，但終究只是提示。
impl<T> Drop for SinglyLinkedList<T> {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}既然鏈結串列是一種序列（sequence，有序的資料結構），少不了實作 Iterator、IntoIterator 等 trait，使串列可以輕鬆使用 for-in loop 遍歷（traverse）。
首先，先定義幾個疊代器的 struct。
{{#include mod.rs:IntoIter_layout}}
{{#include mod.rs:Iter_layout}}
{{#include mod.rs:IterMut_layout}}建立這三個 iterator struct 是常見的 Rust 設計模式。
IntoIter：產生T，實作會吃掉元素所有權的IntoIteratortraitIter：產生&T，實作提供 immutable borrow 的Iteratortrait。IterMut：產生&mut T，實作提供 mutable borrow 的Iteratortrait。
相對應的，SinglyLinkedList 則新增三個成員函式：
fn into_iter(self) -> IntoIter<T>：轉移所有權的疊代器。Into 一詞慣例上指涉所有權移轉。fn iter(&self) -> Iter<T>：以 immutable reference 疊代串列。fn iter_mut(&mut self) -> IterMut<T>：以 mutable reference 疊代串列。
先來看 IntoIter 實作。
// 1
{{#include mod.rs:IntoIter_layout}}
// 2
{{#include mod.rs:IntoIter}}
// 3
{{#include mod.rs:IntoIterator}}- 宣告一個 tuple struct，唯一的成員是
SinglyLinkedList。 - 實作
Iteratortrait 的 required methodnext，為了達成 Into 會消耗原始資料，轉換所有權的特性，我們利用pop_front()將節點的資料依序刪除（pop）。 IntoInterator的 required method 傳遞self進來，所以無論怎麼實作IntoIterstruct，呼叫into_iter()後，外部就無法再次存取此SinglyLinkedList實例，達到所有權轉移的目標。
可能有人會疑惑，
IntoIter並沒有內部狀態記錄欄位，疊代器如何依據狀態產生下一筆資料？受惠於IntoIterator傳遞所有權的特性，IntoIter可直接改變原始串列的內部狀態，例如pop_front會移除原始串列的節點。因此，相較於Iter、IterMut額外記錄狀態，IntoIter不需自行記錄疊代器的疊代狀態。
再來看看 Iter 怎麼實踐。
{{#include mod.rs:Iter_layout}}
{{#include mod.rs:Iter}}
impl<T> SinglyLinkedList<T> {
// ...
{{#include mod.rs:list_iter}}
}- 這個 struct 的
next是為了儲存Node資訊，方便記錄疊代器當前的狀態。加上生命週期'a是因編譯器無法推敲Option<&Node<T>>會活多久，需要顯著標明&Node至少與該疊代器同生共死。 - 由於
Iter是為了實作產生&T的疊代器，associated type 設為&'a T。 - 將當前節點的後一個節點設為
Iter疊代器的狀態。並回傳當前節點的資料。
這邊用了Option::as_deref()，可直接將Option<T>轉換成Option<&T>，若T有實作Deref特徵，更可以將T轉為Deref::Target，例如這裡就是藉由Box::deref()將Box<Node<T>>轉換為&Node<T>。 - 在
SinglyLinkedList上加iter()成員函式回傳Iter疊代器。 - 產生疊代器初始化狀態，和第三步一模一樣。
最後，IterMut 與 Iter 疊代器實作上大同小異。把 Iter 用到 Option::as_deref() 改為 Option::as_deref_mut()，其他 & 改成 &mut 即可。
PartialEq trait 是用來實現兩個串列是否能夠比較，而我們在此定義如下：
有兩個 SinglyLinkedList Sa、Sb，Sa、Sb 的元素皆符合 PartialEq trait。當
- Sa 的總節點數 等於 Sb 的總節點數，
- Sa 所有元素依序等於 Sb 所有元素，
則稱 Sa 與 Sb 有 partial equiavalence（Sa == Sb）。
實作上我們用了 iter 成員函式把兩個串列 zip 在一起，在用 all 確認元素兩兩相等，十分 Rust 風格的作法。
{{#include mod.rs:PartialEq}}為了方便修復臭蟲，通常會實作 Debug trait 印出有助於解決問題的資料。歸功於 Iterator 的實踐，我們可以快速用 self.iter() 印出所有節點內的元素，客製化 Debug 的顯示方式。
{{#include mod.rs:Debug}}| Operation | Complexity |
|---|---|
| get | |
| insert | 節點已知：$O(1)$ ；節點未知：$O(n - i)$ |
| remove | 節點已知：$O(1)$ ；節點未知：$O(n - i)$ |
| append | |
| prepend | |
| pop first | |
| pop last | |
| space |
|
$n$ ：資料筆數。
$i$ ：相對於整個容器的索引位置。
值得觀察的是，許多操作因為單向鏈結串列只能從 head 開始搜索的緣故，執行時間都呈線性，使用上要特別注意。
- Rust Documentation: LinkedList
- Learning Rust With Entirely Too Many Linked Lists
- Duscussions at Stackoverflow
- StackExchange: Reversal of a singly-linked list in Rust
- SVG of node memory representation modified from The Rust Programming Language