链表中 "next" 指针的惯用生命周期是多少？

Question

我正在尝试创建一个简单的简单链表 type class 其中我有一个指向下一个节点的指针，但是运行一些问题。这样做的正确方法是什么？

我目前拥有的是：

trait Base {
    fn connect<'a, 'b>(&'a self, next: &'b Base);
}

struct MyStruct<'b> {
    next: Option<&'b Base>, // This should be swapped out with a reference to Base for the next node
}

impl<a', b'> Base for MyStruct<'b> {
    pub fn new() -> MyStruct<'b'> {
        MyStruct { next: None, }
    }

    pub fn connect<'a, 'b>(&'a self, layer: &'b Base) {
        self.next = Some(layer);
    }
}

我描绘连接的 struct/node 的生命周期的方式应该与初始节点相同（即，当我释放一个列表时，它应该完全这样做）所以它应该有一生。但是，我相信当连接函数中存在自指针时，这会导致问题。

Answer 1

你说

I have a pointer to the next node

你的代码显示了一个引用，而不是一个指针，所以我认为你的意思是一个引用。但你也说

when I deallocate a list it should do so entirely

这两个概念不相容。唯一可以掉落物品的是拥有该物品的东西。这是通过放弃所有权而不是其他任何人获得所有权来完成的。有了参考，您不拥有任何东西，您只是在借用它。

现在，您可以拥有指向下一项的指针。那是一个 Box，代表堆分配的项目。然后没有生命周期需要发挥作用，并在 .

中涵盖

这种类型的列表是通用的，因此您可以像 String 那样存储拥有的项目，或者像 &u32 这样的引用。当列表或列表节点被删除时， String 也会被删除。从技术上讲，引用已被删除，但删除引用确实不会删除所引用的项目。

创建一个仅引用下一个节点的链表是......至少可以说是棘手的，而且可能没有用。

您的 Node 看起来像这样：

struct Node<'a> {
    next: Option<&'a mut Node<'a>>,
}

您必须自己声明和分配每个 Node，因为您无法从假设的 "add" 内部将 Node 存储在堆栈上方法。

您总是会运行遇到一个问题，即对下一个节点的引用和下一个节点具有的生命周期重叠的生命周期（对列表应用归纳法，它会变得非常复杂。）

TL;DR 不清楚为什么要这样做，但基本上不容易做到（或值得，在我的意见）。

链表中 "next" 指针的惯用生命周期是多少？

What is the idiomatic lifetime for the "next" pointer in a linked list?

linked-list

rust