鏈表

鏈表簡介

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 由於不必須按順序存儲，鏈表在給定位置插入的時候可以達到O(1)的複雜度，比另一種線性表順序錶快得多，但是在有序數據中查找一個節點或者訪問特定下標的節點則需要O(n)的時間，而線性表相應的時間複雜度分別是O(logn)和O(1)。

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

下面看我們一步步實現鏈表：

定義鏈表結構

use List::*;

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

實現鏈表的方法

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

    // 在前面加一個元素節點，並且鏈接舊的鏈表和返回新的鏈表
    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`是借用的，所以不能轉移 tail 的所有權
            // 因此使用 tail 的引用
            Cons(_, ref tail) => 1 + tail.len(),
            // 基本規則：所以空的鏈表長度都是0
            Nil => 0
        }
    }

    // 返回連鏈表的字符串表達形式
    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());
}

練習

基於以上代碼實現一個雙向循環鏈表。

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。 循環鏈表是另一種形式的鏈式存貯結構。它的特點是表中最後一個結點的指針域指向頭結點，整個鏈表形成一個環。