如何使用rust實現簡單的單連結串列

2022-03-18 13:01:30

前言

作為初學者，在掌握了rust的基本語法和所有權機制，嘗試寫一下常見資料結構和演演算法，目標是為了更好的理解rust的所有權機制。受限於個人目前對rust仍處於入門階段，因此本文程式碼實現不一定是最合適的，甚至可能存在問題。

今天的目標是用rust實現一個簡單的單連結串列LinkedList，同時為此連結串列提供從頭部插入元素(頭插法)、翻轉連結串列、列印連結串列的功能。

1.連結串列節點的定義

實現連結串列，首先是實現連結串列的節點，根據其他程式語言的經驗，於是用rust首先寫出了下面的連結串列節點結構體定義:

程式碼片段1:

struct Node<T> {
    data: T,
    next: Option<Node<T>>, // recursive type `Node` has infinite size
}

在程式碼片段1中，定義一個Node結構體，data欄位使用了泛型型別T用於連結串列節點的資料。 next使用了Option列舉，即如果該節點沒有下一個節點時，next是可空的，在rust中沒有其他程式語言中的空值(null, nil)，而是提供了Option的解決方案，如果該連結串列節點的下個節點為空，則其next取值為Option::None。

遺憾的是程式碼片段1是無法編譯通過的，報了recursive type ``Node`` has infinite size的編譯錯誤。回顧Rust記憶體管理的基礎知識，Rust需要在編譯時知道一個型別佔用多少空間，Node結構體內部巢狀了它自己，這樣在編譯時就無法確認其佔用空間大小了。在Rust中當有一個在編譯時未知大小的型別，而又想要在需要確切大小的上下文中使用這個型別值的時候，可以使用智慧指標Box。將next欄位的型別修改為Option<Box<Node<T>>>，這樣巢狀的型別為Box，巢狀的Node將會被分配到堆上，next欄位在棧上儲存的只是智慧指標Box的資料(ptr, meta)，這樣在編譯時就能確定Node型別的大小了。將程式碼片段1的修改如下:

程式碼片段2:

struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

修改完成後，可以編譯通過了。根據next: Option<Box<Node<T>>>，每個連結串列節點Node將擁有它下一個節點Node的所有權。

2.連結串列的定義

定義完連結串列之後，下一步再定義一個結構體LinkedList用來表示連結串列，將會封裝一些連結串列的基本操作。結構體中只需方一個連結串列頭節點的欄位head，型別為Option<Box<Node<T>>>。

程式碼片段3:

/// 單連結串列節點
#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

/// 單連結串列
#[derive(Debug)]
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

為了便於使用，再給Node和LinkedList這兩個結構體各新增一下關聯函數new。

程式碼片段4:

impl<T> Node<T> {
    fn new(data: T) -> Self {
        Self { data: data, next: None }
    }
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }
}

Node的new函數用來使用給定的data資料建立一個孤零零的(沒有下一個節點的)節點。

LinkedList的new函數用來建立一個空連結串列。

3.實現從連結串列頭部插入節點的prepend方法

前面已經完成了連結串列和連結串列節點的定義，下面我們為連結串列實現了prepend方法，這個方法將採用頭插法的方式向連結串列中新增節點。

程式碼片段5:

impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }

    /// 在連結串列頭部插入節點(頭插法push front)
    fn prepend(&mut self, data: T) -> &mut Self {
        // 從傳入資料構建要插入的節點
        let mut new_node = Box::new(Node::new(data));
        match self.head {
            // 當前連結串列為空時, 插入的節點直接作為頭節點
            None => self.head = Some(new_node),
            // 當前連結串列非空時, 插入的節點作為新的頭節點插入到原來的頭結點前面
            Some(_) => {
                // 呼叫Option的take方法取出Option中的頭結點(take的內部實現是mem::replace可避免記憶體拷貝), 作為新插入節點的下一個節點
                new_node.next = self.head.take();
                // 將新插入的節點作為連結串列的頭節點
                self.head = Some(new_node);
            }
        }
        self
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    print!("{ll:?}"); // LinkedList { head: Some(Node { data: 1, next: Some(Node { data: 2, next: Some(Node { data: 3, next: Some(Node { data: 4, next: Some(Node { data: 5, next: None }) }) }) }) }) }
}

4.為連結串列實現Display trait客製化連結串列的列印顯示

前面我們實現了連結串列頭部插入節點的prepend方法，並在main函數中構建了一個連結串列，以Debug的形式列印出了連結串列的資訊。

為了使列印資訊更好看，我們決定為LinkedList實現Display trait，使連結串列列印的格式類似為1 -> 2 -> 3 -> 4 -> 5 -> None。

程式碼片段6:

use std::fmt::Display;

......

impl<T: Display> Display for LinkedList<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.head.is_none() {
            // 如果連結串列為空, 只列印None
            write!(f, "Nonen")?;
        } else {
            // 下面將遍歷連結串列, 因為只是列印, 能獲取連結串列各個節點的資料就行, 所以不需要獲取所有權
            let mut next = self.head.as_ref();
            while let Some(node) = next {
                write!(f, "{} -> ", node.data)?;
                next = node.next.as_ref();
            }
            write!(f, "Nonen")?;
        }
        Ok(())
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    print!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
}

5.為連結串列實現翻轉連結串列功能的reverse方法

程式碼片段7:

impl<T> LinkedList<T> {
    ......

    /// 翻轉連結串列
    fn reverse(&mut self) {
        let mut prev = None; // 記錄遍歷連結串列時的前一個節點
        while let Some(mut node) = self.head.take() {
            self.head = node.next;
            node.next = prev;
            prev = Some(node);
        }
        self.head = prev;
    }
}

fn main() {
    let mut ll = LinkedList::new();
    ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
    println!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
    ll.reverse(); // 5 -> 4 -> 3 -> 2 -> 1 -> None
    println!("{ll}");
}

注意事項

只有一個可變參照

在C裡面，如果要在連結串列的頭部插入元素，可以這樣寫

Node* new_node = create_new_node(v);
new_node->next = head;
head = new_node;

但是在Rust裡面你不能這樣做。

在Rust中，常見的指標是Box<T>，和其他物件一樣，Box<T>物件同一時刻只能有一個可變參照，而在上面的插入過程中，第2行，有兩個指標指向同一個頭結點，這個在Rust中是有問題的。

那在Rust裡面，要實現在頭部插入的功能，首先得把指標從head裡面拿出來，然後再放到新的結點裡面去，而不是直接複製，這裡需要用到Option中的take方法，即把Option中的東西取出來。

總結

到此這篇關於如何使用rust實現簡單的單連結串列的文章就介紹到這了,更多相關rust實現單連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！