In this lesson, you will learn how to define generic data structures that reference themselves while ensuring the compiler can calculate their memory size.
The Stack Safety Challenge
In Rust, the compiler must know the exact size of every type at compile time. If you try to define a recursive struct directly, like this:
struct Node<T> {
value: T,
next: Node<T>, // Error: infinite size!
}
The compiler will reject it. Because Node contains a Node, which contains another Node, the size is technically infinite. To fix this, we must introduce a layer of indirection. By using Box<T>, we store the recursive part on the heap rather than the stack. The Box itself has a fixed, known size (the size of a pointer), which tells the compiler exactly how much space to allocate for the struct.
Generic Recursive Structures
When working with generics, this pattern becomes very powerful for building data structures like linked lists or trees. Here is how we implement a simple generic list:
struct List<T> {
head: T,
tail: Option<Box<List<T>>>,
}
By wrapping the recursive List<T> in a Box, we resolve the size ambiguity. The Option type handles the "empty" base case, allowing the structure to terminate gracefully.
Why Static Dispatch Matters
Because we are using Box<List<T>>, we are relying on static dispatch for the generic type T. The compiler knows exactly what T is at every level of the recursion. Unlike trait objects (which use dynamic dispatch), this approach allows the compiler to inline code and optimize memory layout effectively. Since the Box is just a pointer, the compiler only needs to know the size of the pointer and the size of T to determine the total memory footprint of your List<T>.
When you design these structures, always ensure your recursion is terminated by a variant (like None in Option) to avoid logical infinite loops, and rely on Box to provide the size safety the compiler requires.
Key Takeaway: To define recursive generic types, use Box to introduce indirection, turning an infinitely sized structure into a fixed-size pointer.