[solved] What is the proper way to implement a cyclic data structure?


#1

Essentially I am trying to achieve:

struct Node {
    parent: &Node,
    children: Box<[Node]>,
}

The details are truthfully a little more complicated but that is essentially the minimum viable pseudocode to get my point across. Anyways, I have seen a few solutions via google search but most of these appear to be pre Rust 1.0. I’m wondering whether there is a recommended way to tackle cyclic data structures or whether it is instead something to be solved on a per-implementation basis.


#2

Why are you using Box<[Node]> over Vec<Node>?

Anyway, the correct way is probably to use

struct Node {
  parent: Weak<Node>,
  children: Vec<Rc<Node>>
}

Alternatively, allocate the nodes in a backing Vec arena and just store pointers to them.

But this is usually a per-implementation thing.


#3

if you want to make(implement) simple one-linked list just use enums


#4

He wants parent pointers though.


#5

You may want to look at Feedback on an isomorphic data structure


#6

https://github.com/SimonSapin/rust-forest illustrates three different ways to implement data structures like this.


#7

Thank you for all of the feedback. As Manishearth said earlier there appears to be a few good ways to do this depending on the particular problem.

To solve my particular issue I used the pattern outlined in:
http://people.mozilla.org/~lbergstrom/Korea2013/RustPatterns.pdf

This pattern is also implemented in:
https://github.com/rust-lang/rust/blob/master/src/libcollections/linked_list.rs