002 通過連結清單學習Rust筆記之連結清單布局

介紹

視訊位址：https://www.bilibili.com/video/av78062009/

相關源碼：https://github.com/anonymousGiga/Rust-link-list

Rust中最常見的連結清單

用函數式的文法定義一個連結清單如下：

List a  = Empty | Elem a (List a)      

一個連結清單要麼是空的類型，要麼是一個值後面跟着一個連結清單,這種被稱為遞歸定義類型，表示為和類型。Rust中的enum就是類型系統的和類型。是以最常見的Rust的連結清單的定義如下：

#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

fn main() {
    let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
    println!("{:?}", list);
}      

說明,上面的方式是通過枚舉實作，實際上是：

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}      

存在的問題

但是，上面這種是一個非常不好的連結清單定義。

考慮一個包含兩個元素的連結清單，如下：

//第一種布局，也是我們上面的布局
[] = stack //表示配置設定在棧上
() = heap  //表示配置設定在堆上
[Elem A, ptr] -> (Elem B, ptr) -> (Empty, junk）      

這個方式存在兩個問題：

• 元素A是配置設定在棧上而不是配置設定在堆上的；
• 最後的空元素需要配置設定空間。

1、占用多餘的空間

我們再考慮下面的布局：

//第二種布局
[ptr] -> (Elem A, ptr) -> (Elem B, null)      

後面這種布局的最後一個空沒有配置設定一個節點的空間。

2、便于拆分

在一種布局中，第一個節點沒有在堆上配置設定，這也是不太好的，可能在push、pop的時候沒有太大影響，但是在拆分連結清單的時候影響就比較大了。

考慮以下例子的拆分：

第一種布局:

[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)

split off C:

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)

[Elem C, ptr] -> (Empty *junk*)

第二種布局:

[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)

split off C:

[ptr] -> (Elem A, ptr) -> (Elem B. *null*)

[ptr] ->(Elem C, *null*)      

布局2的拆分隻需複制B在棧中存放的指針，然後null将舊的的值替換掉就可以了。布局1則必須将C從堆記憶體拷貝到棧記憶體。

連結清單的合并則是連結清單拆分的相反的過程。

**連結清單的一個比較好的特性就是，我們可以在節點本身進行構造元素，然後在不移動它（節點本身）的情況下，自由的在連結清單中移動它。**連結清單的特性如下面的示意圖：

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-aeyjQ9Gt-1630653384240)(F9EC93015194433981E8BB6FF5DF16BF)]

在上圖中，我們删除中間的節點，我們對中間節點本身的資料并沒有影響，隻是修改了第一個節點的next指針指向的位址，即未移動節點本身而實作在節點在連結清單中的移動。

很明顯，上面的第一種布局方式破壞了連結清單的此特性。

更複雜的枚舉

那我們是否可以定義成如下方式：

pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}      

通過此定義，我們可以節省最後一個空元素的空間。但是，這會更複雜，原因就是enum的本身的布局為如下：

//考慮如下枚舉類型
enum Foo {
    A(u32),
    B(u64),
    C(u8),
}
//其布局如下
struct FooRepr {
    data: u64, // 根據tag的不同，這一項可以為u64，u32，或者u8
    tag: u8, // 0 = A, 1 = B, 2 = C
}      

即使是使用上述的枚舉類型表示空，因為tag的原因，不能使用空指針優化（參考Rust死靈書：如果一個枚舉類型隻包含一個單值變量（比如 None）和一個（級聯的）非 null 指針變量（比如 &T），那麼 tag 其實是不需要的）。

c風格的連結清單

通過上面的分析，我們會發現，我們其實需要的是一個類似于在c語言中實作的連結清單。

我們把List定義成如下：

#[derive(Debug)]
pub struct Node {
  elem: i32,
  next: List,
}

#[derive(Debug)]
pub enum List {
  Empty,
  More(Box<Node>),
}

fn main() {
  let node1 = Node { elem: 1, next: List::Empty};
  let list = Box::new(node1);
  println!("{:?}", list);
}      

#[derive(Debug)]
pub struct List{
    head: Link,
}

#[derive(Debug)]
enum Link {
    Empty,
    More(Box<Node>),
}

#[derive(Debug)]
struct Node {
    elem: i32,
    next: Link,
}

fn main() {
    let node1 = Node { elem: 1, next: Link::Empty};
    let list = List {head: Link::More(Box::new(node1))};
    println!("{:?}", list);
}