In this lesson, you will learn how to design data structures that contain themselves without violating Rust’s strict ownership rules.
The Problem of Infinite Size
In many languages, creating a recursive structure—like a linked list where a node contains another node—is simple because the compiler uses pointers that can be null. In Rust, however, a struct must have a known size at compile time. If you define a struct Node { next: Node }, the compiler cannot calculate the size because the structure is theoretically infinite.
The Role of Indirection
To break this cycle, we use a pointer. By wrapping the recursive part in a Box<T>, we move the data to the heap. A Box has a fixed, known size (the size of a pointer), which tells the compiler exactly how much space the Node takes up on the stack, regardless of how long the list grows in the heap.
Here is how we represent a simple recursive node:
struct Node {
value: i32,
next: Option<Box<Node>>,
}
Respecting Ownership Hierarchies
When we use Box<Node>, we are establishing a strict ownership hierarchy. The Node "owns" its Box, and the Box owns the heap-allocated Node it points to. This follows our previous lessons on ownership transfer and cleanup: when the outer Node goes out of scope, it is dropped. Because it owns the Box, the Box is also dropped, which triggers the cleanup of the next Node in the chain.
This creates a "cascading drop" effect. Rust ensures that as long as we maintain this tree-like ownership (where each node has exactly one parent), we avoid memory leaks and double-free errors. We are effectively building a chain of ownership where each link is responsible for the existence of the one following it. If you tried to have two nodes point to the same next node, the borrow checker would stop you, as that would violate the rule of having a single owner for that heap memory.
Key Takeaway: To design recursive structures, use Box<T> to provide fixed-size indirection while maintaining a clear, linear ownership chain that ensures memory is safely cleaned up when the structure is dropped.