单独链接列表,引用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原始指针.但是,更简单的解决方案是:

• 使用a 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>.