上一篇我们讲了 Array 数组为什么查得快改得慢。

数组的特点是连续内存、下标访问快，但中间插入和删除需要搬动后面的元素。

链表刚好走了另一条路。

它不要求所有数据挨着存，而是把数据拆成一个个节点，每个节点通过指针指向下一个节点。

看起来像是“插入删除很快”的数据结构，但这句话有一个前提：我们已经拿到了要操作的节点或位置。

如果还要从头找这个位置，查找本身仍然要 O(n)。

这篇就把 LinkedList 链表拆开看看，顺便和 Array 做一次正面对比。

链表到底是什么

链表也是一种线性表。

它和数组一样，数据之间是线性关系，但保存方式完全不同。

数组把元素连续摆放：

数组
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘
​

链表则是节点分散存放，再用引用或指针连接起来：

head
 │
 ▼
┌──────────┐      ┌──────────┐      ┌──────────┐
│ data: 10 │ next ───>│ data: 20 │ next ───>│ data: 30 │ next ───> null
└──────────┘      └──────────┘      └──────────┘
​

节点不一定在连续的内存地址上。

只要 next 能找到下一个节点，整条链就能连起来。

所以链表不需要像数组那样提前申请一大块连续空间，扩展时也不需要整体搬家。

节点里有什么

一个最基本的单链表节点通常包含两部分：

• 数据本身
• 指向下一个节点的引用

class Node<T> {
    T value;
    Node<T> next;
}
​

双向链表则会多一个 prev 引用：

class DoubleNode<T> {
    T value;
    DoubleNode<T> prev;
    DoubleNode<T> next;
}
​

这就是链表的核心代价：数组把空间花在连续存储上，链表把空间花在指针或对象引用上。

链表的几种形式

单向链表

单向链表只有一个方向：从当前节点指向下一个节点。

head -> A -> B -> C -> null
​

它结构简单，额外空间开销小。

但如果想从 C 回到 B，就只能重新从头遍历，不能直接向前走。

双向链表

双向链表同时保存前驱和后继：

null <- A <-> B <-> C -> null
        │     │     │
      prev  prev  prev
​

从任意节点都可以向前或向后移动。

Java 的 LinkedList 底层就是双向链表思路，节点通常会保存前一个节点和后一个节点。

好处是删除一个已知节点时更方便，坏处是每个节点多占一份引用空间，修改指针时也要更小心。

循环链表

循环链表的尾节点不指向 null，而是重新指向头节点：

head -> A -> B -> C
        ▲         │
        └─────────┘
​

循环链表适合轮询、环形队列和周期调度等场景。

但遍历时不能简单判断节点是否为 null，必须记录起点，避免无限循环。

链表怎么查找

链表最明显的缺点就是随机访问慢。

数组访问 Array[3] 时，可以通过起始地址和元素大小直接计算目标地址。

链表没有这个条件。

想找第 3 个节点，只能从 head 开始一个个沿着 next 走：

查找第 3 个节点

head
 │
 ▼
节点0 -> 节点1 -> 节点2 -> 节点3
 访问      访问      访问      找到
​

因此链表按下标查找的时间复杂度是 O(n)。

双向链表可以根据目标位置选择从头走还是从尾走，平均能减少一部分遍历距离，但数量级仍然是 O(n)，不会变成 O(1)。

这也是为什么 LinkedList.get(index) 不适合被放进大循环里反复调用。

for (int i = 0; i < list.size(); i++) {
    // LinkedList 按下标 get，可能反复遍历
    process(list.get(i));
}
​

如果只是顺序遍历，应该使用迭代器或增强 for，让链表沿着节点指针向后走一次。

链表怎么插入

链表插入的核心不是搬动数据，而是修改指针。

假设现在有：

A -> B -> C
​

想在 B 和 C 之间插入 N：

第一步：N.next 指向 C
第二步：B.next 指向 N

结果：
A -> B -> N -> C
​

图示如下：

插入前：
B ─────────> C

调整指针：
B ───────┐   C
         │   ▲
         ▼   │
         N ──┘

插入后：
B -> N -> C
​

如果已经拿到了 B 节点，插入动作只需要修改有限几个引用，时间复杂度可以做到 O(1)。

但如果只知道“我要插在第 1000 个位置”，还是要先遍历找到第 999 个节点。

所以更准确的说法是：

已知节点位置的插入：O(1)
按下标寻找位置再插入：O(n)
​

头部插入

头部插入通常非常简单：

插入前：
head -> A -> B -> C

创建 N：
N.next = head
head = N

插入后：
head -> N -> A -> B -> C
​

只要保存了 head 指针，头部插入就是 O(1)。

尾部追加

如果链表同时保存 tail 指针，尾部追加也可以做到 O(1)：

追加前：
head -> A -> B -> C <- tail

C.next = N
tail = N

追加后：
head -> A -> B -> C -> N <- tail
​

如果没有 tail，每次追加都要从 head 走到最后，时间复杂度就是 O(n)。

链表怎么删除

删除操作也是修改指针。

假设删除 B：

删除前：
A -> B -> C
​

让 A 直接指向 C：

A.next = C

删除后：
A -> C
​

如果已经拿到了 A，也就是被删除节点的前驱，删除动作是 O(1)。

双向链表如果已经拿到了 B 自己，也可以通过 B.prev 和 B.next 直接完成摘除：

删除前：
A <-> B <-> C

调整：
A.next = C
C.prev = A

删除后：
A <-> C
​

但如果只有一个值，比如“删除值为 30 的节点”，还是需要从头找，查找时间是 O(n)。

删除时要处理边界

链表删除很容易漏掉这些情况：

• 删除空链表
• 删除头节点
• 删除尾节点
• 链表只有一个节点
• 删除的值不存在
• 删除连续重复值中的一个或全部

使用哨兵节点可以减少头节点的特殊判断：

哨兵 -> 第一个节点 -> 第二个节点 -> null
​

哨兵不保存业务数据，只负责让头部和中间节点拥有相似的操作流程。

代码少几个 if，维护起来就轻松一些。

LinkedList 和 Array 怎么选

数组和链表各有自己的优势。

可以先看一张复杂度对比表：

操作	Array	LinkedList
按下标读取	O(1)	O(n)
头部插入	O(n)	已知头节点时 O(1)
中间插入	O(n)	已知节点位置时 O(1)
尾部追加	有容量时接近 O(1)	有 tail 时 O(1)
中间删除	O(n)	已知节点时 O(1)
顺序遍历	通常很快	需要沿指针访问
扩容	可能复制整体数据	通常按节点增加

但只看大 O 还不够。

## Array的优势

Array 使用连续内存，主要优势是：

- 按下标读取非常快
- 顺序遍历对 CPU 缓存友好
- 每个元素不需要额外保存 next 指针
- 内存布局简单，额外开销小
- 适合批量读取、排序和随机访问

上一篇[Array数组为什么查得快改得慢](/post/153.html)已经详细讲过连续内存和扩容，这里不再重复展开。

## LinkedList的优势

LinkedList 的优势主要在结构调整：

- 已知节点位置时插入删除只需要调整指针
- 头部插入和删除简单
- 不需要整体申请一块连续空间
- 可以自然实现队列、双端队列和循环结构
- 节点可以在运行过程中逐个加入

但“节点逐个加入”不等于完全不消耗内存。

每个节点仍然要保存对象本身和指针引用，频繁创建节点也会带来对象分配和垃圾回收成本。

## LinkedList的缺点

链表的缺点也很明显：

- 按下标访问慢
- 节点可能分散在内存中，缓存局部性差
- 每个节点有额外指针和对象开销
- 指针修改多，代码更容易出边界 bug
- 找到位置本身需要遍历
- 实际性能不一定比数组更好

尤其是 Java 中的 `LinkedList`，它并不是“插入删除万能快”。

如果业务经常按下标读取，或者主要是顺序遍历，`ArrayList` 往往更合适。

如果只是需要队列或双端队列语义，也可以优先考虑接口和场景匹配的容器，而不是因为名字里有 List 就直接选 LinkedList。

# 链表为什么不一定更快

链表的理论优势是“修改指针”，但现代计算机的实际性能还受到 CPU 缓存影响。

数组元素挨着存，CPU 读取一个元素时，附近的数据可能一起进入缓存。

链表节点分散在内存中，遍历每个节点都可能发生指针跳转。

```text
数组遍历：
内存A -> 内存A+1 -> 内存A+2 -> 内存A+3
              连续、容易命中缓存

链表遍历：
地址A -> 地址K -> 地址P -> 地址D
              分散、可能频繁跳转
​

所以即使两者的遍历复杂度都是 O(n)，数组的实际耗时也可能更低。

理论复杂度是选型的起点，不是性能结论的终点。

我个人的习惯是：默认优先选择数组或 ArrayList，只有当业务确实有大量节点插入删除、并且能拿到操作位置时，才考虑链表。

LinkedList 适合哪些场景

链表比较适合下面这些场景：

• 需要频繁从头部加入或移除元素
• 已经持有节点或迭代器位置，需要快速插入删除
• 实现队列、双端队列、LRU 链表结构
• 节点之间有明显的前后关系
• 不需要频繁随机访问

例如 LRU 缓存通常会把哈希表和双向链表组合起来：

HashMap：通过 key 快速找到节点
Double LinkedList：维护最近使用顺序

访问节点 -> 摘除节点 -> 放到链表头部
淘汰节点 -> 删除链表尾部
​

这里哈希表负责定位，链表负责调整顺序，两者配合后才能同时做到快速查找和快速移动。

单独使用 LinkedList，通常无法做到按 key O(1) 定位。

常见实现错误

自己实现链表时，最容易错的是指针更新顺序。

插入节点时，应该先保存后继关系，再修改前驱指针，避免把原链路弄丢。

错误：先覆盖 B.next，再试图寻找原来的 C
结果：C 丢失，链表断开

正确：
1. 先让 N.next 指向 C
2. 再让 B.next 指向 N
​

双向链表还要同时维护 prev 和 next，只改一个方向会造成正向遍历正常、反向遍历断裂。

另外，遍历链表时一定要有终止条件：

单链表：节点走到 null 就结束
循环链表：节点再次回到起点就结束
​

如果判断写错，程序可能陷入死循环。

小结

LinkedList 链表的核心是：节点分散存储，依靠指针连接，修改连接关系而不是整体搬动数据。

它的优势：

• 已知节点位置时插入删除快
• 头部操作简单
• 不要求一整块连续内存
• 适合队列、双端队列和链式结构

它的缺点：

• 按下标查找慢，通常是 O(n)
• 节点有额外指针和对象开销
• 内存不连续，遍历缓存局部性较差
• 找位置的成本经常抵消插入删除的优势

一句话对比：Array 擅长连续访问和随机读取，LinkedList 擅长已知位置的结构调整。

别因为链表的插入删除是 O(1)，就默认它比数组快。

先看业务到底是查得多，还是改得多；再看操作时是否真的拿到了节点位置；最后结合数据规模和实际压测做决定。