从 LinkedList 血案说起：用 3W 法搭建数据结构知识框架
数据结构是算法的骨架，也是程序性能的底层基石。很多同学把数据结构视为课本知识，真正写业务代码时却很少意识到它的存在。这篇文章我们尝试用「3W
法」重新认识数据结构，并对常见分类做一次体系化梳理，为深入学习打好底座。
先分享一个真实的小插曲：曾有一次线上“秒开页面”突然变成“8 秒白屏”，排查半天才发现有人把原本的 ArrayList 换成了
LinkedList。操作在代码里只差几个字母，但由于需要频繁随机访问，链表瞬间把性能拖垮。那天之后，团队里每个人都重新审视起数据结构的力量——它不仅决定算法效率，更直接影响用户体验。希望这篇文章也能带给你这样的直观感受。
事故复盘：8 秒白屏背后的细节
- 场景背景：页面渲染前需要多次随机定位列表元素，最初基于
ArrayList，可以直接通过下标定位。 - 替换动机：为了让插入更“优雅”，有人把底层实现换成
LinkedList，以为可以让插入性能提升。 - 性能崩溃：链表的随机访问是 O(n)，渲染过程中每次
get(i)都要从头遍历，几十次操作瞬间被放大成 O(n²)。 - 排查过程：逐项排除网络、接口、缓存等因素后，反复对比 diff 才发现有人替换了集合类型。
- 核心教训：性能瓶颈常常埋在“看起来只是实现细节”的地方；选型前必须先分析业务的访问模式。
用 3W 法认识数据结构
What：什么是数据结构？
数据结构（Data Structure）是计算机中组织和存储数据的方式，它定义了数据之间的逻辑关系、数据的存储结构以及相关的操作。一个好的数据结构能够让数据存取效率最大化，降低程序复杂度，也为算法设计提供了明确的边界条件。
Why：为什么要学习数据结构？
- 直击性能瓶颈：90% 的性能问题都直接或间接与数据组织方式有关。
- 提高抽象能力：复杂业务往往需要将实体映射为合理的结构才能高效解决。
- 强化面试竞争力：几乎所有技术岗面试都会考察数据结构与算法。
- 夯实工程能力：从缓存、索引再到分布式系统，底层都离不开数据结构的支撑。
How：如何选型与应用？
选择数据结构时可以遵循三步走：
- 明确业务核心操作：是频繁查询、更新还是插入删除？
- 评估数据规模与实时性：数据量、并发度、响应时间要求直接决定选型。
- 结合语言 & 库特性：比如在 Java 中用
ArrayList/LinkedList，在 Go 中用切片/链表等。
小贴士：不要从「我会什么」出发，而要从「问题需要什么」出发，先抽象操作，再确定结构。
数据结构的常见分类
我们可以从逻辑结构和物理存储两条维度认识数据结构，这里以常见逻辑结构为主。
逻辑结构全景图
为了建立完整的知识框架，可以先从逻辑关系的角度对数据结构进行归类：
- 线性结构：数据元素呈一条链，前驱后继关系明确。典型代表有数组、链表、栈、队列。
- 非线性结构：节点之间的连接呈树形或网状，适合表达层级、依赖与关联。包括树、堆、图。
- 哈希/集合结构：基于哈希映射实现快速查找与去重，如哈希表、布隆过滤器。
- 复合结构与抽象数据类型：为特定问题组合或扩展基础结构，如并查集、跳表、LRU 缓存等。
接下来的小节会按“线性结构”和“非线性结构”两大类展开，后续系列文章则会针对特殊结构单独拆解。
线性结构
- 数组（Array）：连续内存，随机访问 O(1)，批量插入成本高。
- 链表（Linked List）：节点分散，插入删除灵活，查找需要遍历。
- 栈（Stack）：后进先出（LIFO），常用在函数调用、撤销操作。
- 队列（Queue）：先进先出（FIFO），适合排队、消息缓冲场景。
| 结构 | 核心访问模式 | 适用场景 | 踩坑提醒 |
|---|---|---|---|
ArrayList |
随机读多、批量写少 | 渲染列表、时间序列、缓存命中表 | 中间插入需要整体搬移，注意扩容 |
LinkedList |
顺序吞吐、插入删除频繁 | 任务调度、链式处理流水 | 不要承担大量随机 get(i)，否则会重演 8 秒白屏 |
推荐一个可视化资源：VisuAlgo 支持数组、栈、队列等动画演示。你可以手动拖拽或自动播放插入过程，帮助加深记忆。
非线性结构
- 树（Tree）：层级结构，适合表示父子关系。如二叉搜索树、AVL 树、红黑树。
- 堆（Heap）：特殊的完全二叉树，维护堆序性质，常用于优先级队列。
- 图（Graph）：节点+边的泛化结构，适合建模复杂关系网络。
- 哈希结构（Hash）：通过哈希函数对键进行映射，支持近似 O(1) 的存取。
同样推荐两个学习资源：
- Algorithm Visualizer：支持树、图等动画演练。
- University of San Francisco Data Structure Visualizations
：美国旧金山大学提供的交互式可视化网站，涵盖树、堆、图等多种结构。
动图 + 代码：Java 源码视角演示
以数组与链表的插入为例，我们可以通过动图和代码加深理解：
- 数组插入：需要移动插入点之后的所有元素，因此时间复杂度为 O(n)。
- 链表插入：调整前后指针即可，平均时间复杂度为 O(1)。
动图资源参考：
- Array Insertion Visualization
- Linked List Visualizer（由 Y. Daniel Liang 提供）
下面分别给出常见结构的 Java 示例，并标注在 JDK 源码中的关键入口（均基于 OpenJDK
17）。每个示例前先快速回顾它在工程中的直观印象，帮助建立“知道是什么 + 看得见怎么做”的关联。
数组（ArrayList）——连续内存、随机访问快
数组是最贴近硬件的线性结构，所有元素紧挨存放，因此下标访问是 O(1)。缺点是中间插入需要整体搬移，扩容也要开辟新空间。
那次白屏之后，我们在代码评审阶段都会先问一句：“调用方是读多写少吗？”如果答案是肯定的，就让
ArrayList留在原位。
List<Integer> arrayList = new ArrayList<>(Arrays.asList(1, 2, 4));
arrayList.add(2, 3); // ElementData 数组扩容 + System.arraycopy
System.out.println(arrayList); // [1, 2, 3, 4]
- 源码入口：
ArrayList#add(int, E)，文件java/util/ArrayList.java - 场景速记：消息列表、时间序列、缓存命中表等“读多写少”的业务非常适合数组。
链表（LinkedList）——节点分散、插入删除灵活
链表把每个元素打包成节点，通过指针串联。插入删除只需改指针，代价是失去了下标随机访问，需要顺着指针遍历。
复盘那次事故我们才意识到：调用代码一旦大量使用
list.get(i)，链表就会被迫一遍遍从头遍历，再优雅的插入体验也救不回整体性能。
LinkedList<Integer> linkedList = new LinkedList<>(List.of(1, 2, 3));
linkedList.addFirst(0); // 链接新的头结点
linkedList.removeLast(); // 断开尾结点
System.out.println(linkedList); // [0, 1, 2]
- 源码入口：
LinkedList#linkFirst、LinkedList#unlinkLast - 场景速记：任务调度器、订单状态流水这类“按顺序批量吞吐”的场景常用链表；不要把它放在需要频繁随机访问的地方。
栈（Stack）——后进先出的一端封闭结构
栈只有一个出口，常见在函数调用栈、撤销操作等场景。ArrayDeque 在 JDK 中推荐用作栈，循环数组让 push/pop 都保持 O(1)。
Deque<String> stack = new ArrayDeque<>();
stack.push("call");
stack.push("return");
stack.pop();
System.out.println(stack.peek()); // call
- 源码入口：
ArrayDeque#push/ArrayDeque#pop - 场景速记：浏览器“前进/后退”、编辑器撤销、表达式求值都在背后用栈支撑。
队列（Queue）——先进先出，适合排队缓冲
队列的特点是从队尾入、队头出，常用在消息缓冲、线程池任务调度。ArrayDeque 借助循环数组避免频繁移动元素。
Queue<String> queue = new ArrayDeque<>();
queue.offer("A");
queue.offer("B");
queue.poll();
System.out.println(queue.peek()); // B
- 源码入口：
ArrayDeque#offer/ArrayDeque#poll - 场景速记：消息队列、打印队列、限流窗口，一切“排队等候”都离不开它。
树（TreeMap）——层级结构，保持有序关系
树把数据组织成父子层级，便于区间查找和排序。TreeMap 基于红黑树，每次插入都会通过颜色和旋转保持平衡。
Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "C");
treeMap.put(1, "A");
treeMap.put(2, "B");
System.out.println(treeMap); // {1=A, 2=B, 3=C}
- 源码入口：
TreeMap#put、TreeMap#fixAfterInsertion - 场景速记：区间搜索、排行榜、基于范围的缓存命中，都可以让树结构发挥威力。
堆（PriorityQueue）——动态获取极值的好帮手
堆是一棵完全二叉树，父节点总是比子节点更优（大顶堆或小顶堆）。适用于优先级队列、Top K 等场景。
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.poll();
System.out.println(minHeap.peek()); // 3
- 源码入口：
PriorityQueue#siftUp、PriorityQueue#siftDown - 场景速记：任务调度优先级、实时榜单、流式数据取前 N 个元素都离不开堆。
哈希结构（HashMap）——用哈希函数换 O(1) 查找
哈希表把键映射到桶数组，冲突时使用链表或树挂载。同一键无需遍历就能定位，非常适合缓存、去重。
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("java", 1);
hashMap.put("ds", 2);
System.out.println(hashMap.get("java")); // 1
- 源码入口：
HashMap#putVal、HashMap#resize - 场景速记：缓存、关键词频次统计、分布式一致性哈希槽位，都是哈希表的主场。
图（Graph）——任意实体关系的通用模型
图通过节点与边刻画复杂关系，例如社交网络、城市交通。常用邻接表或邻接矩阵存储，示例里用 HashMap + ArrayList 自定义邻接表。
Map<String, List<String>> graph = new HashMap<>();
graph.computeIfAbsent("A", k -> new ArrayList<>()).add("B");
graph.computeIfAbsent("A", k -> new ArrayList<>()).add("C");
graph.computeIfAbsent("B", k -> new ArrayList<>()).add("D");
System.out.println(graph); // {A=[B, C], B=[D]}
- 源码入口：以
HashMap为核心，自定义图结构可进一步封装抽象 - 场景速记：推荐系统、城市交通路径、社交关系推荐都可以想象成一张图。
想进一步研究底层逻辑，可以直接跳转到 OpenJDK 源码阅读：
ArrayList#add(int, E)：java/util/ArrayList.java，关注ensureCapacityInternal与System.arraycopy。LinkedList#Node内部类：java/util/LinkedList.java，查看节点结构与链接。TreeMap#put：java/util/TreeMap.java，红黑树旋转如何维护平衡。PriorityQueue#siftUp/siftDown：java/util/PriorityQueue.java，堆的上滤与下滤过程。HashMap#resize：java/util/HashMap.java，了解扩容与树化条件。
有了动图的直观感受，再配合 Java 源码演练，会更容易理解不同结构在底层发生了什么。
工程实践小贴士
- 先认业务再认结构：先画出“读写/顺序/随机”的调用比例图，再对照结构特性挑选，避免凭感觉换容器。
- 代码评审必问访问模式：当看到
List替换时，务必追问调用方是否存在大量get、contains、subList操作。 - 上线前留性能指标：任何结构替换都要带着压测或灰度数据一起评审，性能回归数据能避免 8 秒白屏重演。
- 封装底层实现：通过接口隔离集合操作，限制外层直接依赖下标或指针，给未来的结构替换留缓冲区。
彩蛋：今天就动手排查一次
挑一个正在维护的页面，看它在渲染或数据处理时使用了哪些集合结构。试着回答两件事：
- 它的核心访问模式是什么（读多还是写多，顺序还是随机）？
- 如果把底层结构换成另一种，会不会重演 8 秒白屏？
答案不一定是“需要立刻改造”，但这个练习能让你立刻把文中的 checklist 用到实际工程里。