用尾指针编写链表的惯用方法是什么？

Question

作为 Rust 的学习项目，我有一个非常简单（工作，如果不完整）的单链表实现。结构的声明如下所示：

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

struct Node<T> {
    data: T,
    next: NodePtr<T>,
}

pub struct LinkedList<T> {
    head: NodePtr<T>,
}

实施 size 和 push_front 都相当简单，尽管迭代地执行大小确实涉及一些 "fighting with the borrow checker."

接下来我想尝试的是添加一个指向 LinkedList 结构的 tail 指针。启用高效的 push_back 操作。在这里，我运行有点撞墙了。起初我尝试使用 Option<&Box<Node<T>>> 然后 Option<&Node<T>>。这两者都导致 'a 到处都是，但最终仍然无法向生命周期检查器保证 tail 是有效的。

从那以后我得出了初步的结论，即这些定义是不可能的：没有办法向编译器保证 tail 是有效的在我认为有效的地方。我能做到这一点的唯一方法是让我所有的指针都是 Rc<_> 或 Rc<RefCell<_>>，因为这是让两个东西指向同一个对象（最终节点）的唯一安全方法。

我的问题：这是正确的结论吗？更一般地说：数据结构中无主指针的惯用 Rust 解决方案是什么？在我看来，对于如此简单的事情，引用计数似乎太过沉重，所以我想我一定遗漏了一些东西。（或者也许我只是还没有进入正确的内存安全思维模式。）

Answer 1

是的，如果你想写一个带有尾指针的单链表，你有三个选择：

安全且可变：使用 NodePtr = Option<Rc<RefCell<Node<T>>>>
安全且不可变：使用 NodePtr = Option<Rc<Node<T>>>
不安全且可变：使用 tail: *mut Node<T>

*mut 会更有效率，而且 Rc 实际上不会防止你产生完全无意义的状态（正如您正确推断的那样）。它只是保证它们不会导致段错误（并且使用 RefCell 它仍然可能导致运行时崩溃......）。

最终，任何比 vanilla 单链更复杂的链表都有一个所有权故事，该故事太复杂而无法在 Rust 的所有权系统中安全有效地编码（它不是树）。我个人更喜欢在这一点上拥抱不安全并依靠单元测试来完成一件事情（为什么要写一个次优的数据结构......？）。

用尾指针编写链表的惯用方法是什么？

What is the idiomatic way to write a linked list with a tail pointer?

linked-list

reference-counting

rust