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

help
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 Likes
3

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

4

He wants parent pointers though.

1 Like
5

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

6

GitHub - SimonSapin/rust-forest: A tree of reference-counted nodes, with `RefCell` for mutability 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

8

Those links seem to be broken now (as of 7/3/2021). Are there any updated links for those resources?

1 Like
9

The linked_list.rs has since moved here: https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/linked_list.rs

The paper seems to be available here: RUST PATTERNS. Lars Bergstrom Mozilla Research - PDF Free Download

10

That paper predates stable Rust, and uses an older, pre-stable syntax as well. If you're looking for some practical resources, I would recommend finding something newer. Maybe Introduction - Learning Rust With Entirely Too Many Linked Lists . (If you do read the paper, you'll at least need to know that Box<T> used to be spelt ~T.)

1 Like