012 通过链表学习Rust之持久化单链表

介绍

视频地址：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 ---+      

定义

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>,
}