课程 · #2 / 11

链表

节点散落在内存各处，靠指针缝合在一起

Singly linked list · head → tail

singly doubly circular

init

walk to 3 value

动手试试：点 walk，沿着 head 指针朝某个下标一路追过去——数一数走了多少跳。然后在同一位置 insert 或 delete——指针重连是 O(1)，但你仍然得先走到那个位置。

为什么它重要

链表教会你用指针来思考——这是计算机科学中的一个根本概念。尽管实际中它往往比数组慢，但它为你打开了理解树、图以及内存管理的大门。

核心思想

想象一场寻宝游戏。每条线索都告诉你下一条线索在哪儿。你没法直接跳到第 5 条线索——你必须从头开始一环扣一环地追下去。

这就是链表。 每个节点都装着数据，以及一个指向下一个节点的指针。

它的权衡和数组恰好相反：

在已知位置插入/删除：O(1) —— 只需重新接好指针
按下标找到某个位置：O(n) —— 必须沿链走过去

当你需要频繁地在开头、或在某个已知节点之后插入/删除时，链表胜出。当你需要随机访问时，数组胜出。

要点回顾

在已知位置插入/删除是 O(1) —— 只需改动指针
按下标访问是 O(n) —— 必须从头节点开始遍历
不浪费空间，但每个节点要为指针付出额外内存
适合在头部或已知节点之后频繁插入

再深入一些

单向、双向与循环

| 变体 | 每个节点拥有 | 显著特性 | |---|---|---| | 单向链表 | 仅 next | 内存最省；只能向前走 | | 双向链表 | next + prev | 在已有节点引用时删除是 O(1)（无需再去找前驱）；可双向行走 | | 循环链表（单向或双向） | 尾节点 → next = head | 轮转调度；迭代器永不终止 | | 异或链表（趣闻） | 一个指针 = prev XOR next | 用单向链表的内存代价实现双向链表。会破坏缓存预取——纯学术性。 |

双向链表的杀手锏是 O(1) 拼接：给定一个你已经持有指针的节点 n，只需两次指针写入就能把它从链表中摘除：

n.prev.next = n.next;
n.next.prev = n.prev;

无需遍历。这就是为什么天下所有的 LRU 缓存实现都用一个双向链表来支撑哈希表：哈希表让你按键 O(1) 找到节点；双向链表让你在每次访问时把那个节点 O(1) 地挪到最前面。

循环变体支撑着轮转调度器——每一个给可运行线程分配时间片的操作系统进程调度器，背后某处都有一个循环链表。最后一个线程的 "next" 指针指回第一个；你只管一直往下走。

内存开销 —— 真实的数字

在 64 位系统上，一个装着 int32 的单向链表节点：

[ 4 bytes data ][ 4 bytes padding ][ 8 bytes next pointer ] = 16 B

数据是 4 字节，存储却占了 16 字节——每个元素 4 倍开销。同样数据的双向链表：

[ 4 bytes data ][ 4 bytes padding ][ 8 bytes next ][ 8 bytes prev ] = 24 B

6 倍开销。而且这些节点在内存里并不连续——每个都是独立的堆分配，所以遍历链表就是一场缓存缺失的狂欢。同样这些 int32 装进 Vec<i32> 后，每个紧凑地占 4 字节，连续存放，被 CPU 预取。对一个百万元素的循环来说，尽管大O完全相同，数组也能快上 50–100 倍。

这一课的教训是：只有当你确实需要凭一个活动节点引用做 O(1) 拼接时（LRU 缓存、操作系统调度器、内核数据结构里的侵入式链表），链表才是对的选择。对其余一切，优先用数组——参见数组那一课的缓存局部性章节。

数学细节

时间复杂度: Access by index: O(n); Insert at head: O(1); Insert after node: O(1); Delete node (given prev): O(1); Search: O(n)
空间: 每个节点存储数据 + 指针; Memory per node: sizeof(T) + sizeof(pointer)

实现

链表节点

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

// Insert at head: O(1)
fn push_front(head: &mut Option<Box<Node<T>>>, data: T) {
    let new_node = Box::new(Node {
        data,
        next: head.take(),
    });
    *head = Some(new_node);
}

何时使用

在头部频繁插入/删除
大小未知、内存受限
作为栈、队列的构造基石
理解指针操作

练习

三道经典的链表题目，每道凸显一种不同的指针套路：

反转链表 —— 简单 · 三指针之舞，最经典的指针操作练习
检测环（Floyd 龟兔赛跑） —— 中等 · 替代"已访问集合"的 O(1) 空间方案
合并两个有序链表 —— 简单 · 不分配新内存地拼接节点——这就是归并排序的合并步骤

→ 浏览全部练习题

🔗 链表