CODEWITHSUNDEEP
listdata-structuresrustdigraphs
porton
porton

Reputation: 5805

List with references to its elements

I need to hold a list of nodes (strings) and have a "current" node (or more generally current nodes).

I would use a vector and current nodes specified by indexes, but sometimes a node is removed from the list, this silently invalidates the index, what is not acceptable.

So, I want to represent it as a reference counted digraph: the list is a path in the digraph (with only a single parent per node). When I add a new current node, I add a new parent and reference a node in the list increasing its reference count.

Now I doubt which data structure in Rust to use:

pub struct DigraphNode<T> {
    pub next: DigraphNodeRef<T>, // I made it `pub` to be able `item.next.next()` to remove an item from the middle.
    data: T,
}

pub struct DigraphNodeRef<T> {
    rc: Rc<DigraphNode<T>>,
}

seems a right solution at first, but how then to represent the empty digraph (an empty list of strings)? (Rc can't hold zero strong references.)

Upvotes: 0

Views: 147

Answers (0)

Related Questions