4.2 构建

3 分钟阅读

原文链接: https://rust-unofficial.github.io/too-many-lists/fourth-building.html

好了，我们从构建链表开始。在这个新系统下这相当直接。new 仍然很简单，只需把所有字段设为 None。另外，因为代码开始变得有点臃肿，我们也把 Node 的构造函数单独拆出来：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }
}

1
2
3
> cargo build

**一大堆死代码警告，但编译通过了**

好耶！

现在我们来试着实现向链表前端压入元素。因为双向链表明显复杂得多，我们需要做更多工作。单链表操作可以简化成一行，而双向链表操作则相当复杂。

特别是，我们现在需要特别处理一些与空链表相关的边界情况。大多数操作只会触及 head 或 tail 指针。然而，当从空链表转入或转出时，我们需要同时修改这两个指针。

验证我们的方法是否合理的一个简单方法是维持以下不变量：每个节点应该恰好有两个指向它的指针。链表中间的每个节点都被其前驱和后继指向，而两端的节点则由链表本身指向。

我们来试试看：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub fn push_front(&mut self, elem: T) {
    // 新节点需要 +2 个链接，其他一切应该 +0
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            // 非空链表，需要连接 old_head
            old_head.prev = Some(new_head.clone()); // +1 new_head
            new_head.next = Some(old_head);         // +1 old_head
            self.head = Some(new_head);             // +1 new_head, -1 old_head
            // 总计：+2 new_head, +0 old_head -- OK!
        }
        None => {
            // 空链表，需要设置 tail
            self.tail = Some(new_head.clone());     // +1 new_head
            self.head = Some(new_head);             // +1 new_head
            // 总计：+2 new_head -- OK!
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
cargo build

error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:39:26
   |
39 |                 old_head.prev = Some(new_head.clone()); // +1 new_head
   |                          ^^^^ unknown field

error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:40:26
   |
40 |                 new_head.next = Some(old_head);         // +1 old_head
   |                          ^^^^ unknown field

好吧。编译器报错了。不错的开始。不错的开始。

为什么我们不能访问节点上的 prev 和 next 字段？之前只有 Rc<Node> 的时候是可以的。看起来 RefCell 在碍事。

我们大概应该查一下文档。

Google 搜索 “rust refcell”

点击第一个链接

A mutable memory location with dynamically checked borrow rules
See the module-level documentation for more.

点击链接

Shareable mutable containers.
Values of the Cell<T> and RefCell<T> types may be mutated through shared references (i.e. the common &T type), whereas most Rust types can only be mutated through unique (&mut T) references. We say that Cell<T> and RefCell<T> provide ‘interior mutability’, in contrast with typical Rust types that exhibit ‘inherited mutability’.
Cell types come in two flavors: Cell<T> and RefCell<T>. Cell<T> provides get and set methods that change the interior value with a single method call. Cell<T> though is only compatible with types that implement Copy. For other types, one must use the RefCell<T> type, acquiring a write lock before mutating.
RefCell<T> uses Rust’s lifetimes to implement ‘dynamic borrowing’, a process whereby one can claim temporary, exclusive, mutable access to the inner value. Borrows for RefCell<T>s are tracked ‘at runtime’, unlike Rust’s native reference types which are entirely tracked statically, at compile time. Because RefCell<T> borrows are dynamic it is possible to attempt to borrow a value that is already mutably borrowed; when this happens it results in thread panic.
When to choose interior mutability
The more common inherited mutability, where one must have unique access to mutate a value, is one of the key language elements that enables Rust to reason strongly about pointer aliasing, statically preventing crash bugs. Because of that, inherited mutability is preferred, and interior mutability is something of a last resort. Since cell types enable mutation where it would otherwise be disallowed though, there are occasions when interior mutability might be appropriate, or even must be used, e.g.
Introducing inherited mutability roots to shared types.
Implementation details of logically-immutable methods.
Mutating implementations of Clone.
Introducing inherited mutability roots to shared types
Shared smart pointer types, including Rc<T> and Arc<T>, provide containers that can be cloned and shared between multiple parties. Because the contained values may be multiply-aliased, they can only be borrowed as shared references, not mutable references. Without cells it would be impossible to mutate data inside of shared boxes at all!
It’s very common then to put a RefCell<T> inside shared pointer types to reintroduce mutability:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    shared_map.borrow_mut().insert("africa", 92388);
    shared_map.borrow_mut().insert("kyoto", 11837);
    shared_map.borrow_mut().insert("piccadilly", 11826);
    shared_map.borrow_mut().insert("marbles", 38);
}
Note that this example uses Rc<T> and not Arc<T>. RefCell<T>s are for single-threaded scenarios. Consider using Mutex<T> if you need shared mutability in a multi-threaded situation.

嘿，Rust 的文档依然非常棒。

我们关心的核心内容是这一行：

1
shared_map.borrow_mut().insert("africa", 92388);

特别是那个 borrow_mut。看来我们必须显式借用 RefCell。. 运算符不会替我们完成这件事。奇怪。我们来试试：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
pub fn push_front(&mut self, elem: T) {
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            old_head.borrow_mut().prev = Some(new_head.clone());
            new_head.borrow_mut().next = Some(old_head);
            self.head = Some(new_head);
        }
        None => {
            self.tail = Some(new_head.clone());
            self.head = Some(new_head);
        }
    }
}

1
2
3
4
5
6
7
8
9
> cargo build

warning: field is never used: `elem`
  --> src/fourth.rs:12:5
   |
12 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

嘿，编译通过了！文档再次获胜。

最后修改 August 23, 2026: 更新 (499855b16)