03｜链表及其常见形式

1. 核心概念

链表（Linked List）通过指针连接节点，不要求节点在内存中连续存储。

  • 数据域：保存节点的数据。
  • 指针域：保存其他节点的地址。
  • 头指针（Head）：用于定位链表的起始节点。

普通单向链表沿 Next 指针逐个访问节点，因此按位置查找通常为 O(n)。

2. 常见链表形式

类型链接方式特点
单向链表每个节点指向后继节点主要沿一个方向遍历
双向链表每个节点保存前驱和后继支持前后遍历，指针开销较大
循环链表尾部连接回头部可以循环访问，遍历需明确终止条件

单向/双向与是否循环是两个不同维度，因此可以有单向循环链表和双向循环链表。

3. 插入与删除

链表通过修改节点的链接关系进行插入或删除，不必整体移动其他节点的数据。

flowchart TB
    subgraph Before["插入前"]
        direction LR
        A1["A"] --> B1["B"] --> C1["C"]
    end
    subgraph After["在 B 后插入 X"]
        direction LR
        A2["A"] --> B2["B"] --> X2["X"] --> C2["C"]
    end
  • 已知合适位置及所需链接信息：修改链接通常为 O(1)。
  • 需要先寻找位置：查找可能为 O(n)，应计入完整操作成本。
  • 边界处理：注意空链表、头尾节点、唯一节点，以及节点被摘除后的内存管理。

4. 与数组的对比

比较数组链表
存储方式连续存储通过指针连接，不要求连续
按位置访问O(1)通常 O(n)
中间插删通常需要移动元素已知合适位置时可直接改链接
额外开销无逐节点链接指针节点需要保存指针
缓存局部性通常较好通常较差

5. 适用场景

链表适合需要灵活调整已知节点连接关系的场景，例如任务节点管理、消息节点组织、空闲块管理等。

但链表查找慢、指针管理较复杂。对于数量少、频繁遍历或按下标访问的数据，数组往往更简单。

6. 总结

链表的优势是灵活调整节点连接；它不擅长随机访问。插删频繁不等于一定选择链表，还要考虑寻找位置、内存与维护成本。