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

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两者都相当直截了当，尽管迭代地确定大小确实涉及一些“与借用检查器的斗争”。

接下来我想尝试添加一个 tail指向 LinkedList 的指针结构。启用高效的 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 它可能仍然会导致运行时崩溃......)。

最终，任何比普通单链表更复杂的链表都有一个所有权故事，该故事太复杂而无法安全有效地编码到 Rust 的所有权系统中(它不是树)。我个人倾向于接受此时的不安全性，并依靠单元测试来完成一件事情(为什么要写一个次优的数据结构......？)。