怎么用rust實(shí)現(xiàn)單鏈表

這篇文章將為大家詳細(xì)講解有關(guān)怎么用rust實(shí)現(xiàn)單鏈表，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

前言

今天的目標(biāo)是用rust實(shí)現(xiàn)一個(gè)簡(jiǎn)單的單鏈表LinkedList，同時(shí)為此鏈表提供從頭部插入元素(頭插法)、翻轉(zhuǎn)鏈表、打印鏈表的功能。

1.鏈表節(jié)點(diǎn)的定義

實(shí)現(xiàn)鏈表，首先是實(shí)現(xiàn)鏈表的節(jié)點(diǎn)，根據(jù)其他編程語(yǔ)言的經(jīng)驗(yàn)，于是用rust首先寫(xiě)出了下面的鏈表節(jié)點(diǎn)結(jié)構(gòu)體定義:

代碼片段1:

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

在代碼片段1中，定義一個(gè)Node結(jié)構(gòu)體，data字段使用了泛型類型T用于鏈表節(jié)點(diǎn)的數(shù)據(jù)。 next使用了Option枚舉，即如果該節(jié)點(diǎn)沒(méi)有下一個(gè)節(jié)點(diǎn)時(shí)，next是可空的，在rust中沒(méi)有其他編程語(yǔ)言中的空值(null, nil)，而是提供了Option的解決方案，如果該鏈表節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)為空，則其next取值為Option::None。

遺憾的是代碼片段1是無(wú)法編譯通過(guò)的，報(bào)了recursive type ``Node`` has infinite size的編譯錯(cuò)誤?；仡橰ust內(nèi)存管理的基礎(chǔ)知識(shí)，Rust需要在編譯時(shí)知道一個(gè)類型占用多少空間，Node結(jié)構(gòu)體內(nèi)部嵌套了它自己，這樣在編譯時(shí)就無(wú)法確認(rèn)其占用空間大小了。 在Rust中當(dāng)有一個(gè)在編譯時(shí)未知大小的類型，而又想要在需要確切大小的上下文中使用這個(gè)類型值的時(shí)候，可以使用智能指針Box。將next字段的類型修改為Option<Box<Node<T>>>，這樣嵌套的類型為Box，嵌套的Node將會(huì)被分配到堆上，next字段在棧上存儲(chǔ)的只是智能指針Box的數(shù)據(jù)(ptr, meta)，這樣在編譯時(shí)就能確定Node類型的大小了。將代碼片段1的修改如下:

代碼片段2:

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

修改完成后，可以編譯通過(guò)了。根據(jù)next: Option<Box<Node<T>>>，每個(gè)鏈表節(jié)點(diǎn)Node將擁有它下一個(gè)節(jié)點(diǎn)Node的所有權(quán)。

2.鏈表的定義

定義完鏈表之后，下一步再定義一個(gè)結(jié)構(gòu)體LinkedList用來(lái)表示鏈表，將會(huì)封裝一些鏈表的基本操作。 結(jié)構(gòu)體中只需方一個(gè)鏈表頭節(jié)點(diǎn)的字段head，類型為Option<Box<Node<T>>>。

代碼片段3:

/// 單鏈表節(jié)點(diǎn)
#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

/// 單鏈表
#[derive(Debug)]
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

為了便于使用，再給Node和LinkedList這兩個(gè)結(jié)構(gòu)體各添加一下關(guān)聯(lián)函數(shù)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函數(shù)用來(lái)使用給定的data數(shù)據(jù)創(chuàng)建一個(gè)孤零零的(沒(méi)有下一個(gè)節(jié)點(diǎn)的)節(jié)點(diǎn)。

LinkedList的new函數(shù)用來(lái)創(chuàng)建一個(gè)空鏈表。

3.實(shí)現(xiàn)從鏈表頭部插入節(jié)點(diǎn)的prepend方法

前面已經(jīng)完成了鏈表和鏈表節(jié)點(diǎn)的定義，下面我們?yōu)殒湵韺?shí)現(xiàn)了prepend方法，這個(gè)方法將采用頭插法的方式向鏈表中添加節(jié)點(diǎn)。

代碼片段5:

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

    /// 在鏈表頭部插入節(jié)點(diǎn)(頭插法push front)
    fn prepend(&mut self, data: T) -> &mut Self {
        // 從傳入數(shù)據(jù)構(gòu)建要插入的節(jié)點(diǎn)
        let mut new_node = Box::new(Node::new(data));
        match self.head {
            // 當(dāng)前鏈表為空時(shí), 插入的節(jié)點(diǎn)直接作為頭節(jié)點(diǎn)
            None => self.head = Some(new_node),
            // 當(dāng)前鏈表非空時(shí), 插入的節(jié)點(diǎn)作為新的頭節(jié)點(diǎn)插入到原來(lái)的頭結(jié)點(diǎn)前面
            Some(_) => {
                // 調(diào)用Option的take方法取出Option中的頭結(jié)點(diǎn)(take的內(nèi)部實(shí)現(xiàn)是mem::replace可避免內(nèi)存拷貝), 作為新插入節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
                new_node.next = self.head.take();
                // 將新插入的節(jié)點(diǎn)作為鏈表的頭節(jié)點(diǎn)
                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.為鏈表實(shí)現(xiàn)Display trait定制鏈表的打印顯示

前面我們實(shí)現(xiàn)了鏈表頭部插入節(jié)點(diǎn)的prepend方法，并在main函數(shù)中構(gòu)建了一個(gè)鏈表，以Debug的形式打印出了鏈表的信息。

為了使打印信息更好看，我們決定為L(zhǎng)inkedList實(shí)現(xiàn)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, "None\n")?;
        } else {
            // 下面將遍歷鏈表, 因?yàn)橹皇谴蛴? 能獲取鏈表各個(gè)節(jié)點(diǎn)的數(shù)據(jù)就行, 所以不需要獲取所有權(quán)
            let mut next = self.head.as_ref();
            while let Some(node) = next {
                write!(f, "{} -> ", node.data)?;
                next = node.next.as_ref();
            }
            write!(f, "None\n")?;
        }
        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.為鏈表實(shí)現(xiàn)翻轉(zhuǎn)鏈表功能的reverse方法

代碼片段7:

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

    /// 翻轉(zhuǎn)鏈表
    fn reverse(&mut self) {
        let mut prev = None; // 記錄遍歷鏈表時(shí)的前一個(gè)節(jié)點(diǎn)
        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}");
}

注意事項(xiàng)

只有一個(gè)可變引用

在C里面，如果要在鏈表的頭部插入元素，可以這樣寫(xiě)

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

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

在Rust中，常見(jiàn)的指針是Box<T>，和其他對(duì)象一樣，Box<T>對(duì)象同一時(shí)刻只能有一個(gè)可變引用，而在上面的插入過(guò)程中，第2行，有兩個(gè)指針指向同一個(gè)頭結(jié)點(diǎn)，這個(gè)在Rust中是有問(wèn)題的。

那在Rust里面，要實(shí)現(xiàn)在頭部插入的功能，首先得把指針從head里面拿出來(lái)，然后再放到新的結(jié)點(diǎn)里面去，而不是直接復(fù)制，這里需要用到Option中的take方法，即把Option中的東西取出來(lái)。

關(guān)于“怎么用rust實(shí)現(xiàn)單鏈表”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。