Using Box<T> for Heap Allocation in Rust

WHY IT EXISTS: Rust requires the size of a type to be known at compile time to allocate space on the stack. This poses a problem for recursive types, like a linked list node that contains another node, which would have an infinite size. Heap allocation solves this by storing the data elsewhere and only keeping a fixed-size pointer on the stack.

THE MENTAL MODEL: Think of Box<T> as a cardboard box for your data. The data lives inside the box (on the heap), and you hold a receipt for it (the pointer on the stack). The receipt has a fixed size, no matter how big the box is. When the receipt is dropped (goes out of scope), the box and its contents are automatically destroyed and deallocated.

HOW IT WORKS: Box::new(value) allocates memory on the heap, moves the value into it, and returns a Box<T> smart pointer. This pointer owns the data. When the Box<T> goes out of scope, its destructor runs, freeing the heap memory. Because Box<T> is fundamentally a pointer, it has a known, fixed size. This allows it to be used inside a struct or enum to break an otherwise infinite size calculation.

WHEN TO USE IT: The primary use case is defining recursive data structures. It's also used to transfer ownership of large data across function boundaries to avoid expensive stack copies. Finally, it's used to create trait objects, which allow for dynamic dispatch.

WHEN NOT TO USE IT: Avoid Box<T> when stack allocation is sufficient, as heap allocation and dereferencing have a performance cost. Be extremely careful with Foreign Function Interface (FFI). While a Rust function returning Box<Foo> can be safely exposed to C as Foo*, you must never take a pointer allocated in C and wrap it in a Box<T>. The Box destructor will try to free memory using Rust's global allocator, which is undefined behavior for memory it doesn't own.

ONE CANONICAL EXAMPLE: A recursive linked list. A naive definition like enum List { Cons(i32, List), Nil } won't compile because List contains itself, implying an infinite size. The solution is to use a box: enum List { Cons(i32, Box<List>), Nil }. Now, the Cons variant stores an i32 and a pointer to the next List element. The size of Box<List> is known at compile time, so the compiler is satisfied.