链表

概述

链表（Linked List） 是一种通过**指针（引用）**将节点串联而成的线性数据结构。与数组不同，链表的元素在内存中不必连续存放，每个节点通过指针指向其前驱和/或后继节点，从而实现灵活的动态插入与删除。

定义

双链表（Doubly Linked List）

双链表中的每个节点 $x$ 包含三个域：

• $x.key$：存储元素值。
• $x.prev$：指向前驱节点的指针（若 $x$ 为头节点则为 $\text{NIL}$）。
• $x.next$：指向后继节点的指针（若 $x$ 为尾节点则为 $\text{NIL}$）。

链表还维护一个头指针 $L.head$，指向链表的第一个节点。若链表为空，则 $L.head=\text{NIL}$。

**单链表（Singly Linked List）**是双链表的简化版本，每个节点仅包含 $key$ 和 $next$ 域，只能沿一个方向遍历。

核心性质

基本操作与复杂度

操作	时间复杂度	说明
$\text{textsc}List-Search(L,k)$	$O(n)$	从头遍历，逐一比较 $key$
$\text{textsc}List-Insert(L,x)$	$O(1)$	在链表头部插入，仅修改指针
$\text{textsc}List-Delete(L,x)$	$O(1)$	已知节点 $x$ 的指针时，仅修改相邻指针

操作伪代码

搜索：

LIST-SEARCH(L, k)
  x = L.head
  while x ≠ NIL and x.key ≠ k
    x = x.next
  return x

插入（在链表头部）：

LIST-INSERT(L, x)
  x.next = L.head
  if L.head ≠ NIL
    L.head.prev = x
  L.head = x
  x.prev = NIL

删除：

LIST-DELETE(L, x)
  if x.prev ≠ NIL
    x.prev.next = x.next
  else
    L.head = x.next
  if x.next ≠ NIL
    x.next.prev = x.prev

哨兵（Sentinel / Dummy Node）

哨兵的作用

引入一个哨兵节点 $L.nil$（哑节点），替代所有 $\text{NIL}$ 指针。哨兵不存储实际数据，仅作为边界标记。

优势：消除边界条件判断，简化代码逻辑。例如，删除操作不再需要检查 x.prev 是否为 NIL，因为哨兵保证每个节点都有前驱。

代价：额外占用一个节点的空间，但通常可以忽略不计。

循环链表

在循环链表中，尾节点的 $next$ 指针指向头节点（双链表中头节点的 $prev$ 指向尾节点），形成环形结构。配合哨兵使用时，哨兵本身既是”头”也是”尾”，遍历到哨兵即表示遍历完成。

单链表 vs 双链表

特性	单链表	双链表
每节点指针数	1（$next$）	2（$prev$, $next$）
空间开销	较低	较高
反向遍历	不支持	支持
已知节点删除	需要前驱指针	$O(1)$ 直接删除
适用场景	仅需单向遍历时	需要频繁双向操作时

章节扩展

第10章：指针与动态内存

链表是 CLRS 第10章中基于指针的数据结构的代表。与栈和队列的数组实现不同，链表利用显式指针将分散在内存中的节点串联起来，天然支持动态增长（无需预分配容量）。

链表是许多高级数据结构的基础构件：有根树的节点表示本质上就是链表的扩展（每个节点可以有多个指针指向子节点）；散列表的**链接法（chaining）**使用链表处理冲突。

参见

• 栈 — 栈可用链表实现，无需预分配容量
• 队列 — 队列可用链表实现，维护 head 和 tail 指针
• 有根树 — 树的节点表示是链表指针思想的扩展
• 二叉堆 — 对比：堆用数组紧凑存储，链表用指针灵活链接，各有取舍