Singly linked list with references to random nodes in Rust

Question

I am trying to create a singly linked list composed of nodes each having a reference to the next node, data associated with the node and, this is the interesting bit, a reference to a random node in the list. The random node of a given node can appear before the node itself or after it in the list. The random node is optional. Here is a diagram:

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

The diagram demonstrates a list with four nodes. The random reference of the first node points to the second node. The second node's random reference is missing. The random reference of the third node is to the first one. The random reference of the forth node points to the second one.

The list needs to support only adding new nodes. Once a node has been added it lives as long as the list so random references cannot get invalidated by removing a node.

What I tried:

I am stuck at the absolute beginning - I cannot figure out how to design the struct and how to construct the list. Here is the code I ended up with after wrestling with the compiler for a while:

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);
    }
}

The compiles refuses to compile it with:

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

And the code is very messy. Obviously I am doing it wrong.

No, it's not. "Singly linked list with references to random nodes" is the best name I could come up with. — Svetlin Mladenov, Apr 07 '16 at 08:22
Possible duplicate of [Why can't I store a value and a reference to that value in the same struct?](http://stackoverflow.com/questions/32300132/why-cant-i-store-a-value-and-a-reference-to-that-value-in-the-same-struct) — oli_obk, Apr 07 '16 at 08:27
@ker: The issue is similar, however the recommended solution (not put the items in the same struct) does not hold for data structures I fear. — Matthieu M., Apr 07 '16 at 08:32

score 7 · Accepted Answer · answered Apr 07 '16 at 08:30

Unfortunately, what you are trying to achieve is inherently unsafe as far as the compiler is concerned because you are creating aliases to mutable nodes. Two possible issues that the compiler will complain about:

there is no proof that the node will not move, so the reference you take might be invalidated
there is no proof that the node will not be mutated, so having two aliases to it (and being able to hand over two aliases to it) create a safety hole

Now what?

There are various approaches. If you are sure of yourself you could use unsafe and raw pointers, for example. However, the simpler solutions would be:

use a Vec to store the nodes, and indexes to link them
use Rc and Weak

The former is:

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

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

And the latter would be:

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

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

the latter however will not allow mutation of the internal nodes (because there is inherent aliasing) so you may need to wrap the T into RefCell<T>.

Singly linked list with references to random nodes in Rust

1 Answers1

Linked