---
title: 数据结构知识体系：数组、链表、哈希表、树、图、堆与面试
description: 数据结构面试复习路线，涵盖数组、链表、栈、队列、哈希表、树、图、堆、Trie、并查集、跳表、红黑树、布隆过滤器、LRU、复杂度分析和 Java 后端工程场景。
category: 计算机基础
tag:
  - 数据结构
  - 算法
  - 面试
sitemap:
  changefreq: weekly
  priority: 0.9
head:
  - - meta
    - name: keywords
      content: 数据结构,数据结构面试题,数据结构复习路线,数组,链表,栈,队列,哈希表,HashMap,树,图,堆,Trie,并查集,跳表,红黑树,布隆过滤器,LRU,Java集合,Redis,MySQL索引,后端面试
---

这份 **数据结构知识体系** 按面试和 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 怎么写？                        | 和算法模板一起复习           |

## 面试回答框架

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

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

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

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

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

## 建议阅读顺序

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

## 核心文章

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

## 结构选型速查

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

| 场景                      | 优先考虑            | 取舍点                                             |
| ------------------------- | ------------------- | -------------------------------------------------- |
| 按下标频繁随机访问        | 数组、`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 为什么常用哈希表加双向链表实现？

## 相关专题

- [计算机基础知识体系](../)
- [算法专题](../algorithms/)
- [常见数据结构经典 LeetCode 题目推荐](../algorithms/common-data-structures-leetcode-recommendations.md)
- [Java 集合](../../java/collection/java-collection-questions-01.md)
- [MySQL 索引详解](../../database/mysql/mysql-index.md)
- [Redis 常见面试题总结](../../database/redis/redis-questions-01.md)
- [面试准备](../../interview-preparation/)

<!-- @include: @article-footer.snippet.md -->
