> For the complete documentation index, see [llms.txt](https://chapin666.gitbook.io/too-many-list-zh/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chapin666.gitbook.io/too-many-list-zh/yi-ge-zao-gao-dan-an-quan-de-shuang-xiang-dui-lie/gou-jian.md).

# 构建

好了，我们将从构建 list 开始。 对于这个新系统，这非常简单。 new 仍然微不足道，所有字段中都是 None。 另外，由于它有点笨拙，我们也来介绍一下 Node 构造函数：

```rust
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 }
    }
}
```

```rust
> cargo build

**A BUNCH OF DEAD CODE WARNINGS BUT IT BUILT**
```

耶！

现在让我们尝试写一下 push\_front。因为双向链表要复杂得多，我们需要做更多的工作。在单链表操作可以简化为单线程的情况下，双链表操作相当复杂。

特别是，我们现在需要特别处理一些与空列表有关的边界情况。大多数操作只触及头部或尾部指针。但是，当转换到空列表或从空列表转换时，我们需要同时编辑这两个列表。

要验证我们的方法是否有意义，一个简单的方法是我们保持以下不变量: 每个节点应该有两个指向它的指针。列表中间的每个节点由其前置节点和后续节点指向，而末端的节点则由列表本身指向。

让我们来试一试:

```rust
pub fn push_front(&mut self, elem: T) {
    // new node needs +2 links, everything else should be +0
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            // non-empty list, need to connect the 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
            // total: +2 new_head, +0 old_head -- OK!
        }
        None => {
            // empty list, need to set the tail
            self.tail = Some(new_head.clone());     // +1 new_head
            self.head = Some(new_head);             // +1 new_head
            // total: +2 new_head -- OK!
        }
    }
}
```

```rust
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"。*

[点击第一个链接](https://doc.rust-lang.org/std/cell/struct.RefCell.html)

> 具有动态检查借用规则的可变内存位置
>
> 有关更多信息，请参见[模块级文档](https://doc.rust-lang.org/std/cell/index.html)。

点击链接

> 可共享的可变容器。
>
> Cell 和 RefCell 类型的值可以通过共享引用（即常见的 \&T类型）进行更改，而大多数 Rust 类型只能通过唯一（\&mut T）引用进行更改。 我们说 Cell 和 RefCell 提供了“内部可变性”，而典型的Rust类型则表现出“继承的可变性”。
>
> Cell 类型有两种：Cell 和 RefCell 。 Cell 提供 get 和 set 方法，这些方法可以通过单个方法调用来更改内部值。 Cell 仅与实现 Copy 的类型兼容。 对于其他类型，必须使用 RefCell 类型，在进行更改之前获取写锁定。
>
> RefCell\<T> 使用Rust的生命周期来实现“动态借用”，这是一个可以请求对内部值进行临时、独占、可变访问的过程。RefCell\<T> 的借用是在“运行时”进行跟踪的，这与 Rust 的本机参考类型不同，后者在编译时是完全静态跟踪的。 由于RefCell\<T> 借用是动态的，因此可以尝试借用已经可变借用的值。 发生这种情况时，将导致线程崩溃。
>
> **什么时候选择内部易变性**

> 更常见的继承易变性是一个关键的语言元素，它使 Rust 能够对指针别名进行强有力的推理，静态地防止崩溃错误。因此，继承的易变性是首选，而内部的易变性则是最后的手段。由于 Cell 型使得可变可能被禁止，所以有时候内部可变可能是适当的，甚至必须使用，例如：
>
> * 将继承的可变性根源引入共享类型
> * 逻辑不可变方法的实现细节
> * 改变 Clone 的实现

> **将继承的可变性根源引入共享类型**
>
> 共享的智能指针类型（包括 Rc\<T> 和 Arc\<T> ）提供了可以在多方之间克隆和共享的容器。 由于包含的值可能是多重别名，因此只能借用它们作为共享引用，而不是可变引用。 没有 cell，根本不可能在共享盒内对数据进行修改！

> 在共享指针类型中加入 RefCell\<T> 来重新引入可变性是很常见的:
>
> ```rust
> 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);
> }
> ```
>
> 注意，这个例子使用 Rc\<T> 而不是 Arc\<T> 。RefCell\<T> 用于单线程方案。如果在多线程环境中需要共享可变性，请考虑使用 Mutex\<T> 。

嘿，Rust的文档仍然很棒。

我们关心的是这句话:

```rust
shared_map.borrow_mut().insert("africa", 92388);
```

特别是 borrow\_mut 这个词。看来我们需要明确地借用一个 RefCell。这个 "." 操作不会为我们做的。真奇怪。让我们试试：

```rust
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);
        }
    }
}
```

```rust
> cargo build

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

嘿，它构建成功了！ 文档再次胜利。