The idiomatic way to work with Rc<Refcell> in structures with nodes

[ndtoan96]

I am solving leetcode problems and sometimes see this struct:

struct ListNode {
    val: i32,
    next: Option<Rc<RefCell<ListNode>>>
}

So I tried to play with it but can't figure out a way to iterate to the end node. Let's say, for example, how to implement a push method that appends a value to the end of the linked list.

[alice]

One thing to keep in mind with that kind of structure is that when accessing a value behind a RefCell, you will be given access through a guard (a Ref or RefMut). You can only access stuff behind the guard while it still exists, and it has a destructor. This means that naively trying to iterate arbitrarily many nodes into the structure will fail, because each level produces another guard with a destructor, and the whole chain of guards must be alive for the naive approach to work.

To get around this, you can clone the Rc and then release the guard.

[ndtoan96]

How exactly to do that then? Sorry because I'm still quite new in rust and this is the first time I work with Rc and Refcell.

[alice]

If node is a Rc<RefCell<ListNode>>, then you can do this:

let next: Option<Rc<RefCell<ListNode>>> = node.borrow().next.clone();

The clone will only increment the ref-count of the node when the option is Some.

[Hyeonu]

Note that the next: Option<Rc<RefCell<ListNode>>> itself is not much idiomatic way to implement linked list in Rust. This type signature is prone to make circular reference and panic on runtime borrow check, and of course prevents efficient multuthreading. Try reimplement your solution with next: Option<Box<ListNode>>.

[ndtoan96]

Isn't the idiomatic way to implement linked list in rust is to define an enum:

enum LinkedList {
    Cons(val, Box(Node)),
    Nil
}

because in this case root and the next node of root has pretty much the same type, we don't have to deal with Option and it's possible for a null list.

[daboross]

That is indeed a singly-linked list, but it wouldn't have great performance. I recommend reading through this blog series if you haven't already: Introduction - Learning Rust With Entirely Too Many Linked Lists

[H2CO3]

If you use Option, it still has the same type. Option is also a regular enum, just like what you would have come up with. However, it has nice standard library support, and it expresses semantics ("the next node may or may not be there"). It's also non-intrusive: you can make next just a single field in your struct and store whatever else you want in other fields. While the other style (which is unfortunately overwhelmingly popular in the FP community) forces you to be intrusive and store everything inside the Cons variant.