A generic recursive type

Level: 201 → 301 · working knowledge

One line: A type that contains itself has no finite size until a pointer breaks the cycle — Option<Box<Self>> is that pointer, and the Option half of it is free.

struct ListNode<T> {
    data: T,
    next: Option<Box<ListNode<T>>>,
}

impl<T> ListNode<T> {
    fn new(data: T) -> Self {
        Self { data, next: None }
    }

    fn push_front(self, data: T) -> Self {
        Self { data, next: Some(Box::new(self)) }
    }
}

let ballot = ListNode::new("Cara").push_front("Ben").push_front("Ada");
println!("{}", ballot.data);  // Ada

One definition, and ListNode<&str> and ListNode<u8> are two unrelated linked lists built from it.

Why the Box is not optional

Write the field as Option<ListNode<T>> and the type has no size the compiler can compute — a node contains a node contains a node:

error[E0072]: recursive type `ListNode` has infinite size
 --> e0072.rs:1:1
  |
1 | struct ListNode<T> {
  | ^^^^^^^^^^^^^^^^^^
2 |     data: T,
3 |     next: Option<ListNode<T>>,
  |                  ----------- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
3 |     next: Option<Box<ListNode<T>>>,
  |                  ++++           +

A Box<ListNode<T>> is one pointer, eight bytes, whatever T turns out to be — so the size stops depending on itself and the recursion moves to the heap where it belongs. Rc and & break the cycle the same way; Box is the one to reach for when the node owns the rest of the list.

The Option is free

None costs nothing here, because a Box is never null and the compiler knows it — so None is stored as the null pointer rather than as a tag beside one:

Type	size_of
Box<ListNode<i32>>	8
Option<Box<ListNode<i32>>>	8

That is the null-pointer optimisation, and it is what makes Option<Box<T>> the idiomatic "maybe another node" in Rust rather than a wrapper you pay for.

Rolling your own Option gets you an Option

The alternative spelling — an enum with an explicit End variant — is a reasonable-looking idea:

enum NextNode<T> {
    Next(Box<OtherNode<T>>),
    End,
}

struct OtherNode<T> {
    data: T,
    next: NextNode<T>,
}

It compiles, it is the same eight bytes (the same niche applies), and it walks the same way. What it is, precisely, is Option<Box<OtherNode<T>>> with the variants renamed — and renaming them costs the whole Option API: no as_deref, map, take, is_none, unwrap_or, no while let Some(…) that every Rust reader already knows on sight. A bespoke two-variant enum earns its place when the names carry meaning the code depends on (Pending / Finalised); "there is no next node" is not that case.

Do not box the payload

The data field needs no Box. T is not recursive — only the next field is — so boxing it buys nothing and costs an allocation and a dereference per node:

Node type	size_of	Heap allocations per node
ListNode<[u8; 64]> — payload inline	72	1 (for the next pointer)
BoxedData<[u8; 64]> — data: Box<T>	16	2

The boxed row is not strictly worse: it is a smaller node, which matters if you move nodes around a lot or if T is huge and rarely read. But it is a decision to make about a specific T, and the default is inline. A Box<T> in a generic struct is right when the type must be a fixed size regardless of T — not as a habit.

Likewise a where T: Clone on the node definition itself — which is how the books usually print this struct — is a bound in the wrong place: it stops you from ever building a list of something unclonable, and the plainest impl block below it becomes six errors. Where the bound goes has that transcript.

Walking one

let mut current = Some(&ballot);
while let Some(node) = current {
    println!("{}", node.data);
    current = node.next.as_deref();
}

as_deref() ↗ turns &Option<Box<ListNode<T>>> into Option<&ListNode<T>> — the loop variable borrows and never owns, so the list is intact afterwards. That one method is why the Option spelling is worth keeping.

Recursion works too (fn len(&self) -> usize { 1 + self.next.as_ref().map_or(0, |n| n.len()) }), and it has a real limit: nothing here is tail-call optimised, so a long enough list overflows the stack. The iterative walk has no such ceiling. The same asymmetry applies to Drop, and it is the one bug this data structure is famous for — dropping a very long list recurses once per node.

When you actually want one

Rarely. A Vec<T> beats a linked list on almost every access pattern on real hardware, and std's own LinkedList ↗ says so in its documentation. Build this one to learn what Box, Option and <T> do together — that is what it is for here, and it is why the type turns up in every Rust book. If you want the deep version, Learn Rust With Entirely Too Many Linked Lists ↗ is six increasingly honest attempts at exactly this struct.

If you are coming from another language

Python. class Node: def __init__(self, data, next=None) needs no equivalent of the Box, and it is worth knowing why: every Python value is already a reference, so self.next = other stores a pointer whether you think about it or not, and a class instance has no fixed inline size to compute. Rust makes the same choice visible — Box is where you say this part lives on the heap — and hands you the counterpart in exchange: the node owns its successor, so the whole list is freed when the head is dropped, with no reference counting and no collector. None maps to None, pleasingly exactly.

ABAP. The same wall, and the same fix. A structure cannot contain itself by value — there is no size for it — so a linked node is built from a reference component: TYPE REF TO ty_node for a data reference, or the more common shape, a class whose attribute is TYPE REF TO lcl_node. That is Box under a different name, minus the ownership: ABAP references are garbage collected, so two nodes may point at the same successor and nobody has to decide who frees it. Rust's Box says exactly one owner, which is what lets the memory be released at a known moment; when you genuinely need the ABAP arrangement — several owners, freed when the last one goes — the type is Rc<T>.

C++. struct Node { T data; std::unique_ptr<Node> next; }; is the same design with the same reasoning, and Box is unique_ptr. Rust's version needs no rule of five, no explicit destructor, and cannot be double-freed or read after the move, because the move is the compiler's business rather than yours. The recursive-Drop stack overflow, however, is shared exactly — both languages destroy the list one frame per node unless you write the loop by hand.

Java. class Node<T> { T data; Node<T> next; } compiles as written, since every object reference is already a pointer, and the collector handles the rest. Rust asks for the Box because it lays a struct out inline by default, and hands back deterministic freeing for the trouble.

The verified output

examples/a_generic_recursive_type.rs compiled and run:

Verified output of a_generic_recursive_type.rs — regenerated by tools/run_examples.py, never hand-typed.

  1. Ada
  2. Ben
  3. Cara
length 3

size_of::<Box<ListNode<i32>>>()          8
size_of::<Option<Box<ListNode<i32>>>>()  8
size_of::<NextNode<i32>>()               8

size_of::<ListNode<i32>>()               16
size_of::<ListNode<[u8; 64]>>()          72
size_of::<BoxedData<[u8; 64]>>()         16

ListNode<&str> of 3, ListNode<u8> of 2
the hand-rolled spelling walks the same way: 1 then 0
BoxedData holds 64 bytes behind one more pointer

Practice

Walk it without recursion. Give ListNode<T> a method values(&self) -> Vec<&T> that returns every payload in order, head first, using a loop rather than recursion — and without moving or cloning anything, so the list is still usable afterwards.

Write the obvious recursive version first if you like; then convert it, and note what the loop needs that the recursion did not. The method that makes the loop possible is on Option, not on your type.

Solution

a_generic_recursive_type_kata.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

// Kata solution: walk a recursive generic list without recursion.

struct ListNode<T> {
    data: T,
    next: Option<Box<ListNode<T>>>,
}

impl<T> ListNode<T> {
    fn new(data: T) -> Self {
        Self { data, next: None }
    }

    fn push_front(self, data: T) -> Self {
        Self { data, next: Some(Box::new(self)) }
    }

    // `as_deref()` turns &Option<Box<ListNode<T>>> into Option<&ListNode<T>>,
    // which is the whole trick: the loop variable never owns anything.
    fn values(&self) -> Vec<&T> {
        let mut out = Vec::new();
        let mut current = Some(self);
        while let Some(node) = current {
            out.push(&node.data);
            current = node.next.as_deref();
        }
        out
    }
}

fn main() {
    let ballot = ListNode::new("Cara").push_front("Ben").push_front("Ada");
    println!("names   {:?}", ballot.values());
    println!("length  {}", ballot.values().len());

    // The same walk, over a different T. One definition, two lists.
    let scores = ListNode::new(0u8).push_front(3).push_front(5);
    println!("scores  {:?}", scores.values());

    // The list is still there afterwards: values() borrowed, it did not consume.
    println!("first   {}", ballot.values()[0]);
}

Verified output of a_generic_recursive_type_kata.rs — regenerated by tools/run_examples.py, never hand-typed.

names   ["Ada", "Ben", "Cara"]
length  3
scores  [5, 3, 0]
first   Ada

See also

• Nullable pointers — why Option<Box<T>> is free, measured
• Variants that carry data — what a payload costs, and the niche this page is spending
• Where the bound goes — why struct ListNode<T> where T: Clone is the wrong shape
• Generic enums — NextNode<T> in its own right, and the two-parameter case
• What a generic is — the <T> being made recursive here
• Ownership and moves — what push_front(self, …) is doing to the old head

Po polsku

Struktura, która zawiera samą siebie, nie ma skończonego rozmiaru — i w tym tkwi cały problem tej lekcji. rustc mówi to wprost: error[E0072]: recursive type ListNode has infinite size, a w podpowiedzi sam proponuje Box. Po polskim kursie struktur danych ta ściana wydaje się dziwna, bo w Javie i w Pythonie pole next już jest referencją, a w C i C++ pisze się je wskaźnikiem odruchowo. Rust układa pola struktury w miejscu (inline), więc trzeba powiedzieć na głos, gdzie zaczyna się sterta: Option<Box<ListNode<T>>> to osiem bajtów niezależnie od tego, czym okaże się T, i te osiem bajtów przerywa cykl.

Drugi fakt bywa jeszcze mniej oczywisty: Option jest tu za darmo. Box nigdy nie jest nullem i kompilator o tym wie, więc None zapisuje się jako wskaźnik zerowy, a nie jako dodatkowy znacznik obok niego — size_of::<Box<ListNode<i32>>>() i size_of::<Option<Box<ListNode<i32>>>>() dają tyle samo, po 8. To optymalizacja niszy (null-pointer optimisation) i to dzięki niej „może jest następny węzeł” pisze się w Ruscie przez Option<Box<T>>, a nie przez własne opakowanie, za które trzeba by zapłacić.

Stąd pułapka, w którą wpada się właśnie po kursie list: skoro lista ma mieć „koniec”, to napiszmy własne wyliczenie z wariantem End. Ono się kompiluje, zajmuje te same 8 bajtów — i jest dokładnie Option<Box<…>> z przemianowanymi wariantami, tyle że bez całego API Option: bez as_deref, map, take, is_none, bez while let Some(…), które każdy czytelnik Rusta rozpoznaje od razu. Własne dwuwariantowe wyliczenie zarabia na siebie wtedy, gdy nazwy coś znaczą (Pending / Finalised); „nie ma następnego węzła” to nie ten przypadek. Osobno: pola data nie pakuj w Box. Rekurencyjne jest wyłącznie next — ListNode<[u8; 64]> z ładunkiem w miejscu to 72 bajty i jedna alokacja na węzeł, a wersja z data: Box<T> to 16 bajtów i dwie.

Na koniec zastrzeżenie, którego polskie materiały o listach wiązanych zwykle nie stawiają: w Ruscie ta struktura jest ćwiczeniem, nie narzędziem. Vec<T> wygrywa z listą jednokierunkową (linked list) przy niemal każdym wzorcu dostępu na prawdziwym sprzęcie i dokumentacja LinkedList ze std sama to przyznaje. Do tego domyślny Drop schodzi rekurencyjnie, po jednej ramce stosu na węzeł, więc dostatecznie długa lista przepełnia stos przy zwalnianiu — tak samo jak rekurencyjne len(). Przejście iteracyjne, przez as_deref(), takiego sufitu nie ma.

Szukaj po polsku: lista jednokierunkowa w Ruscie · typ rekurencyjny o nieskończonym rozmiarze · optymalizacja niszy · rust E0072 recursive type has infinite size · rust Option Box null pointer optimization