链表（Linked List）
链表是一种链式存储的线性数据结构，元素可以分散在内存的任何位置，通过每个节点上的指针串联起来。
核心特征
| 特性 | 说明 |
|---|---|
| 内存分布 | 分散的内存块，不要求连续 |
| 访问方式 | O(N) 顺序访问（需遍历指针） |
| 扩容 | 无需扩容，随时添加节点 |
| 内存效率 | 高效利用零散内存，但每个节点额外存储指针 |
与数组对比
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分布 | 连续内存空间 | 分散内存块 |
| 随机访问 | O(1)（索引计算） | O(N)（遍历指针） |
| 头部插入 | O(N)（需移动元素） | O(1) |
| 尾部插入 | O(1)*（可能触发扩容） | O(N)*（有尾引用则O(1)） |
| 中间插入 | O(N)（需移动元素） | O(N)（需遍历找位置） |
| 删除操作 | O(N)（需移动元素） | O(1)*（已知节点引用） |
*取决于是否持有尾引用及具体实现
基本操作时间复杂度
查找/修改（给定索引）
- O(N)：必须从头（或尾）遍历到目标位置
插入
- 头部插入：O(1)
- 尾部插入：O(N)（无尾引用）；O(1)（有尾引用）
- 中间插入：O(N)（需先找到前驱节点）
删除
- 头部删除：O(1)
- 尾部删除：O(N)（需找前驱）；O(1)（双链表有前驱指针）
- 中间删除：O(N)（需先找到前驱节点）；O(1)（已知节点引用）
常见类型
1. 单链表（Singly Linked List）
每个节点只存储一个后继指针（next），只能单向遍历。
参见：单链表
2. 双链表（Doubly Linked List）
每个节点存储两个指针（prev + next），支持双向遍历。
参见：双链表
3. 其他变体
- 循环链表：尾节点指向头节点
- 静态链表：用数组模拟链表
关键技巧
虚拟头节点（Dummy Head）
在链表头部添加一个不存储数据的虚拟节点，统一边界条件处理。
参见：虚拟头尾节点
双指针技巧
链表算法中的核心技巧，详见 双指针 概念页。
快慢指针
用于查找中间节点、判断环、找倒数第k个节点等场景。
| 模式 | 快指针速度 | 慢指针速度 | 应用场景 |
|---|---|---|---|
| 倒数第k个 | k步领先 | 同步 | 从后向前定位 |
| 寻找中点 | 2步/次 | 1步/次 | 定位中间位置 |
| 环检测 | 2步/次 | 1步/次 | 判断是否有环，找环起点 |
双指针拼接
用于解决交点问题：让两个指针分别遍历不同链表，逻辑上拼接成相同长度。
详见：链表技巧总结
多指针操作
如反转链表需要同时维护 prev、curr、next 三个指针。