Rust中的鏈表

在 Rust 中學習鏈表相當麻煩，第一次看到像Option<Box<LinkedList>>這樣的表達式時簡直是瘋狂。我在這裡寫下了許多我不熟悉的內容，真的是很多！

概念#

在 Rust 中使用已定義的鏈表的一種方式是Option<Box<LinkedList>>，其中使用兩個包裝器來確保 1）對象的可選存在性，類似於 cpp 中的nullptr，以及 2）指向下一個元素的固定大小指針。

以下概念出現在 Rust 中對 LinkedList 的操作中。通常，你可能想使用Option類型的as_mut()和take()方法來進行鏈表操作。

Mermaid Loading...

take的簽名：

pub fn take(&mut self) -> Option(T)

take()用默認值（分別為None或Err）填充原始的Option對象或Result。這是用來從其可變引用中獲取可變Option()枚舉的所有權。

要在這樣的Option上創建可變引用，你使用在Option上實現的as_mut()特徵，將&mut Option<T>轉換為Option<&mut T>。簽名如下：

fn as_mut(&mut self) -> &mut T;

有了這些魔法，我們終於可以像在 cpp 中執行node1.next = node2; auto tmp = node2.next;的操作：

// 將指針更改為另一個
node2.as_mut()?.next = node1;
// 將當前節點的下一個移動到獨立變量
let node3 = node2.as_mut()?.next.take();
// 移動對象本身很簡單
node1 = node2;
node2 = node2;

為什麼要使用`Box`？#

在 Rust 中，Box類型是一種用於在堆上分配數據的智能指針。當Box超出作用域時，會調用其析構函數並釋放堆內存。

我們在LinkedList中的ListNode使用Box的原因是因為 Rust 的所有權和大小要求。在 Rust 中，所有變量和數據在編譯時必須具有已知的大小。然而，LinkedList是一種遞歸數據結構，其中一個節點可以包含另一個節點。如果我們試圖在沒有Box的情況下定義它，則會因為每個節點包含另一個節點而導致無限大小。

通過使用Box，我們將ListNode存儲在堆上，而不是直接存儲在父節點中。這意味著父節點只需存儲Box，而Box具有已知的大小（它是指向堆內存的指針）。

以下是ListNode的可能樣子：

pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

在這個定義中，每個ListNode包含一個可能包含指向下一個ListNode的Box的Option。Option用於指示next字段可能為None（可能沒有下一個節點），而Box用於在堆上存儲下一個ListNode。

因此，僅僅使用Option是不夠的，因為它無法解決大小要求問題。我們需要Box來在堆上分配ListNode並為next字段提供已知的大小。

那麼如何創建一個循環鏈表？#

Box是一種智能指針，或者更具體地說，是 cpp 中的唯一指針。這意味著在Box中創建的鏈表保證不會有循環，因為Box對其指向的數據擁有獨占所有權，防止對同一數據的多個可變引用，從而避免潛在的數據競爭。

在 Rust 中創建LinkedList中的循環確實具有挑戰性，因為 Rust 的所有權模型及其防止數據競爭的方式。然而，有一些方法可以在 Rust 中創建循環或更複雜的結構，但它們涉及使用Rc（引用計數）和RefCell類型。Rc允許對同一數據的多個擁有者，而RefCell允許內部可變性，這意味著即使有對其的不可變引用，我們也可以修改數據。

以下是如何創建循環的示例：

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn main() {
    let node1 = Rc::new(RefCell::new(Node { value: 1, next: None }));
    let node2 = Rc::new(RefCell::new(Node { value: 2, next: Some(node1.clone()) }));

    // 創建循環
    node1.borrow_mut().next = Some(node2.clone());
}

在這個示例中，node1指向node2，而node2又指向node1，形成了一個循環。Rc類型允許兩個節點擁有對方，而RefCell類型允許我們修改node1以指向node2，即使node1最初是不可變的。

然而，這樣的循環可能導致內存泄漏。在這個示例中，由於循環的存在，node1和node2將永遠不會被釋放，因為它們的引用計數始終大於零。Rust 的Rc類型沒有檢測或處理循環的方式。

因此，雖然在 Rust 的LinkedList中創建循環是可能的，但應該非常小心地進行，以避免內存泄漏。

參考#

循環鏈表的實際使用？（來自 GPT4 的回答）#

是的，循環或圓形鏈表在現實應用中確實有實際用途。以下是幾個例子：

輪詢調度：這是一種用於操作系統和其他處理時間共享的系統的調度算法。任務列表保存在圓形鏈表中，調度程序輪流處理任務，給每個任務一小段執行時間。當一個任務完成其回合後，調度程序將移動到圓形列表中的下一個任務。
多人棋盤遊戲：在許多多人遊戲中，基於回合的系統可以用圓形鏈表來實現。每個節點代表一個玩家，當前節點代表輪到的玩家。在每個回合之後，遊戲將前進到圓形列表中的下一個玩家。
圖片輪播或幻燈片：在網頁或移動應用中，圖片輪播或幻燈片可能使用圓形鏈表來循環顯示圖片。當用戶到達最後一張圖片時，下一張圖片是第一張，形成無縫循環。
CPU 緩存組織：在計算機架構中，一些緩存系統使用圓形緩衝區（可以用圓形鏈表實現）來管理內存。
導航系統：一些導航系統使用圓形鏈表來循環選項或菜單。

雖然這些是實際用途，但值得注意的是，其他數據結構（如數組或數組列表）通常可以用來實現相同的目標，有時性能特徵更好。數據結構的選擇取決於具體情況的要求。