Box<T> in Rust: heap and recursive types step by step

Box<T> is an owning pointer to the heap that stores a value.

In the early articles we learned the difference between Stack (fast, fixed size, ordered) and Heap (flexible, dynamic size, unordered).

By default, primitive types and structs in Rust are stored on the Stack. But what if we have a huge piece of data that we don’t want to copy constantly? Or what if we want to create a data structure that contains itself (like a linked list or a tree)?

That’s where Box<T> comes in.

Basic usage

fn main() {
    // The '5' is stored on the Heap. 'b' is a pointer on the Stack.
    let b = Box::new(5);

    println!("b = {}", b);
} // Here 'b' goes out of scope and Rust frees the heap memory automatically.

For all practical purposes, it’s used almost like the original value. Rust applies “automatic dereferencing” when you call methods, but if you want to access the raw value manually, you can use the dereference operator *.

let x = 5;
let b = Box::new(x); // Copies x to the Heap

assert_eq!(5, x);
assert_eq!(5, *b); // *b accesses the value inside the box

The problem with recursive types

Rust needs to know at compile time exactly how much space a data type occupies.

Imagine we want to create a Linked List (Cons List) in the Lisp style. A list is:

• Either a value and the rest of the list.
• Or Nil (end of the list).

// ❌ THIS DOES NOT COMPILE
enum Lista {
    Cons(i32, Lista),
    Nil,
}

Rust will try to calculate the size of Lista:

1. How much does Lista occupy? It depends on its variants.
2. Cons stores an i32 and… another Lista!
3. So size(Lista) = size(i32) + size(Lista).
4. size(Lista) = size(i32) + size(i32) + size(Lista)…
5. Result: Infinite size.

The compiler will give you the error: recursive type Lista has infinite size.

The solution: indirection with Box

We cannot put an infinite list inside another. But we can put a pointer to the next list.

We know how much a fine pointer like Box<Lista> occupies: a fixed size for each architecture (usually 8 bytes on 64-bit systems).

By wrapping the recursion in a Box, we break the infinite cycle.

// ✅ THIS DOES COMPILE
enum Lista {
    Cons(i32, Box<Lista>), // Now it's i32 + pointer
    Nil,
}

use crate::Lista::{Cons, Nil};

fn main() {
    // List: 1 -> 2 -> 3 -> Nil
    let lista = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));
}

Now the size calculation is: size(Lista) = size(i32) + size(Box). Finite and known.

Visually, instead of having nested objects like matryoshka dolls (which wouldn’t fit in memory), we have separate objects on the Heap, each with a “note” (pointer) saying where the next one is.

Unboxing

To work with data inside a Box (for example, in a match), we need to be careful with Ownership. Box owns the data, so we cannot simply take it out without breaking the box (unless we move it).

fn imprimir_lista(lista: Lista) {
    match lista {
        Cons(valor, siguiente_caja) => {
            println!("Valor: {}", valor);
            // 'siguiente_caja' is a Box<Lista>.
            // We can call ourselves recursively by passing the content of the Box.
            imprimir_lista(*siguiente_caja);
        },
        Nil => println!("Fin"),
    }
}

Note: By using *siguiente_caja we are moving the content out of the box into the recursive call. The original box is destroyed.