数据结构：数组、链表、栈与队列

S2-003建议学进阶约 90 分钟JDK 21计算机基础 · 数据结构与算法

1. 本节定位

从本节起进入 S2 的数据结构部分 ——这是后面所有内容的"操作对象"：

数据结构（本节）→ 算法与复杂度（S2-004~007）→ JVM 内存与并发（S6）→ 高并发设计（S6）

本节的特点：不讲"是什么"（书上都有），只讲"什么时候用哪个" ✓ ——并用真实耗时给出判断依据 ✓

2. 学习目标

• 说出数组与链表在四种操作上的代价差异 ★★★（含实测）；
• 知道 LinkedList.get(i) 是个陷阱 ★★★；
• 知道"当栈当队列"该选 ArrayDeque ★★★；
• 能说出栈与队列在工程里的典型用途 ★★；
• 知道 ArrayList 与 LinkedList 的真实选择依据 ★★。

3. 前置知识检查

• 会用 List / Deque 接口吗？（《HashMap》）✓
• 知道大 O 的含义吗？（《时间复杂度和空间复杂度》）✓

4. 为什么需要这个知识

先看两个高频事故 ✗：

// 事故 1：用下标遍历 LinkedList
LinkedList<Integer> list = ...;
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));        // ✗ 每次 get 都从头走一遍 → O(n²)
}

实测数据（DataStructureLesson）：同样 2 万次随机访问，ArrayList 4 ms，LinkedList 525 ms ✗✗ ——131 倍 ✓

// 事故 2：用 LinkedList 当队列（以为它快）
Deque<Task> queue = new LinkedList<>();      // 次优选择

实测：ArrayDeque 23 ms vs LinkedList 32 ms ✓ ——前者更快，且内存更省 ✓

5. 核心概念

5.1 四种操作的代价对照 ★★★

理论复杂度：

操作	ArrayList（数组）	LinkedList（双向链表）
按下标访问 ★★	O(1) ✓✓	O(n) ✗✗
尾部插入	均摊 O(1) ✓	O(1) ✓
头部插入	O(n) ✗（要搬移）	O(1) ✓
中间插入（已定位）	O(n) ✗	O(1) ✓
额外内存	仅数据本身 ✓	每个节点两个指针 ✗

★ 实测数据（本节的核心）：

===== 1. 顺序遍历 =====
  ArrayList  顺序遍历 200 万个： 4 ms
  LinkedList 顺序遍历 200 万个：18 ms      → 慢 4.5 倍 ✗

===== 2. 随机访问第 k 个元素 =====
  ArrayList.get   20000 次：  4 ms（O(1)）
  LinkedList.get  20000 次：525 ms（O(n)） → 慢 131 倍 ✗✗

===== 3. 在头部插入 =====
  ArrayList.add(0, i)   100000 次：538 ms（每次搬移整个数组）✗
  LinkedList.add(0, i)  100000 次： 11 ms（只改两个指针）✓
  ArrayDeque.addFirst   100000 次：  8 ms（循环数组）✓✓

===== 4. 当队列用 =====
  ArrayDeque 入队出队 500000 次：23 ms ✓✓
  LinkedList 入队出队 500000 次：32 ms

★ 从这四组数据能读出四条结论 ✓：

#	结论
①	链表没有"顺序遍历更快"的优势 ✗ —— 反而慢 4.5 倍（缓存不友好）★
②	LinkedList.get(i) 是灾难 ✗✗ —— 用下标遍历它等于把 O(n) 变成 O(n²)
③	头部插入确实是链表的主场（11 vs 538 ms）✓ —— 但 ArrayDeque 更快（8 ms） ★★
④	当队列用，ArrayDeque 也胜出 ✓

5.2 为什么链表"顺序遍历"反而更慢 ★★★

这条反直觉，但原因很实在 ✓：

ArrayList：元素在连续内存里
   → CPU 预取器能一次把后面的数据拉进缓存 ✓
   → 缓存命中率高

LinkedList：每个节点是"单独 new 出来的对象"
   → 内存地址分散
   → 每跳一个节点都是一次"内存随机访问" ✗
   → 缓存基本命中不了 ✗✗

★ 这就是"缓存友好"的威力 ✓✓ ——在现代 CPU 上，它的影响常常超过"操作次数" ✓

★ 一个推论：

在链表上"顺序遍历"看起来是 O(n)，实际常数比数组大得多 ✓

所以"链表适合频繁遍历"是错的 ✗✗ ——链表适合"频繁在已知位置插入删除" ✓

5.3 栈与队列：工程里用在哪 ★★

两者都是"受限的线性表" ✓ ——限制带来的是"语义清晰" ✓：

结构	规则	典型用途
栈（LIFO） ★★	后进先出	方法调用栈、括号匹配、表达式求值、撤销（Undo）、DFS ✓
队列（FIFO） ★★	先进先出	任务队列、消息队列、BFS、缓冲、限流 ✓
双端队列（Deque） ★★	两端都能进出	既能当栈也能当队列 ✓✓

★ Java 里的选择（可以照抄） ✓：

// ✗ 不要用 Stack：它是早期设计的遗留类，方法加了 synchronized
Stack<Integer> stack = new Stack<>();

// ✗ 不要用 LinkedList 当队列：比 ArrayDeque 慢且更费内存
Queue<Integer> queue = new LinkedList<>();

// ✓✓ 统一用 ArrayDeque
Deque<Integer> stack = new ArrayDeque<>();     // 当栈：push/pop
Deque<Integer> queue = new ArrayDeque<>();     // 当队列：offer/poll

★ 为什么 Stack 被弃用 ✓：

问题	说明
继承自 Vector ✗	每个方法都带 synchronized ——单线程下白付锁开销 ✓
属于"历史遗留" ⚠️	官方文档推荐用 ArrayDeque 替代 ✓
暴露了下标访问 ✗	允许 elementAt(2) ——破坏了"栈"的语义 ✓

★ 关于 ArrayDeque 的一个细节：

它不允许存 null ✓ ——这是刻意的（因为 poll() 返回 null 表示"空"，两者会混淆）✓✓

所以"用 null 当哨兵值"的代码要改 ⚠️

5.4 选择的判断表 ★★★

需求	首选	理由
按下标随机访问 ★★	ArrayList ✓✓	O(1)，实测快 131 倍
顺序遍历 ★	ArrayList ✓	缓存友好，实测快 4.5 倍
尾部增删	ArrayList ✓	均摊 O(1)
头部/中间频繁增删 ★	ArrayDeque ✓✓（不是 LinkedList）	实测 8 ms vs 11 ms
当栈/队列用 ★★	ArrayDeque ✓✓	实测更快、更省内存
需要按下标 + 频繁中间插入	换个思路（如跳表、树）	不要用 LinkedList 折中 ✗

★ 一条实践结论（本节最该记住的） ✓✓：

日常开发 95% 的场景用 ArrayList 和 ArrayDeque 就够了 ✓✓

LinkedList 在真实项目里极少是正确选择 ✗ —— 它的"理论优势"（O(1) 插入）在实测里常被"缓存不友好"和"ArrayDeque 更优"抵消 ✓

★ 那什么时候真的用 LinkedList ✗：

场景	说明
必须在"已持有节点引用"的位置做 O(1) 插入/删除 ★	比如实现 LRU 时与 HashMap 配合 ✓
数据量极大且内存碎片不敏感 ⚠️	罕见 ✓
需要"两个链表拼接"这类操作	罕见 ✓

★ LRU 那个例子值得一提（《泛型基础》 的实现思路）：

LinkedHashMap（内部是"HashMap + 双向链表"）可以 O(1) 地：
   · 找到 key       ← HashMap 的能力
   · 把节点移到队首  ← 双向链表的能力 ✓
两者缺一不可 ✓

6. 递进示例

6.1 最小示例：栈的典型用途（括号匹配）

Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
    if (c == '(') { stack.push(c); }
    else if (c == ')') {
        if (stack.isEmpty()) { return false; }
        stack.pop();
    }
}
return stack.isEmpty();

6.2 业务示例：用队列做"任务缓冲区"

Deque<Task> buffer = new ArrayDeque<>();
buffer.offer(task);              // 生产者
Task next = buffer.poll();       // 消费者（空时返回 null）

★ 注意"有界"这件事 ✗：

ArrayDeque 没有容量上限 ——生产者快于消费者时会一直涨到 OOM ✗✗

生产环境要用 ArrayBlockingQueue（有界 + 阻塞） ✓✓（《项目 B：高并发场景与架构设计》 会展开）✓

6.3 反例：用下标遍历链表

for (int i = 0; i < linkedList.size(); i++) {
    linkedList.get(i);           // ✗ 每次 O(n)，总计 O(n²)
}

7. 完整可运行代码与实测

代码：labs/cs-basics/src/main/java/cn/kb/learn/cs/DataStructureLesson.java

运行：

cd labs
.\mvnw.cmd -pl cs-basics compile
java "-Dstdout.encoding=UTF-8" -cp cs-basics/target/classes cn.kb.learn.cs.DataStructureLesson

实测输出（完整）：

===== 1. 顺序遍历（ArrayList vs LinkedList）=====
  ArrayList  顺序遍历 200 万个： 4 ms
  LinkedList 顺序遍历 200 万个：18 ms
  → LinkedList 慢 4.5 倍

===== 2. 随机访问第 k 个元素 =====
  ArrayList.get      20000 次：  4 ms（O(1)，按下标直接算地址）
  LinkedList.get     20000 次：525 ms（O(n)，每次从头走）
  → LinkedList 慢 131 倍 ✗✗

===== 3. 在头部插入 =====
  ArrayList.add(0, i)  × 100000：538 ms（每次搬移整个数组）✗
  LinkedList.add(0, i) × 100000： 11 ms（只改两个指针）✓
  ArrayDeque.addFirst  × 100000：  8 ms（循环数组）✓✓

===== 4. 当队列用 =====
  ArrayDeque 入队出队 500000 次：23 ms ✓✓
  LinkedList 入队出队 500000 次：32 ms
  → ArrayDeque 快 1.4 倍

★ 三条可直接写进代码评审的结论 ✓：

#	结论	依据
①	禁止用下标遍历 LinkedList	131 倍的差距 ✗
②	当栈/队列统一用 ArrayDeque（不写 Stack、不写 LinkedList）	更快 + 官方推荐 ✓
③	"头部频繁插入"的第一选择是 ArrayDeque	8 ms vs 11 ms ✓

★ 一个诚实的说明：这组数据在第一次运行时曾出现"ArrayDeque 比 LinkedList 慢"的反常结果 ✗ —— 原因是数据量太小（20 万）且受 JIT 影响 ✓ ——放大到 200 万后结论就稳定了 ✓✓ （这再次印证 《时间复杂度和空间复杂度》 的"微基准要看量级"）✓

8. Debug 观察点

1. 把顺序遍历的数据量改回 20 万：观察两者差异消失（都是 1 ms）★；
2. 把随机访问的 LinkedList 次数从 2 万提到 10 万：观察耗时呈平方增长 ✗✗；
3. 用 Stack 替代 ArrayDeque 做同样的操作：观察额外的同步开销 ⚠️；
4. 打印 LinkedList 与 ArrayList 的内存占用（用 -verbose:gc 或估算）★；
5. 往 ArrayDeque 里 add(null)：观察 NullPointerException ✓。

9. 常见错误

#	错误	说明
1	用下标遍历 LinkedList ✗✗	O(n²)（5.1）✗✗
2	用 LinkedList 当队列 ✗	ArrayDeque 更快更省内存 ✓
3	用 Stack 类 ✗	遗留类，带不必要的同步 ✓
4	以为"链表遍历快" ✗✗	缓存不友好，实测慢 4.5 倍 ✓
5	用无界队列当缓冲区 ✗✗	生产快于消费会 OOM ✓
6	ArrayDeque 里存 null ✗	会抛 NPE（因为 null 要表示"空"）✓

10. 动手实验

目标：亲手量出"两种结构的真实代价"，并形成自己的选择习惯。

步骤：

1. 跑 DataStructureLesson，记录四组数据 ✓；
2. 自己写一个"用下标遍历 LinkedList"的例子（n=5 万），测耗时，再换成 for-each ★★；
3. 用 ArrayDeque 与 LinkedList 各实现一个"任务队列"，各入队出队 100 万次，对比耗时 ✓；
4. 把数据量再扩大一倍，观察倍数关系是否稳定 ✓；
5. 总结自己的"选择口诀" ✓。

验收方式：能说出"为什么链表遍历反而慢"，并给出实测依据。

扩展任务：实现一个有界队列：

• 基于 ArrayDeque + 容量判断（满时丢弃或抛异常）✓；
• 对比 ArrayBlockingQueue（JDK 自带的，带阻塞与条件变量）✓；
• 说明：为什么生产环境要用"有界"队列（提示：背压）★★

11. 练习题

1. 判断：LinkedList 的顺序遍历比 ArrayList 快。（对 / 错）
2. 填空：随机访问第 k 个元素，ArrayList 是 ______，LinkedList 是 ______；实测差 ______ 倍。
3. 简答：为什么"当队列用"推荐 ArrayDeque 而不是 LinkedList？
4. （代码阅读）

LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 50000; i++) { list.add("x" + i); }
long count = list.stream().filter(s -> s.length() > 3).count();

这段代码有问题吗？（提示：stream() 底层用的是迭代器还是 get）★ 5. （编程）用 ArrayDeque 实现一个"撤销（Undo）"功能：每次操作压栈，撤销时弹栈，最多保留 100 步。

参考答案（要点）

1. 错。实测慢 4.5 倍 ✓ ——因为链表节点内存分散，CPU 缓存命中率低 ✓★
2. O(1)；O(n)；131 倍 ✓
3. 因为 ArrayDeque 实测更快（23 vs 32 ms）、内存更省（不需要每个节点存两个指针）✓
4. 没问题 ——stream() 用的是迭代器，是 O(n) ✓★ 会出问题的是"用下标 for 循环 + get(i)" ✗
5. 要点：ArrayDeque + 计数；超过 100 就 pollLast() 把最旧的丢掉 ✓ 说明：这本质就是一个"有容量上限的栈" ✓

12. 掌握标准

• [ ] 能说出四种操作下数组与链表的代价差异，并引用实测数字 ★★★；
• [ ] 知道 LinkedList.get(i) 是 O(n)，绝不用于按下标遍历 ★★★；
• [ ] 知道"链表遍历反而慢"及其原因（缓存不友好） ★★★；
• [ ] 当栈/队列统一用 ArrayDeque ★★★；
• [ ] 知道 Stack 为什么被弃用 ✓；
• [ ] 知道"无界队列会导致 OOM"，生产要用有界队列 ★★。

13. 扩展资源

• Java 集合框架官方教程
• ArrayDeque 与 LinkedList 的性能对比（Baeldung）
• 算法（第 4 版）：背包、队列和栈

14. 下一步学习

《树、堆与哈希表》：从线性结构进入非线性结构。

前置知识

• S1-003 数组

后续知识

• S2-004 树、堆与哈希表
• S2-005 基础算法：排序与二分查找
• S2-007 时间复杂度和空间复杂度

进度只保存在本机浏览器，可随时清除