链表（单/双/循环）：数组之外，为什么还要学"指针的艺术"

本节你将能

学完这一节，你将能说清三件事：链表和数组到底差在哪、单链表 / 双向链表 / 循环链表分别怎么增删查改、以及为什么现代系统（Redis、操作系统、浏览器）处处都在用链表。它是整个线性结构模块（C3–C9）的入口，后续的栈队列、优先队列、二叉搜索树、图的邻接表，底层全都有链表的影子。

一、数组的"痛"与链表的登场

数组最大的优点是随机访问 O(1)——给定下标直接算出内存地址。但它有三个结构性短板：① 中间插入 / 删除要搬移后续元素，O(n)；② 需要一段连续内存，当内存碎片化严重时可能分配失败；③ 容量通常固定，扩容要整体拷贝。链表正是为弥补这些短板而生：它把数据存在一个个节点里，节点在内存中零散分布，彼此通过指针（引用）相连，于是插入删除只需改几个指针、无需搬移，也不需要连续内存。

二、单链表：节点与指针

单链表的每个节点包含两部分：数据域和指向下一个节点的指针 next。一条链靠"头指针 head"进入，最后一个节点的 next 为 null（空），表示链尾。遍历从 head 出发，沿 next 一路走到 null 为止。

节点与遍历（Python，用对象模拟指针）：

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def traverse(head):
    cur = head
    while cur is not None:
        print(cur.val)
        cur = cur.next

链表的时间复杂度：访问第 k 个节点必须从头走，O(n)；插入 / 删除已知前驱节点时只需改指针，O(1)；但查找前驱本身要 O(n)。空间上每个节点多存一个指针，有额外开销。

图：单链表节点结构与 head→null 的链式存储

三、单链表的增删：断链是头号坑

在节点 p 之后插入新节点 new，顺序绝不能反：必须先让 new.next = p.next，再让 p.next = new；若先改 p.next，后面的链就断了、找不回来了。删除 p 之后的节点，则令 p.next = p.next.next 即可，被删节点随后被垃圾回收。这些"指针改向"操作，正是链表代码的灵魂，也是面试反复考的细节。

def insert_after(p, val):
    new = Node(val)
    new.next = p.next   # 先接后面
    p.next = new        # 再接前面

def delete_after(p):
    if p.next is not None:
        p.next = p.next.next

头节点特殊：在头部插入 / 删除会改变 head 本身，调用方得拿到新的 head。为统一处理，工程上常引入哨兵节点（dummy head）（见今日第⑦篇），让"头插"和"中间插"走同一套代码。

图：insert_after(p, val) 的指针改向——先 new.next 后 p.next

图：delete_after(p) —— 让 p.next 直接跳过被删节点

四、双向链表：多一个指针，少一类麻烦

双向链表的每个节点多一个 prev 指针指向前驱。代价是多一倍指针空间，好处是给定任一节点就能 O(1) 删除它自己（无需先找前驱），还能双向遍历。这正是 LRU 缓存（今日第②篇）、Java LinkedList、Linux 内核调度队列的底层结构。

class DNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

def remove_node(x):           # 已知节点 x，O(1) 自删除
    if x.prev: x.prev.next = x.next
    if x.next: x.next.prev = x.prev

五、循环链表：首尾相连

循环链表把尾节点的 next 指回头节点，形成环。它特别适合表达"周期性"场景：操作系统的时间片轮转调度、环形缓冲区（ring buffer）、以及经典的约瑟夫环问题（今日第④篇）。从任一节点出发都能遍历全表，但要小心别写出死循环——必须按"走了 n 步"或"回到起点"来终止。

六、四种线性结构对比

图：四种线性结构的核心能力速查

七、经典技巧预告

链表之所以是算法面试的常客，是因为它催生了一批"指针艺术"题：反转链表（今日第⑤篇）、快慢指针判环 / 找中点（第⑥篇）、哨兵节点化简边界（第⑦篇）。这些技巧不靠复杂数学，全凭对指针走向的精确把控，是检验"是否真懂数据结构"的试金石。

图：迭代反转的核心——三指针每次前移，cur.next 翻向 prev

小结与下一步

链表用"指针换灵活"：牺牲 O(1) 随机访问，换来 O(1) 插入删除与无需连续内存，成为数组之外最基础的线性结构。单链表够轻量、双向链表支持自删、循环链表适合周期场景。下一步建议推进：C5 二叉搜索树（节点带左右指针的自然延伸）→ C8 优先队列与堆（底层常用链表管理）→ G1 图的邻接表（链表串起图的边）。整个线性结构轨道已在缺口体系中排好优先级，逐个击破即可。

---