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

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的所有权系统(它不是一棵树).我个人赞成在这一点上接受不安全的事情,并依靠单元测试来完成一个终点线(为什么写一个次优的数据结构......？).