入门：节点、指针与链表的三种形态
基于通用数据结构概念 · 核于 2026-07
速查
- 定义：链表是用指针把一组**分散在内存各处的节点（node）**串成一条链的线性结构，每个节点 =
数据域 + 指针域（next或再加prev）。 - 核心复杂度：访问/按下标查 O(n)（从头节点逐个跳转）；头部插入/删除 O(1)；已知节点处插入/删除 O(1)（只改前后节点的指针）；查找特定值 O(n)。
- 三种形态：单链表（只有
next，单向）；双链表（prev + next，双向，删节点无需前驱）；循环链表（尾节点指回头节点，首尾相接）。 - 与数组的核心差异：数组 O(1) 访问 / O(n) 增删；链表反过来 O(n) 访问 / O(1) 增删（已知节点）——选型看「访问多还是增删多」。
- 缓存不友好：节点分散在堆各处，CPU 缓存行命中率极低，顺序遍历比数组慢一个数量级（即使大 O 相同）。
- 虚拟头节点（dummy）：在真实头节点前加一个不存数据的哨兵节点，让「对头节点的增删」与「对中间节点的增删」代码统一，消除空表/头节点特判。
- 不能二分、不能随机访问：因 O(n) 访问，链表上一切需要「跳到第 i 个」的操作都要从头遍历。
- 内存开销：每个节点多存 1~2 个指针；存 int 这类小元素时内存翻倍。
- next 指针是「钥匙」：删节点时若先丢
next就再也找不回后续节点——「先存 next 再改」是铁律。 - 链表是手写结构的入门：栈/队列（两端操作）、哈希表（链地址法）、LRU 缓存（双向链表 + 哈希）都以它为载体。
- 进阶顺序：链表经典算法 → 进阶操作 → 参考。
一、节点与指针：链表的物理模型
链表的基本单元是节点（node），每个节点存两样东西：
- 数据域（val）：实际承载的数据。
- 指针域（next / prev）：指向下一个（或上一个）节点的引用。
// 单链表节点
class ListNode {
constructor(val, next = null) {
this.val = val; // 数据域
this.next = next; // 指针域：指向下一个节点
}
}
// 构造 1 -> 2 -> 3 -> null
const head = new ListNode(1, new ListNode(2, new ListNode(3)));与数组「一段连续内存 + 基地址」不同，链表的节点分散在堆内存各处，彼此靠 next 指针「跳转」连接。访问第 i 个元素必须从头节点 head 出发，顺着 next 走 i 步——这就是 O(n) 访问的根源。它派生三个推论：
- 不依赖连续内存：节点可以分配在任何空闲位置，申请大链表不会因碎片化失败。
- 增删只改指针：在「已知节点」处插入/删除，只需修改前后节点的
next，无需搬移任何元素，O(1) 完成。 - 缓存不友好：节点地址不连续，CPU 缓存行（通常 64 字节）无法预取后续节点，顺序遍历访存延迟高——这是链表遍历比数组慢一个数量级的主因。
二、核心复杂度
| 操作 | 数组 | 单链表 | 双链表 |
|---|---|---|---|
按下标访问 a[i] / node(i) | O(1) | O(n) | O(n) |
| 头部插入/删除 | O(n) | O(1) | O(1) |
| 尾部插入 | O(1)（动态摊还） | O(1)（带尾指针）/ O(n) | O(1)（带尾指针） |
| 尾部删除 | O(1) | O(n)（要找前驱） | O(1) |
| 中间增删（已知位置） | O(n) | O(1)（单链表删除需前驱） | O(1) |
| 查找（按值） | O(n) | O(n) | O(n) |
| 二分查找 | O(log n) | O(n)（不能二分） | O(n) |
记住一句话：「访问多、要二分、要随机访问 → 数组；增删多、尤其头部增删 → 链表」。注意单链表「删除某节点」若只给了该节点指针、没给前驱，需 O(n) 找前驱才能改 next——双链表靠 prev 指针规避了这点。
三、三种链表形态
单链表（Singly Linked List）
每个节点只有一个 next 指针，只能从头单向走到尾，尾节点的 next 为 null。这是面试题默认的「链表」形态，最常考。
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}优点是结构简单、每节点只多存一个指针；缺点是只能单向遍历，删除某节点（只给该节点指针）需 O(n) 找前驱，不能回退。
双链表（Doubly Linked List）
每个节点有 prev 和 next 两个指针，可双向遍历。给定一个节点指针，删除它只需 node.prev.next = node.next; node.next.prev = node.prev，O(1) 完成——无需像单链表那样找前驱。
class DListNode {
constructor(val, prev = null, next = null) {
this.val = val;
this.prev = prev;
this.next = next;
}
}代价是每节点多存一个指针（内存翻倍）。Java LinkedList、C++ std::list、LRU 缓存底层都是双链表。
循环链表（Circular Linked List）
尾节点的 next 不指 null，而是指回头节点，整个链表首尾相接成环。可以是单循环链表，也可以是双循环链表。常用于「约瑟夫环」「轮询调度」「缓冲区」等需要循环处理的场景。
单循环：head -> A -> B -> C -> head（C.next = head）
双循环：head <-> A <-> B <-> C <-> head（首尾 prev/next 互指）判断循环链表「遍历结束」不能用 curr.next === null，而要看 curr.next === head（或用 curr === head 起始 + 至少走一步）。
四、与数组对比
| 维度 | 数组（动态） | 链表 |
|---|---|---|
随机访问 a[i] / node(i) | O(1) ✅ | O(n) ❌ |
| 头部增删 | O(n) ❌ | O(1) ✅ |
| 尾部增删 | O(1)（摊还）✅ | O(1)（带尾指针）✅ |
| 中间增删（已知位置） | O(n) | O(1) ✅ |
| 顺序遍历缓存 | 友好（连续内存）✅ | 差（节点分散）❌ |
| 内存开销 | 仅数据 | 每节点多 1~2 个指针 |
| 二分查找 | 支持 ✅ | 不支持 ❌ |
| 内存布局 | 必须连续 | 分散，按需分配 |
选型口诀：「读多写少 / 要随机访问 / 要二分 / 要排序 → 数组；写多读少 / 频繁头插 / 大小不确定且频繁中间插删 → 链表」。实际工程里，由于现代 CPU 缓存的强大，即使增删多也常常优先用动态数组（连续内存带来的缓存收益常压过指针操作的常数节省）——链表多用于 LRU 缓存、链式哈希桶、多项式、实现栈/队列等特定场景。
五、内存模型：节点分散
堆内存（分散）：
+------+ +------+ +------+
| 1 | ●-|---->| 3 | ●-|---->| 5 | / |
+------+ +------+ +------+
head node2 node3
（● 是 next 指针，/ 是 null）每个节点单独 new 出来，地址不连续。好处是无需扩容（加节点就 new，不占大块连续内存）；坏处是每节点独立寻址 + 指针跳转，缓存命中差。
为什么链表遍历比数组慢
虽然单链表顺序遍历也是 O(n)，但实际跑起来比数组慢一个数量级，原因：
- 缓存不命中：数组连续，CPU 预取连续缓存行；链表节点分散，每跳一个节点都可能 cache miss（一次访存 ~100 周期）。
- 指针解引用：每次
curr = curr.next都是一次间接寻址，破坏流水线。 - 内存碎片：节点散落各处，TLB 命中也差。
所以「链表增删 O(1)」只在不计缓存、不计常数的理论分析下成立；工程上小数据量数组常更快。
六、虚拟头节点与哨兵技巧
虚拟头节点（dummy head）
在真实头节点之前加一个不存数据的哨兵节点 dummy，让 dummy.next = head。返回时取 dummy.next。
// 在有序链表中插入一个新节点（用 dummy 统一边界）
function insert(head, node) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next && prev.next.val < node.val) prev = prev.next;
node.next = prev.next; // 先接后
prev.next = node; // 再接前
return dummy.next; // 返回新头（head 可能变）
}好处：统一了「对头节点的操作」和「对中间节点的操作」——不用单独写「若插入到头节点之前则更新 head」的特判。涉及「可能改变头节点」的题（删除节点、合并、反转区段）几乎都该用 dummy。
哨兵节点（sentinel）
更广义地，「哨兵」是放在边界处简化判断的虚拟节点。如双向链表的头尾哨兵：head 和 tail 是两个空节点，真实节点夹在中间，首尾插入删除都变成「中间插入删除」，无需特判空表/单元素。
下一步
理解了链表的节点模型与三种形态后，下一步是链表最高频的算法套路——反转、环检测、找中点、倒数第 k、合并，它们几乎全是双指针的应用，见链表经典算法。