Layout

A linked list is one node pointing at the next, so the type is recursive. In C you'd write struct Node { int v; struct Node* next; } and never think twice. In Rust the obvious translation does not compile, and the reason is the entire point of the chapter.

01

First instinct: an enum that's either empty or a node containing a value and the rest of the list. It mirrors the C struct one-to-one. The compiler has a problem with it.
```
pub enum List {
    Empty,
    More(Node),
}

struct Node {
    elem: i32,
    next: List,
}
```
02

The error: the type has infinite size. C lets you do this because Node* is one pointer wide regardless of what it points at. Rust stores the variant inline, so More(Node) would have to embed another List directly inside itself, which embeds another, and so on. The size of List is the size of List plus a bit. The compiler refuses to solve that equation.
```
error[E0072]: recursive type `List` has infinite size
  --> src/lib.rs:1:1
   |
1  | pub enum List {
   | ^^^^^^^^^^^^^
2  |     Empty,
3  |     More(Node),
   |          ---- recursive without indirection
```
03

Box<T> is the heap allocation. It owns one T on the heap and is a single pointer at runtime. Drop a Box, the heap memory is freed. Wrap the recursive part in Box<Node> and the size collapses to one pointer.
```
pub enum List {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: List,
}
```
04

It compiles, but the layout is sloppy. List::Empty is a valid value of List, which means an empty list still costs an enum tag plus padding. Worse, Node's next field can itself be empty, so we're paying for the empty-case representation at every link. We can fix that by hiding the recursion behind a private alias and a wrapper struct.
```
pub struct List {
    head: Link,
}

// private to the module — readers don't see this
enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}
```