002 通过链表学习Rust笔记之链表布局

介绍

视频地址:www.bilibili.com/video/av78062009/
相关源码:github.com/anonymousGiga/Rust-link...

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从堆内存拷贝到栈内存。
链表的合并则是链表拆分的相反的过程。

链表的一个比较好的特性就是,我们可以在节点本身进行构造元素,然后在不移动它(节点本身)的情况下,自由的在链表中移动它。链表的特性如下面的示意图:
链表删除示意图
在上图中,我们删除中间的节点,我们对中间节点本身的数据并没有影响,只是修改了第一个节点的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);
}

我们必须要将Node设置为public才能正确运行,但是在实际情况下我们更倾向于将Node设置private。因此我们进一步演进如下:

#[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);
}

至此,我们基本上得到了一个我们相对满意的链表的布局!

本作品采用《CC 协议》,转载必须注明作者和本文链接
令狐一冲
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
文章
255
粉丝
119
喜欢
308
收藏
128
排名:335
访问:2.8 万
私信
所有博文
社区赞助商