在 Rust 中學習鏈表相當麻煩,第一次看到像Option<Box<LinkedList>>
這樣的表達式時簡直是瘋狂。我在這裡寫下了許多我不熟悉的內容,真的是很多!
概念#
在 Rust 中使用已定義的鏈表的一種方式是Option<Box<LinkedList>>
,其中使用兩個包裝器來確保 1)對象的可選存在性,類似於 cpp 中的nullptr
,以及 2)指向下一個元素的固定大小指針。
以下概念出現在 Rust 中對 LinkedList 的操作中。通常,你可能想使用Option
類型的as_mut()
和take()
方法來進行鏈表操作。
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 緩存組織:在計算機架構中,一些緩存系統使用圓形緩衝區(可以用圓形鏈表實現)來管理內存。
- 導航系統:一些導航系統使用圓形鏈表來循環選項或菜單。
雖然這些是實際用途,但值得注意的是,其他數據結構(如數組或數組列表)通常可以用來實現相同的目標,有時性能特徵更好。數據結構的選擇取決於具體情況的要求。