数据结构知识体系：数组、链表、哈希表、树、图、堆与面试

这份 数据结构知识体系 按面试和 Java 后端场景组织内容：先理解数据怎么存，再看常见操作复杂度，最后把结构和 Java 集合、MySQL 索引、Redis、缓存、消息队列这些工程问题连起来。

面试里问数据结构，很少只停在“数组是什么”。更常见的是追问：数组和链表为什么一个查询快、一个插入删除方便？HashMap 为什么需要扩容？B+ 树为什么适合索引？布隆过滤器为什么会误判？这些问题背后都在考同一件事：你是否理解结构选择带来的复杂度和场景取舍。

准备数据结构时，不建议只背定义。更有效的方式是把每个结构拆成 4 个问题：怎么存、怎么查、怎么改、适合什么场景。能把这 4 个问题讲清楚，再去刷对应的算法题，效率会高很多。

适合谁看

• 正在补数据结构基础，准备校招或社招后端面试的同学。
• 刷算法题时经常卡在数组、链表、树、图、堆等结构上的读者。
• 想把数据结构和 Java 集合、Redis、MySQL、缓存系统联系起来的工程师。
• 已经看过概念，但回答面试题时容易停在定义层面的开发者。

数据结构面试考什么

考察点	常见问法	复习重点
存储方式	顺序存储和链式存储有什么区别？	内存连续性、指针、缓存友好性
操作复杂度	为什么数组查询是 O(1)，链表查询是 O(n)？	查询、插入、删除、遍历复杂度
结构对比	红黑树和 AVL 树怎么选？B 树和 B+ 树有什么区别？	对比表 + 适用场景
工程关联	HashMap、TreeMap、PriorityQueue、Redis ZSet 用了什么结构？	Java/数据库/缓存中的真实应用
算法承接	树遍历、图搜索、Top K、LRU 怎么写？	和算法模板一起复习

面试回答框架

数据结构题的回答不要只停在“是什么”。面试里更稳的表达方式是按下面这条线展开：

定义 -> 存储方式 -> 常见操作复杂度 -> 优缺点 -> 适用场景 -> Java/Redis/MySQL 中的应用

以哈希表为例，一个完整回答可以这样组织：

1. 哈希表通过哈希函数把 key 映射到数组下标。
2. 查询、插入、删除平均是 O(1)，但冲突严重时会退化。
3. 冲突可以用拉链法、开放寻址法等方式处理。
4. Java HashMap 使用数组 + 链表 + 红黑树，扩容用于控制负载因子。
5. 它适合快速查找、计数、去重、缓存索引等场景，但会消耗额外空间。

这种回答比“哈希表查询是 O(1)”更耐追问，因为它同时交代了原理、复杂度和工程落点。

建议阅读顺序

1. 线性数据结构详解：先掌握数组、链表、栈、队列，理解顺序存储和链式存储。
2. 哈希表面试题总结：理解哈希函数、冲突、扩容，并和 HashMap 连起来。
3. 树结构详解：掌握二叉树、二叉搜索树、AVL、B 树、B+ 树，以及 MySQL 索引关联。
4. 堆详解：理解优先队列、Top K、堆排序和 PriorityQueue。
5. 图详解：理解图的存储、DFS、BFS、拓扑排序和最短路径入口。
6. Trie 前缀树面试题总结、并查集面试题总结：补齐字符串集合和连通性问题。
7. 跳表面试题总结、红黑树详解、布隆过滤器详解、LRU 缓存面试题总结：面向 Java 集合、Redis、缓存和数据库场景复盘。

核心文章

文章	重点	常见关联
线性数据结构详解	数组、链表、栈、队列	ArrayList、LinkedList、消息队列
哈希表面试题总结	哈希函数、冲突、扩容	HashMap、缓存、去重
树结构详解	二叉树、BST、AVL、B 树、B+ 树	MySQL 索引、表达式树
图详解	邻接表、邻接矩阵、DFS、BFS	依赖关系、路由、推荐关系
堆详解	最大堆、最小堆、堆排序	PriorityQueue、Top K、延迟队列
红黑树详解	近似平衡、旋转、变色	TreeMap、HashMap 树化
布隆过滤器详解	位数组、哈希、误判	缓存穿透、去重、黑名单
跳表面试题总结	多级索引、范围查询	Redis ZSet
LRU 缓存面试题总结	哈希表 + 双向链表	本地缓存、页面置换

结构选型速查

很多数据结构问题，实际是在问“这个场景为什么选它，而不是另一个结构”。下面这张表适合面试前快速复盘：

场景	优先考虑	取舍点
按下标频繁随机访问	数组、ArrayList	查询快，插入删除中间元素成本高
频繁在两端插入删除	双端队列、链表	指针操作灵活，但随机访问慢
快速判断元素是否存在	哈希表、布隆过滤器	哈希表准确但占空间，布隆过滤器省空间但可能误判
维护有序集合和范围查询	红黑树、跳表、B+ 树	红黑树适合内存有序集合，跳表适合范围查询和工程实现
处理最大值、最小值、Top K	堆、优先队列	只关心局部最值，不适合全量有序遍历
判断连通性和分组	并查集	合并和查询很快，但不适合频繁删除关系
前缀匹配、搜索提示	Trie	查询与字符串长度相关，但节点数量可能较多
缓存淘汰	LRU、LFU	LRU 看最近访问，LFU 看访问频率

复习时可以反过来问自己：如果不用这个结构，会慢在哪里？会多占多少空间？边界条件是什么？这几个问题想清楚，面试追问通常就能接住。

7 天复习路线

天数	重点	建议动作
第 1 天	数组、链表	写复杂度表，手写反转链表和删除节点
第 2 天	栈、队列、哈希表	写括号匹配、用栈实现队列、两数之和
第 3 天	树	写二叉树遍历、最近公共祖先，复盘 B+ 树
第 4 天	堆	写 Top K、前 K 高频元素，理解 PriorityQueue
第 5 天	图	写 DFS/BFS、岛屿数量、课程表
第 6 天	红黑树、跳表、布隆过滤器	重点准备工程场景追问
第 7 天	LRU 和综合复盘	手写 LRU，整理所有结构的复杂度和应用场景

30 天复习路线

阶段	时间	目标
第一阶段	第 1 到 6 天	线性结构和哈希表，能说清复杂度和 Java 集合关联
第二阶段	第 7 到 13 天	树、堆、图，配合 DFS/BFS 和 Top K 刷题
第三阶段	第 14 到 20 天	Trie、并查集、跳表、红黑树，补齐进阶结构
第四阶段	第 21 到 25 天	布隆过滤器、LRU、工程场景题，连接 Redis/MySQL/缓存
第五阶段	第 26 到 30 天	做错题复盘和面试口述练习，每个结构准备 2 个追问

高频问题自测

• 数组和链表的内存布局有什么区别？为什么数组随机访问快？
• ArrayList 和 LinkedList 在 Java 里怎么选？
• 栈和队列分别适合哪些场景？单调栈、单调队列解决什么问题？
• 哈希冲突有哪些解决方式？HashMap 为什么要扩容？
• 二叉搜索树、AVL 树、红黑树有什么区别？
• B 树和 B+ 树为什么适合数据库索引？
• 堆和普通二叉树有什么区别？Top K 为什么常用堆？
• 图的邻接表和邻接矩阵怎么选？DFS 和 BFS 复杂度是多少？
• 跳表为什么适合范围查询？Redis 为什么使用跳表？
• 布隆过滤器为什么会误判？为什么删除困难？
• LRU 为什么常用哈希表加双向链表实现？

相关专题

• 计算机基础知识体系
• 算法专题
• 常见数据结构经典 LeetCode 题目推荐
• Java 集合
• MySQL 索引详解
• Redis 常见面试题总结
• 面试准备

写在最后

如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。

JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。

如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。