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

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都是相当直接的，尽管反复实施size确实涉及到一些“与借阅检查人的斗争”

我想尝试的下一件事是向LinkedList结构添加一个尾部指针。以启用有效的push_back操作。在这里，我碰到了一堵墙。起初我试图使用选项

从那以后，我得出了一个初步的结论，这些定义是不可能的：没有办法向编译器保证尾巴在我认为有效的地方是有效的。我唯一能做到这一点的方法是让我所有的指针都是Rc

我的问题：这是正确的结论吗？更一般地说：数据结构中无主指针的惯用解决方案是什么？在我看来，对于这么简单的事情来说，引用计数似乎非常重要，所以我想我一定错过了什么。（或者我只是还没有进入记忆安全的正确思维模式。）




Answer 1

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

• 安全且可变：使用NodePtr=选项

*mut将更有效，而且它不像Rc实际上会阻止你产生完全无意义的状态（正如你正确推断的那样）。它只是要保证它们不会导致SEGFULTS（而对于RefCell，它仍然可能导致运行时崩溃…）。

最终，任何比香草单链接更复杂的链表都有一个过于复杂的所有权故事，无法安全有效地编码到Rust的所有权系统中（它不是树）。我个人倾向于在这一点上接受不安全，并依靠单元测试来完整地到达终点线（为什么要编写一个次优的数据结构...？）。