4.1 数据布局
原文链接: https://rust-unofficial.github.io/too-many-lists/fourth-layout.html
我们设计的关键是 RefCell 类型。RefCell 的核心是一对方法：
1
2
| fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;
|
borrow 和 borrow_mut 的规则与 & 和 &mut 完全相同：你可以随意调用 borrow，但 borrow_mut 需要独占访问。
RefCell 不是在编译期强制执行这些规则，而是在运行时强制执行。如果你违反了规则，RefCell 会直接 panic 并让程序崩溃。为什么它要返回这些 Ref 和 RefMut 呢？嗯，它们基本上就像用于借用的 Rc。它们还会在离开作用域之前一直保持 RefCell 处于借用状态。我们稍后再讲这个。
有了 Rc 和 RefCell，我们就能成为……一种极其啰嗦、处处可变、却无法回收循环引用的垃圾回收语言！耶——
好了，我们想要的是双向链表。这意味着每个节点都有指向前一个和后一个节点的指针。此外，链表本身还有指向第一个和最后一个节点的指针。这样我们就能在列表的两端快速插入和删除。
所以我们大概需要这样的结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| use std::rc::Rc;
use std::cell::RefCell;
pub struct List<T> {
head: Link<T>,
tail: Link<T>,
}
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
elem: T,
next: Link<T>,
prev: Link<T>,
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| > cargo build
warning: field is never used: `head`
--> src/fourth.rs:5:5
|
5 | head: Link<T>,
| ^^^^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `tail`
--> src/fourth.rs:6:5
|
6 | tail: Link<T>,
| ^^^^^^^^^^^^^
warning: field is never used: `elem`
--> src/fourth.rs:12:5
|
12 | elem: T,
| ^^^^^^^
warning: field is never used: `next`
--> src/fourth.rs:13:5
|
13 | next: Link<T>,
| ^^^^^^^^^^^^^
warning: field is never used: `prev`
--> src/fourth.rs:14:5
|
14 | prev: Link<T>,
| ^^^^^^^^^^^^^
|
嘿，编译通过了！虽然有很多死代码警告，但编译通过了！我们来试着用一下。