How to Build Recursive Data Structures in Rust (Linked Lists, Trees)

Memory/Ownership
2026-04-17T16:43:47+00:00
You cannot define recursive data structures using `struct` directly because Rust requires all types to have a known, finite size at compile time.

You cannot define recursive data structures using struct directly because Rust requires all types to have a known, finite size at compile time. Instead, you must wrap the recursive field in a pointer type like Box<T> or Rc<T> to move the data to the heap, or use Option to handle the base case of the recursion.

Here is a practical implementation of a singly linked list using Box for ownership and Option to terminate the recursion:

#[derive(Debug)]
enum List {
    Cons(i32, Box<List>),
    Nil,
}

fn main() {
    let list = List::Cons(1, Box::new(
        List::Cons(2, Box::new(
            List::Cons(3, Box::new(List::Nil))
        ))
    ));
    
    println!("{:?}", list);
}

In this example, List is an enum with two variants: Cons holds a value and a pointer to the next node, while Nil represents the empty end of the list. The Box<List> ensures the recursive List is allocated on the heap, giving the compiler a fixed size for the Cons variant itself.

For trees where multiple nodes might share ownership (like a graph or a tree with shared subtrees), use Rc (Reference Counting) instead of Box. If you need interior mutability (e.g., modifying a node without borrowing the whole tree), combine Rc with RefCell:

use std::rc::Rc;
use std::cell::RefCell;

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

fn main() {
    let leaf = Rc::new(RefCell::new(Node {
        value: 42,
        children: vec![],
    }));

    let root = Rc::new(RefCell::new(Node {
        value: 10,
        children: vec![Rc::clone(&leaf)],
    }));

    // Access and modify safely
    let mut leaf_ref = leaf.borrow_mut();
    leaf_ref.value = 100;
}

Avoid using raw pointers (*mut T) unless you are writing unsafe code for performance-critical systems, as they bypass Rust's safety guarantees. Stick to Box for simple ownership chains and Rc<RefCell<T>> for shared, mutable recursive structures. This pattern keeps your code safe while allowing infinite depth in theory, limited only by heap memory.