rust - 引用 Rust 中随机节点的单链表

Question

我正在尝试创建一个由节点组成的单向链表，每个节点都具有对下一个节点的引用、与该节点关联的数据，以及对列表中随机节点的引用，这很有趣。给定节点的随机节点可以出现在列表中节点本身之前或之后。随机节点是可选的。这是一个图表:

       +---------+  +-------------------+
       |         v  v                   |
     +-+--+     ++--++     +----+     +-+--+
+--->+Data+---->+Data+---->+Data+---->+Data|
     +-+--+     +----+     +--+-+     +----+
       ^                      |
       +----------------------+

该图演示了一个包含四个节点的列表。第一个节点的随机引用指向第二个节点。第二个节点的随机引用丢失。第三个节点的随机引用是第一个节点。第四个节点的随机引用指向第二个节点。

列表需要只支持添加新节点。添加一个节点后，它与列表的生命周期一样长，因此随机引用不会因删除节点而失效。

我尝试过的:

我卡在了绝对的开头——我无法弄清楚如何设计结构以及如何构建列表。这是我在与编译器搏斗了一段时间后最终得到的代码:

type NodePtr<'a, T> = Option<Box<Node<'a, T>>>;

pub struct Node<'a, T: 'a> {
    data: T,
    next: NodePtr<'a, T>,
    random: Option<&'a Node<'a, T>>,
}

pub struct List<'a, T: 'a> {
    root: NodePtr<'a, T>,
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn construct() {
        let mut list:List<i32> = List {root: Some(Box::new(Node {data: 5, next: None, random: None}))};
        let mut f: &mut Node<i32> = &mut **list.root.as_mut().unwrap();
        f.random = Some(&f);
    }
}

编译器拒绝编译它:

src/topology_copy.rs:21:26: 21:27 error: `f` does not live long enough
src/topology_copy.rs:21         f.random = Some(&f);

而且代码很乱。显然我做错了。

Answer 1

不幸的是，就编译器而言，您试图实现的目标本质上是不安全的，因为您正在为可变 节点创建别名。编译器可能会提示的两个问题:

• 没有证据表明节点不会移动，所以你引用的引用可能会失效
• 没有证据表明该节点不会发生变异，因此为其设置两个别名(并且能够将两个别名移交给它)会造成安全漏洞

---

现在呢？

有多种方法。如果您确定自己可以使用 unsafe和原始指针，例如。但是，更简单的解决方案是:

• 使用Vec存储节点和链接它们的索引
• 使用Rc和 Weak

前者是:

struct Node<T> {
    data: T,
    next: Option<usize>,
    random: Option<usize>,
}

pub struct List<T> {
    store: Vec<Node<T>>,
}

后者是:

struct Node<T> {
    data: T,
    next: Option<Rc<Node<T>>,
    random: Option<Weak<Node<T>>,
}

pub struct List<T> {
    head: Option<Rc<Node<T>>,
}

然而，后者不允许内部节点发生变化(因为存在固有的别名)，因此您可能需要包装 T进入RefCell<T> .