# 布局

那么单链队列是什么样的呢？当我们有一个单链接的堆栈时，我们把它推到列表的一端，然后从同一端弹出。堆栈和队列之间的唯一区别是队列从另一端弹出。因此，从我们的堆栈实现中，我们可以看到:

```
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
```

为了建立队列，我们只需要决定移动到列表末尾的操作：push还是pop？因为我们的列表是单链的，我们实际上可以用同样的工作方式将任何一个操作移到最后。

要将 push 移动到结尾，我们只需要一直走到 None，并将新元素将其设置为 Some。

```
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
```

要将pop移到末尾，我们一直走到None之前的节点，然后取走：

```
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
```

我们今天就可以做到这一点，然后结束。但那会很糟糕！这两个操作都会遍历整个列表。有些人会认为这样的队列实现实际上是一个队列，因为它公开了正确的接口。不过，我保证接口的性能。我不关心精确的渐近界，只关心“快”与“慢”。队列保证了push和pop的速度很快，而遍历整个列表绝对不是很快。

一个关键的观察是，我们重复做同样的事情浪费了大量的工作。我们能记住这个工作吗？为什么，是的！我们可以存储一个指向列表末尾的指针，然后直接跳到那里！

事实证明，只有 push 和 pop 的一种反转才可以使用。 要反转 pop，我们必须将 “tail” 指针向后移动，但是由于我们的列表是单链链接，因此我们无法有效地做到这一点。 如果我们取反推，则只需向前移动 “head” 指针，这很容易。

让我们试试这个:

```rust
use std::mem;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

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

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // swap the old tail to point to the new tail
        let old_tail = mem::replace(&mut self.tail, Some(new_tail));

        match old_tail {
            Some(mut old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
            }
        }
    }
}
```

我现在将更详细地介绍隐含的细节，因为我们应该对这种事情很满意。 并不是说您一定一定希望在第一次尝试时就产生此代码。 我只是略过了我们之前必须处理的反复试验。 实际上，在编写此代码时我犯了很多错误，但我没有显示出来。 您只能看到我离开 mut 或 ; 如此反复才停止启发性。 不用担心，我们还会看到许多其他错误消息！

```rust
> cargo build

error[E0382]: use of moved value: `new_tail`
  --> src/fifth.rs:38:38
   |
26 |         let new_tail = Box::new(Node {
   |             -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 |         let old_tail = mem::replace(&mut self.tail, Some(new_tail));
   |                                                          -------- value moved here
...
38 |                 old_tail.next = Some(new_tail);
   |                                      ^^^^^^^^ value used here after move
```

> 使用 move value: new tail

没有实现 Copy，所以我们不能把它分配到两个位置。更重要的是，Box 拥有它所指向的东西，并且会在它 drop 时释放它。如果我们编译了 push 实现，我们就可以双倍释放列表的尾部了！实际上，正如我们所写的那样，我们的代码会在每次推送时释放 old\_tail。哎呀！

好吧，我们知道如何制作一个非所有权指针。 那只是参考！

```rust
pub struct List<T> {
    head: Link<T>,
    tail: Option<&mut Node<T>>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

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

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
                old_tail.next.as_mut().map(|node| &mut **node)
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
                self.head.as_mut().map(|node| &mut **node)
            }
        };

        self.tail = new_tail;
    }
}
```

这里没有什么棘手的问题。 与之前的代码相同的基本思想，不同之处在于，无论使用什么填充实际Box的位置，我们都使用一些隐式的返回善意来提取尾部引用。

```rust
> cargo build

error[E0106]: missing lifetime specifier
 --> src/fifth.rs:3:18
  |
3 |     tail: Option<&mut Node<T>>, // NEW!
  |                  ^ expected lifetime parameter
```

哦，对了，我们需要在类型生命周期中提供引用。 嗯...这个引用的生命周期是多少？ 好吧，这看起来像IterMut，对吗？ 让我们尝试一下为IterMut做的事情，然后添加一个通用的 'a：

```rust
pub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

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

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
                old_tail.next.as_mut().map(|node| &mut **node)
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
                self.head.as_mut().map(|node| &mut **node)
            }
        };

        self.tail = new_tail;
    }
}
```

```rust
cargo build

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/fifth.rs:35:27
   |
35 |                 self.head.as_mut().map(|node| &mut **node)
   |                           ^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
  --> src/fifth.rs:18:5
   |
18 | /     pub fn push(&mut self, elem: T) {
19 | |         let new_tail = Box::new(Node {
20 | |             elem: elem,
21 | |             // When you push onto the tail, your next is always None
...  |
39 | |         self.tail = new_tail;
40 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/fifth.rs:35:17
   |
35 |                 self.head.as_mut().map(|node| &mut **node)
   |                 ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
  --> src/fifth.rs:13:6
   |
13 | impl<'a, T> List<'a, T> {
   |      ^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut fifth::Node<T>>
              found std::option::Option<&mut fifth::Node<T>>
```

哇，这是一个非常详细的错误消息。这有点令人担忧，因为这意味着我们正在做一些真正混乱的事情。这里有一个有趣的部分:

> 必须在 impl 上定义有效生命周期 'a

我们借用了self，但是编译器希望我们能持续到 'a，如果我们告诉它self能持续那么长时间呢。。？

```rust
    pub fn push(&'a mut self, elem: T) {
```

```
cargo build

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

哦，嘿，成功了! 太好了！

让我们也做一下 pop 吧:

```rust
pub fn pop(&'a mut self) -> Option<T> {
    // Grab the list's current head
    self.head.take().map(|head| {
        let head = *head;
        self.head = head.next;

        // If we're out of `head`, make sure to set the tail to `None`.
        if self.head.is_none() {
            self.tail = None;
        }

        head.elem
    })
}
```

并为此写一个快速测试:

```rust
mod test {
    use super::List;
    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop(), None);

        // Populate list
        list.push(1);
        list.push(2);
        list.push(3);

        // Check normal removal
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push(4);
        list.push(5);

        // Check normal removal
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);
    }
}


```

```rust
cargo test

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:68:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
68 |         list.push(1);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:69:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
69 |         list.push(2);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:70:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
70 |         list.push(3);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here


....

** WAY MORE LINES OF ERRORS **

....

error: aborting due to 11 previous errors

```

🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀

我的天啊。

编译器对我们所有人的呕吐没有错。我们刚犯了一个主要的Rust罪过：我们在自己的内部存储了对自己的引用。 不知何故，我们设法说服了Rust，这在我们的push和pop实施中是完全合理的（我们确实为之震惊）。 我相信原因是Rust不能仅仅通过 push 和 pop 来告诉引用是对我们自己的引用，或者更确切地说，Rust根本没有这个概念。 引用失败的行为只是一种新出现的行为。

一旦我们尝试使用我们的列表，一切都会很快崩溃。 当我们调用push或pop时，我们会立即在自己中存储对自己的引用并陷入困境。 我们实际上是在借用自己。

我们的 pop 实现提示了为什么这可能是非常危险的：

```rust
// ...
if self.head.is_none() {
    self.tail = None;
}
```

如果我们忘记这样做怎么办？ 然后，我们的尾巴将指向已从列表中删除的某个节点。 这样的节点将立即释放，并且我们将有一个悬空的指针，Rust应该保护它免受攻击！

的确，Rust 正在保护我们远离那种危险，只是以一种非常... 迂回的方式。

那么我们能做什么呢? 回到 Rc\<refcell> 地狱？

求你了不要。

相反，我们将偏离正轨，使用原始指针。我们的布局将是这样的：

```rust
pub struct List<T> {
    head: Link<T>,
    tail: *mut Node<T>, // DANGER DANGER
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

```

就是这样。 这些无聊的引用计数动态借阅检查都是胡说八道！ 真实。 硬。 未检查的指针。

让我们成为C。 让我们整天成为C。

我回来了，我准备好了。

Hello unsafe。


---

# Agent Instructions: 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-bu-an-quan-de-dui-lie/bu-ju.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.