造轮子：用 Box 理解链表

本章目标

这一章用单向链表理解堆分配和递归类型。你会知道为什么链表节点需要 Box，为什么 Rust 不喜欢自引用结构，以及链表在 Rust 里常常不是首选数据结构。

它是什么

链表由一个个节点组成，每个节点保存值和下一个节点的位置。

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

Box<Node<T>> 表示节点放在堆上，当前节点只保存一个固定大小的指针。

为什么需要

递归类型如果直接包含自己，编译器无法知道大小：

struct BadNode<T> {
    value: T,
    next: Option<BadNode<T>>,
}

BadNode 里面有 BadNode，里面又有 BadNode，大小无限。Box 打断这个无限大小：Box<T> 自身大小固定，指向堆上的 T。

怎么使用

一个最小链表：

struct List<T> {
    head: Option<Box<Node<T>>>,
}

空链表的 head 是 None。非空链表的 head 是 Some(Box<Node<T>>)。

逐行解释

fn push_front(&mut self, value: T) {
    let old_head = self.head.take();
    let new_node = Box::new(Node {
        value,
        next: old_head,
    });
    self.head = Some(new_node);
}

&mut self 表示要修改链表。
self.head.take() 把当前头节点取出来，并把 head 留成 None。
这样做避免从借用中的字段里直接移动值。
Box::new(Node { ... }) 在堆上创建新节点。
value 被移动进节点。
next: old_head 让新节点指向旧头节点。
self.head = Some(new_node) 把新节点设为头。

这段代码体现了 Rust 链表的关键：移动节点所有权，而不是裸指针乱连。

常见坑

链表不是 Rust 中性能最常用结构。Vec 通常更快，因为缓存局部性好。
递归类型需要间接层，如 Box、Rc 或引用。
从字段中移动值时经常需要 Option::take()。
双向链表会涉及共享所有权和内部可变性，初学阶段不要急。

练习

定义 Node<T> 和 List<T>。
实现 new() 和 push_front()。
实现 pop_front() -> Option<T>。
写测试确认后进先出行为。

造轮子任务

实现一个单向链表栈 LinkedStack<T>。要求不用 Vec，只用 Box 和 Option。完成后比较它和上一章 Stack<T> 的 API 是否一致。

小结

链表不是为了替代 Vec，而是为了理解递归类型、堆分配和所有权转移。Box 的作用是给递归结构一个固定大小的间接层。