介绍

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

详细内容

在之前我们已经实现了一个单链表，从这节开始，我们将实现一个持久化的单链表。通过持久化的单链表，可以让其他人来共享使用链表的数据。

布局

考虑如下例子：

list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D

我们希望我们看到的内存布局是这样：

list1 -> A ---+
              |
              v
list2 ------> B -> C -> D
              ^
              |
list3 -> X ---+

因为我们链表中的B的所有权是共享的，所以我们不能像之前那样定义我们的链表了。
那我们怎么办喃？我们将使用Rc引用计数来实现我们的共享。

定义

我们将Box换成Rc重新定义我们的链表，代码如下：

use std::rc::Rc;

pub struct List<T> {
	head: Link<T>,
}

type Link<T> = Option<Rc<Node<T>>>;

struct Node<T> {
	elem: T,
	next: Link<T>,
}