Lumen

Lumen

Eager to know more, about the world, about the intelligence, and about myself.
github

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()用默認值(分別為NoneErr)填充原始的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包含一個可能包含指向下一個ListNodeBoxOptionOption用於指示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最初是不可變的。

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

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

參考#

循環鏈表的實際使用?(來自 GPT4 的回答)#

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

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

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

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。