Understanding Rc and RefCell in Rust

March 22, 2025, 10:01 AM

rust

programming

data-structures

Rust's memory management model is one of its most powerful features, but it also presents unique challenges for beginners. Unlike languages with garbage collection, Rust enforces strict ownership and borrowing rules at compile time. However, there are cases where we need more flexibility—especially when dealing with tree structures or graphs where multiple owners of a value exist. This is where Rc<T> (Reference Counting) and RefCell<T> (Interior Mutability) come in (i'd leave some references to the rust docs/book at the bottom of the post).

In this post, i'll break down Rc and RefCell using a real-world example: building a tree from a list of parent-child relationships.

The Challenge: Building a Tree from a Graph

Consider a tree structure where each node has a value and can have multiple children. In Rust, we need to manage ownership correctly so that parent nodes can own their children while ensuring children don't get dropped prematurely.

Let's say we have a list of edges representing a tree:

let graph = vec![(0, 1), (0, 2), (1, 3), (3, 4)];

This represents a hierarchy where 0 is the root, 0 has children 1 and 2, and so on. The challenge is converting this into an actual tree structure.

Why Can't We Use Plain Structs?

A naive approach might define a Node struct with a Vec<Node> for children:

struct Node {
    value: i8,
    children: Vec<Node>,
}

However, this runs into ownership issues. When a node is part of Vec<Node>, it is owned by the vector. If another parent wants to reference the same child, Rust's ownership rules won't allow it.

Solution: Using Rc and RefCell

We solve this problem by:

Wrapping Node in Rc<T> (Reference Counting) to allow multiple owners.
Using RefCell<T> (Interior Mutability) to allow modifying the children inside an immutable Rc<Node>.

Final Implementation

use std::{cell::RefCell, collections::HashMap, rc::Rc};

struct Node {
    #[allow(unused)]
    value: i32,
    children: Vec<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(value: i32) -> Rc<RefCell<Self>> {
        return Rc::new(RefCell::new(Node {
            value,
            children: vec![],
        }));
    }

    fn adopt(&mut self, node: Rc<RefCell<Node>>) {
        self.children.push(node);
    }

    fn depth(node: &Node, level: i32) -> i32 {
        if node.children.len() == 0 {
            return level;
        }

        return node
            .children
            .iter()
            .map(|node| Node::depth(&node.borrow(), level + 1))
            .max()
            .unwrap_or(level);
    }

    fn len(&self) -> i32 {
        return Node::depth(self, 0);
    }
}

fn arr_notation_to_nodes(graph: Vec<(i32, i32)>) -> Rc<RefCell<Node>> {
    let mut map: HashMap<i32, Rc<RefCell<Node>>> = HashMap::new();

    for (parent, child) in &graph {
        let parent_node = map
            .entry(*parent)
            .or_insert_with(|| Node::new(*parent))
            .clone();
        let child_node = map
            .entry(*child)
            .or_insert_with(|| Node::new(*child))
            .clone();

        parent_node.borrow_mut().adopt(child_node);
    }

    return map[&graph[0].0].clone();
}

fn main() {
    let graph: Vec<(i32, i32)> = vec![(0, 1), (0, 2), (1, 3), (3, 4)];
    let root = arr_notation_to_nodes(graph);
    let depth = root.borrow().len();
    println!("The length of the array is {depth}");
}

Breaking Down the Solution

1. `Rc<T>` for Shared Ownership

Rc<T> (Reference Counting) allows multiple parts of our program to share ownership of a Node. This is essential because child nodes can have multiple references in different parent nodes.

Rc::new(RefCell::new(Node { value, children: vec![] }))

Each node is wrapped inside Rc so that it can be cloned and shared without moving ownership.

2. `RefCell<T>` for Interior Mutability

Since Rc<T> only allows shared ownership and doesn't support mutation, we wrap the Node inside RefCell<T>. This lets us mutate the children of a node even if it's wrapped in an Rc<T>.

parent_node.borrow_mut().adopt(child_node);

Here, .borrow_mut() gives us a mutable reference to modify the children vector.

3. Building the Tree

The function arr_notation_to_nodes creates nodes only if they don't already exist in the HashMap. Then it establishes parent-child relationships by calling adopt().

Why This Works in Rust

Without Rc<RefCell<Node>>, Rust's strict ownership model would make it impossible to have multiple references to the same child node. Rc allows multiple owners, and RefCell enables interior mutability while keeping the borrow checker happy.

Summary

Rc<T> enables shared ownership of a value.
RefCell<T> allows interior mutability.
Rc<RefCell<T>> together let us build tree structures with dynamically changing children.
This pattern is useful for graphs, trees, and scenarios where multiple owners need mutable access.

If you're new to Rust (like me), Rc and RefCell might seem complex at first, but once you understand their purpose, they become invaluable tools. The key take-away is that they provide flexibility while maintaining Rust's memory safety guarantees.