数据结构速查表

1. 一句话总结

数据结构面试先抓访问方式、增删成本、内存结构、典型场景和复杂度。

2. 通俗解释

把数据结构当工具箱：数组适合快速定位，链表适合改连接，栈处理最近关系，队列处理先后顺序，哈希表用空间换查找速度。

3. 核心概念

• 数组：连续内存，随机访问 O(1)，中间插删 O(n)。
• 链表：非连续内存，按指针连接，查找 O(n)，已知节点插删 O(1)。
• 栈：后进先出，常用于括号匹配、递归、单调栈。
• 队列：先进先出，常用于 BFS、任务调度、消息缓冲。
• 哈希表：平均 O(1) 查询，依赖哈希函数、冲突解决和扩容。
• 树：天然表达层级结构，二叉树遍历是递归和迭代基础。
• B+ 树：适合数据库索引，减少磁盘 IO，支持范围查询。
• 堆：快速获取最大/最小值，适合 Top K 和优先队列。
• 排序：重点比较快排、归并、堆排的复杂度、稳定性和空间。
• 二分：本质是在有序或单调答案空间中排除一半。

4. 底层原理

• 数组快的底层原因是连续内存和 Cache 友好。
• 哈希表快的前提是冲突可控，负载因子过高会扩容。
• 树结构的关键是降低查找高度，平衡树避免退化为链表。
• 堆只保证父子局部有序，不保证整体有序。
• 二分不是只能用于数组，也可用于答案单调性问题。
• 动态规划的本质是用状态保存子问题答案，避免重复计算。

5. 面试标准回答

数据结构题要先说清“结构特点”和“复杂度”。数组是连续内存，随机访问快但中间插删慢；链表通过指针连接，查找慢但已知节点插删快；栈和队列分别解决后进先出、先进先出问题；哈希表通过哈希函数把 key 映射到位置，平均查询 O(1)，但要处理冲突和扩容；树和图用于表达层级和关系，BFS、DFS 是基本遍历方式；堆适合快速取最值；排序、二分、贪心、DP 则是算法题高频框架。面试不要只背复杂度，要说明为什么以及适用场景。

6. 高频追问

追问 1：数据结构速查表面试第一句话怎么答？

先给结论：数组：连续内存，随机访问 O(1)，中间插删 O(n)。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

数组快的底层原因是连续内存和 Cache 友好。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：哈希表快的前提是冲突可控，负载因子过高会扩容。

追问 5：实际开发中怎么体现？

Python dict/set 背后是哈希表，平均查询快但会扩容。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• Python dict/set 背后是哈希表，平均查询快但会扩容。
• MySQL 索引用 B+ 树，是因为磁盘页和范围查询。
• Redis 的 zset 常联系跳表，list/quicklist 联系链表和连续存储折中。
• 消息队列、BFS、线程池任务队列都能用队列理解。
• LRU Cache 可由哈希表 + 双向链表实现。

9. 背诵速记

速记：数组连续、链表指针、栈最近、队列先后、哈希映射、树降高度、堆取最值、图看关系、排序看稳定性和空间、二分看单调性、DP 看状态和转移。回答时先复杂度，再讲为什么。