鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。由于不必須按順序存儲，鏈表在給定位置插入的時候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是在有序數(shù)據(jù)中查找一個節(jié)點或者訪問特定下標(biāo)的節(jié)點則需要O(n)的時間，而線性表相應(yīng)的時間復(fù)雜度分別是O(logn)和O(1)。

使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項目的方式可能不同于這些數(shù)據(jù)項目在內(nèi)存或磁盤上的順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。

下面看我們一步步實現(xiàn)鏈表：

定義鏈表結(jié)構(gòu)

use List::*;

enum List {
    // Cons: 包含一個元素和一個指向下一個節(jié)點的指針的元組結(jié)構(gòu)
    Cons(u32, Box<List>),
    // Nil: 表示一個鏈表節(jié)點的末端
    Nil,
}

實現(xiàn)鏈表的方法

impl List {
    // 創(chuàng)建一個空鏈表
    fn new() -> List {
        // `Nil` 是 `List`類型的。因為前面我們使用了 `use List::*;`
        // 所以不需要 List::Nil 這樣使用
        Nil
    }

    // 在前面加一個元素節(jié)點，并且鏈接舊的鏈表和返回新的鏈表
    fn prepend(self, elem: u32) -> List {
        // `Cons` 也是 List 類型的
        Cons(elem, Box::new(self))
    }

    // 返回鏈表的長度
    fn len(&self) -> u32 {
        // `self` 的類型是 `&List`, `*self` 的類型是 `List`,
        // 匹配一個類型 `T` 好過匹配一個引用 `&T`
        match *self {
            // 因為`self`是借用的，所以不能轉(zhuǎn)移 tail 的所有權(quán)
            // 因此使用 tail 的引用
            Cons(_, ref tail) => 1 + tail.len(),
            // 基本規(guī)則：所以空的鏈表長度都是0
            Nil => 0
        }
    }

    // 返回連鏈表的字符串表達(dá)形式
    fn stringify(&self) -> String {
        match *self {
            Cons(head, ref tail) => {
                // `format!` 和 `print!` 很像
                // 但是返回一個堆上的字符串去替代打印到控制臺
                format!("{}, {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }
}

代碼測試

fn main() {
    let mut list = List::new();

    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);

    println!("linked list has length: {}", list.len());
    println!("{}", list.stringify());
}

練習(xí)

基于以上代碼實現(xiàn)一個雙向循環(huán)鏈表。

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。循環(huán)鏈表是另一種形式的鏈?zhǔn)酱尜A結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。

下一篇：閉包的語法