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

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chapin666.gitbook.io/too-many-list-zh/yi-ge-zao-gao-dan-an-quan-de-shuang-xiang-dui-lie/gou-jian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.