想象你是一家米其林餐厅的行政总厨。午市高峰有 300 位客人同时点菜：预定名单、食材库存、半成品、出餐顺序、外卖路线全挤在一起。如果你把蔬菜堆在角落、订单塞进抽屉、甜品随便摆在案板上，客人催促时你只能翻箱倒柜。程序的本质也在做同样的事——管理数据。数据结构的精髓，不是背代码，而是回答四个问题：数据放哪？怎么找？怎么加？怎么删？本文把算法面试题当成一次“后厨改造”：给食材建编号格子、把手写订单串成纸链、把盘子叠成后进先出的小山、让客人按号排队、给调料贴标签、用组织架构管理半成品、把最急的订单顶到出餐口、给外卖画一张配送网。这套储藏哲学，就是数据结构。

岗位关联

对 AI 从业者而言，数据结构是算法面试的基石，也是 AI 工程性能的根基。掌握它，你才能在模型训练、推理服务、检索系统中做出低延迟、省内存的取舍。

目录
  1. 可视化演示
  2. 复杂度分析
  3. 数组与字符串
  4. 链表精讲
  5. 栈与队列
  6. 哈希表
  7. 树与二叉树
  8. 堆与优先队列
  9. 图论基础
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

演示哈希表O(1)查找、二叉树遍历、图搜索BFS/DFS三大面试核心场景，点击按钮切换数据结构模式。

本节配有交互动效（进入视口后自动加载，约 3KB）。

哈希表O(1)查找 哈希函数将key映射到bucket 冲突时链表/开放寻址处理 T_lookup = O(1) avg, O(n) worst 空间换时间是核心思想

复杂度分析

午市从 10 桌变成 1000 桌时，如果每来一桌客人都要把全部食材重新清点一遍，后厨就会彻底瘫痪。真正重要的不是单次操作快不快，而是当数据规模变大时，耗时和内存会沿着哪条曲线增长。算法面试里说的复杂度，就是给这条曲线拍一张“全身照”。

计算机科学家用大 O 记号描述这种趋势：它丢掉常数和低阶项，只留下随着输入规模 n 变化的头号因素。比如电梯里按下第 1 层和按下第 1000 层，电梯执行的判断是同一套动作，这是 O(1)；在按字母排序的菜单里用折半法找一道菜，每次排除一半，这是 O(log n)；把 n 道菜和另外 n 道菜两两搭配试味，则是 O(n²)。

复杂度分时间与空间两方面，还要区分最坏、平均与均摊。面试里不能只背结论，要能解释：为什么这个算法最坏 O(n²) 但实际很快？因为多数情况落在平均路径上。

回到后厨：与其纠结这轮切菜快了 1 秒，不如先算明白客人增长 100 倍时，流程会从几分钟变成几小时。复杂度分析就是面试官用来筛掉“只顾眼前、不看规模”的方案的那把尺子。

T(n)=T(n2)+O(1),T(1)=O(1)⇒T(n)=O(log⁡2n)\displaystyle T(n)=T\left(\frac n2\right)+O(1), \quad T(1)=O(1) \quad\Rightarrow\quad T(n)=O(\log_2 n)
这个递推关系代表“每次只剩一半、只做常数工作”，是二分查找、二叉树搜索背后共同的复杂度蓝图。
  1. 递归项把规模为 n 的问题拆成一半，拆完后的另一半用同一个函数继续求解，这就是公式左边的递归来源。
    T(n)=T(n2)+O(1)T(n)=T\left(\frac n2\right)+O(1)
  2. 常数操作每次拆分后只做一次比较和指针移动，与 n 无关的工作量记为 O(1)。
    O(1)O(1)
  3. 对数层数n 连续除以 2 直到 1，除的次数是 log₂ n；每层 O(1)，总复杂度因此为 O(log₂ n)。
    T(n)=O(log⁡2n)T(n)=O(\log_2 n)

数组与字符串

后厨里有一排带编号的冷藏柜，柜门 0 号到 n-1 号。想取第 5 格的牛肉，直接走到 5 号门打开就行，不需要从 0 号开始一格格找。这就是数组最核心的能力：随机访问。

数组是一段连续内存，每个元素占据相同大小，编译器可以通过“起始地址 + 下标 × 元素大小”一步算出目标位置。代价是：在中间插入或删除元素时，后面的元素必须整体向前或向后挪动，最坏要搬动 n 个元素。所以“读写快、增删慢”是数组的典型画像。

面试中的字符串，本质是字符数组。很多题看似是子串问题，实际是在考数组的连续区间操作。双指针能通过左右两个下标把两层循环压缩成一层；滑动窗口则把“所有子串都看一遍”变成“只移动窗口两端”。

冷藏柜的收益很清楚：编号本身就是地址，客人说“第 3 格”，你一步都不用多走。数组面试题难的也不是访问，而是“如何用双指针、滑动窗口，避免反复搬动老食材”。

addr(a[i])=base+i×size\displaystyle \text{addr}(a[i])=\text{base}+i\times \text{size}
数组按下标取元素的数学依据：从基地址出发，跳 i 次、每步 size 字节。
  1. 基地址 base数组在内存中的起点，也就是 0 号元素所在位置。
    base\text{base}
  2. 下标 i元素编号从 0 开始，第 i 个元素相对于起点偏移 i 个位置。
    ii
  3. 元素宽度 size每个元素占用的字节数，比如整数占 4 字节、双精度浮点数占 8 字节。
    size\text{size}

链表精讲

如果订单不是写进固定编号的柜子，而是一张张纸条用线串起来，每张纸条只记录“我的菜名”和“下一张纸条在哪”。这就是链表：节点之间靠指针串联，从头节点出发，一个节点一个节点地摸下去。

链表的优势在插入和删除：只要知道前一个节点，修改指针就能摘除或接入节点，不需要搬动其他数据。但随机访问是 O(n)，想找第 100 个节点，必须从第 1 个开始数。面试中常用三个技巧：哑节点统一处理“头节点为空”的边界；快慢指针找中点、判环；递归反转链表时要先想清楚“当前节点和下一节点谁先变”。

快慢指针是链表题的常客：快指针每次走两步，慢指针每次走一步，快指针到终点时，慢指针正好在中点。

纸质订单链的好处是加一张纸很容易，坏处是想看中间某张订单必须从头翻。链表面试考的不是“背代码”，而是你能不能顺着指针把边界条件想清楚。

sf=2ss,sf=L⇒ss=L2\displaystyle s_f=2s_s,\quad s_f=L \quad\Rightarrow\quad s_s=\frac{L}{2}
快指针走过的距离是慢指针的两倍；当快指针走完整条链长 L，慢指针自然停在 L/2 处。
  1. 速度关系快指针速度是慢指针的 2 倍，所以相同时间内快指针路程是慢指针的 2 倍。
    sf=2sss_f=2s_s
  2. 终点条件快指针先到达链表末尾，此时它走过的总距离等于链表长度 L。
    sf=Ls_f=L
  3. 联立求解把两个式子合并，得到慢指针走过的距离是 L 的一半，即中点。
    ss=L2s_s=\frac{L}{2}

栈与队列

后厨角落有一叠干净的盘子，后放上去的盘子永远被先拿走，这是栈；门口等位的客人先到先入座，这是队列。一个是“后进先出”，一个是“先进先出”，它们规定了数据进出的顺序。

栈适合处理“最近发生的事情优先解决”：函数调用、括号匹配、浏览器前进后退。队列适合处理“先来先服务”的场景：任务调度、消息缓冲、层级遍历。面试进阶题里，单调栈专门用来找“左边或右边第一个比当前值大/小的位置”，它用空间换时间，能把很多 O(n²) 的枚举题优化到 O(n)。

用数组实现队列时，为了避免频繁搬移数据，通常做成循环队列：头尾指针在环形空间里追赶。但“空”和“满”都可能表现为 head == tail，所以常用一个空位来区分。

叠盘子的人不会从盘子山中间抽盘子，排队等位的客人也不能插队到最前面。栈和队列的本质，就是把“顺序”变成一种不可破坏的规矩，面试题只是在检验你有没有遵守这条规矩。

full: (tail+1) mod cap=head\displaystyle \text{full}:\ (tail+1)\bmod cap = head
当尾指针再往前走一格就撞到头指针时，说明队列已满；空出一格是为了区分空队列和满队列。
  1. 尾指针前移tail 每加入一个元素就向后移一格，超过末尾就回到 0。
    (tail+1) mod cap(tail+1)\bmod cap
  2. 相遇判断如果 tail 的下一个位置正好是 head，说明此时队列已经没有可用空位。
    full: (tail+1) mod cap=head\text{full}:\ (tail+1)\bmod cap = head
  3. 空位设计永远浪费一个格子，让“head == tail”只表示队列为空，避免歧义。
    empty: head=tail\text{empty}:\ head = tail

哈希表

给 300 种调料分别贴上标签，写“生抽”“老抽”“花椒”，要找时直接看标签翻抽屉，而不是把整个调料柜从头翻到尾。哈希表就是这张标签：通过哈希函数把 key 映射到数组下标，期望做到“一次定位”。

但两个不同的 key 可能映射到同一个下标，这叫冲突。常见解法是链地址法：每个桶里挂一条链表；或者开放寻址法：冲突后向后找空位。无论哪种，当元素越来越多、桶不够用时，查找就会变慢。负载因子衡量的是“每个桶平均挂了多少元素”。

调料柜再好，也不能把所有东西塞进同一个抽屉。哈希表面试题最爱问“为什么 HashMap 可能慢”“怎么设计哈希函数”，本质是在考你是否理解：标签只是让查找变快的设计，不是免费的万能药。

α=nm\displaystyle \alpha=\frac{n}{m}
负载因子 = 已存元素数 / 桶数。α 越大，冲突概率越高，哈希表性能越差。
  1. 已存元素 n哈希表里实际放入了多少个 key-value 对。
    nn
  2. 桶数量 m底层数组有多少个位置，也就是哈希表最多能直接放多少个“抽屉”。
    mm
  3. 平均链长n 个元素均匀散到 m 个桶，每个桶平均 n/m 个元素，也就是 α。
    α=nm\alpha=\frac{n}{m}

树与二叉树

如果把后厨的半成品管理画成组织架构图：主厨在顶部，下面分冷菜、热菜、甜点三个主管，每个主管再管几个档口。树就是一种“一个根、多个分支、层层向下”的结构，二叉树则是每个节点最多有两棵子树。

二叉树最常见的考点是遍历：前序、中序、后序、层序。递归写法直观，但面试常要求用栈或队列改成迭代；中序遍历一棵二叉搜索树会得到有序序列，这一条性质能解决大量题目。最近公共祖先问题则是“从根往下找，两个目标节点在哪分叉”的经典应用。

一个满的完全二叉树，节点数 n 和高度 h 之间有固定关系：高度近似等于 log₂ n。这也是二叉搜索树为什么能做到 O(log n) 查找的原因。

组织架构图的优点是一层管一层，找人不用满后厨乱跑。树的面试题也一样，只要你能画出“从根到叶的路径”，递归、遍历、公共祖先都会变得清晰。

h=⌊log⁡2n⌋\displaystyle h=\lfloor \log_2 n\rfloor
n 个节点的完全二叉树，高度大约是对 n 取以 2 为底的对数后再向下取整。
  1. 节点数 n树中所有节点的总数。
    nn
  2. 对数关系每向下走一层，节点数最多翻一倍，所以高度与 log₂ n 挂钩。
    log⁡2n\log_2 n
  3. 向下取整节点数不一定正好是 2 的幂，所以用向下取整表示实际高度。
    ⌊log⁡2n⌋\lfloor \log_2 n \rfloor

堆与优先队列

出餐口有一块电子板，永远显示当前最紧急的订单：可能是等了最久的客人，也可能是 VIP 的加急单。堆就是这块电子板：它是一棵完全二叉树，但只保证父节点和子节点之间的顺序，不保证整棵树完全有序。

堆通常用数组存储，因为完全二叉树可以连续编号：根是 0，任意节点 i 的左孩子是 2i+1，右孩子是 2i+2，父节点是 (i-1)/2。插入元素时从下往上“上浮”，取出堆顶时把最后一个元素搬到根再“下沉”，每次操作都是 O(log n)。

面试里最常考的堆应用是 TopK：在几千万个元素里找最大的 K 个，维护一个大小为 K 的小顶堆，比全排序快得多。

出餐台不需要把订单全部排成整齐的队伍，它只要保证“最急的那张一定在最上面”。堆的哲学就是：用最小的维护成本，随时拿到极值，而不是维护全局有序。

parent(i)=⌊i−12⌋,left=2i+1,right=2i+2\displaystyle \text{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor,\quad \text{left}=2i+1,\quad \text{right}=2i+2
这是堆在数组中的“血缘关系公式”：只要知道一个节点的下标，就能算出它的父节点和孩子节点。
  1. 父节点当前节点 i 的父节点下标是 (i-1) 向下取整。
    parent(i)=⌊i−12⌋\text{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor
  2. 左孩子当前节点 i 的左孩子下标是 2i+1。
    left=2i+1\text{left}=2i+1
  3. 右孩子当前节点 i 的右孩子下标是 2i+2。
    right=2i+2\text{right}=2i+2

图论基础

外卖配送路线就是一张图：餐厅、写字楼、住宅是顶点，道路是边。图不要求像树那样只有一个根，它可以有环、可以有多个连通块，所以比树更自由，也更容易绕晕。

存储图有两种主流方式。邻接矩阵用 V×V 的二维数组记录每对顶点之间有没有边，判断两点是否相邻很快，但空间是 O(V²)；邻接表为每个顶点挂一条邻居链表，稀疏图下非常省空间，遍历邻居也方便。面试里大多数图题默认用邻接表。

配送路线图不需要把所有路口都记在脑子里，只要记住“每个路口通向哪些邻居”。图的面试题，先选对存储方式，再用 DFS 深入探索或 BFS 逐层扩散，很多难题就有了入口。

邻接矩阵：O(V2),邻接表：O(V+E)\displaystyle \text{邻接矩阵：}O(V^2),\quad \text{邻接表：}O(V+E)
V 是顶点数，E 是边数。矩阵把所有顶点对都存下来；邻接表只存实际存在的边。
  1. 顶点数 V 与边数 EV 是节点个数，E 是连接节点的边数。
    V, EV,\ E
  2. 矩阵存储量邻接矩阵要开 V 行 V 列，所以空间是 V²。
    O(V2)O(V^2)
  3. 邻接表存储量要遍历所有顶点和所有边，所以空间是 V+E。
    O(V+E)O(V+E)

AI 应用场景

实时推荐 TopK

阶段：在线推理 / 特征服务

解决的问题：推荐系统要为每个用户从海量候选里选出最可能点击的 TopK。传统做法是全部排序后取前 K 个，候选达到千万级时延迟不可接受。用哈希表统计实时点击频次，再用大小为 K 的堆维护当前 TopK，只需 O(n log K) 就能拿到结果。

具体案例：某资讯 App 每小时有 10 万篇新文章涌入，系统对每篇文章统计近 5 分钟的点击量，用一个小顶堆维护点击量最高的 100 篇，热点榜单每秒刷新一次，内存占用始终保持稳定。

GraphRAG 知识图谱检索

阶段：检索增强生成（RAG）

解决的问题：大模型回答企业知识库问题时，需要沿实体关系做多跳检索。把实体和关系建模成图，用邻接表存储邻居，BFS/DFS 就能高效扩展“这个项目关联了哪些人、哪些文档”，避免在全部文档里暴力扫描。

具体案例：企业知识库中，用户问“李雷参与过哪些算法项目？”，系统先从实体表定位“李雷”，再沿邻接表找到他参与的项目节点，最后把项目描述作为上下文喂给大模型生成回答。

Python 演示

python17 行
from collections import Counterimport heapq def top_k_frequent(nums, k):    counter = Counter(nums)    heap = []    for num, freq in counter.items():        heapq.heappush(heap, (freq, num))        if len(heap) > k:            heapq.heappop(heap)    return [num for num, freq in heap] if __name__ == '__main__':    nums = [1, 1, 1, 2, 2, 3, 4, 4, 4, 4]    k = 2    result = top_k_frequent(nums, k)    print("Top", k, "frequent:", result)
目的：用哈希表统计频率，再用大小为 k 的小顶堆找出数组中出现次数最多的前 k 个元素，对应堆与哈希表两节的核心思想。
  1. counter = Counter(nums)用哈希表统计每个数字出现次数，底层是 Python 的字典。
  2. heapq.heappush(heap, (freq, num))以频率为第一关键字、元素值为第二关键字，把候选值放进小顶堆。
  3. if len(heap) > k: heapq.heappop(heap)堆大小一旦超过 k，就弹出当前频率最小的元素，堆里留下的就是频率前 k 大。
  4. return [num for num, freq in heap]从堆中取出元素本身，作为 TopK 结果返回。

常见误区

误区数组只能从头到尾遍历，删除或者插入任何一个元素都要移动一大堆数据，所以数组不适合做任何增删操作。

正解数组“在中间插入/删除”确实是 O(n)，但在末尾追加或删除是 O(1)，按下标随机访问也是 O(1)。真实工程里，很多场景是“读多写少”，数组因为缓存友好反而比链表更快。数据结构的取舍必须看操作分布，不能只看单一操作。

为何常见：教材讲数组缺点时总拿“中间插入”举例，初学者记住了结论，却忽略了操作的上下文和频率分布。

误区链表插入删除是 O(1)，数组是 O(n)，所以链表在任何删除场景下都更快。

正解链表只有在“已经知道前驱节点”时才能 O(1) 完成删除。如果题目只给值让你删，你仍然要先遍历链表找到这个节点，复杂度是 O(n)。而且链表节点分散在内存中，缓存命中率低，实际性能常常不如数组。

为何常见：很多人把“操作代价”和“查找代价”混在一起，误以为删除操作本身就包含了找到目标的过程。

误区哈希表有哈希函数，直接定位，所以所有操作都是铁打的 O(1)。

正解理想情况下查找是平均 O(1)，但最坏情况下所有 key 冲突到同一个桶，链地址法会退化成 O(n)。负载因子过高还会触发扩容，扩容本身要重新哈希所有元素，单次操作可能很慢。面试官问“为什么 HashMap 会退化”，就是在考察这一点。

为何常见：日常用 Python 字典、Java HashMap 时数据量小、哈希函数良好，大家很少见到退化场景，便默认哈希永远高效。

误区看到“二叉树”三个字，就觉得它天然有序，查询应该很快。

正解二叉树只描述“每个节点最多两个孩子”的形状，不规定节点值的大小关系。二叉搜索树才要求左小右大，普通二叉树的中序遍历不一定有序，查找也不一定是 O(log n)。堆是完全二叉树，但它也不是二叉搜索树。

为何常见：很多面试题从二叉搜索树引入，让人潜意识里把“二叉树”和“有序”绑定，忽略了结构性质与数据性质的区分。

误区堆是一种树，所以从根到叶子、从左到右都应该排好序，取出来就是有序数组。

正解堆只保证父节点和子节点之间的偏序关系，比如小顶堆里父节点小于等于孩子，但兄弟节点之间没有顺序约束。从堆里连续弹出堆顶，可以得到有序序列，但堆本身内部并不是全序排列。

为何常见：大家熟悉数组和有序链表，容易用“全序”的直觉去套堆，忽视了堆只负责“快速取极值”这一核心目标。

面试题

Q1. 数组相比链表，最大的结构性优势是什么？

单选题 · easy

  • A.插入新元素无需搬动
  • B.支持按下标随机访问← 正确答案
  • C.内存空间比链表更省
  • D.不需要考虑容量上限

答案：B。数组是连续内存，编译器能通过基地址加偏移直接定位任意下标，所以随机访问是 O(1)。链表要顺藤摸瓜找到目标，插入无需搬动但查找慢；内存省不省要看元素大小和指针开销；数组通常需要预先知道容量，所以 D 也不对。

Q2. 栈这种结构的核心行为是？

单选题 · easy

  • A.先来先服务
  • B.两端都可以进出
  • C.后进先出← 正确答案
  • D.按位置随机访问

答案：C。栈只允许在栈顶操作，后放进去的盘子先被拿走，所以是后进先出（LIFO）。先来先服务是队列，两端都能进出是双端队列，随机访问是数组的特征。

Q3. 动态数组每次扩容为原来的 2 倍，连续 n 次追加的均摊复杂度是？

单选题 · extreme

  • A.O(1)← 正确答案
  • B.O(log n)
  • C.O(n)
  • D.O(n²)

答案：A。虽然某一次扩容需要复制 O(k) 个元素，但每次扩容后容量翻倍，下一次扩容要等很多次追加才会发生。把 n 次追加的总工作量摊到每次操作上，平均是常数级别，所以均摊复杂度是 O(1)。这是“均摊”思想在动态数组中的典型应用。

Q4. 数组实现的循环队列为什么要浪费一个存储位置？

单选题 · mid

  • A.防止哈希冲突
  • B.区分队空和队满← 正确答案
  • C.降低扩容频率
  • D.让头尾指针相等

答案：B。如果允许所有格子都放数据，队空和队满时 head 都可能等于 tail，无法区分。空一个位置后，head == tail 一定表示队空，tail 的下一个位置是 head 才表示队满。这样判断逻辑简单且不会出错。

Q5. 已知单向链表当前节点，删除该节点后继的时间复杂度是？

单选题 · mid

  • A.O(1)← 正确答案
  • B.O(log n)
  • C.O(n)
  • D.O(n log n)

答案：A。已知当前节点 cur 后，删除它的后继只需要一句 cur.next = cur.next.next，不涉及遍历，所以是 O(1)。如果只是知道某个值要删节点，那就必须先花 O(n) 找到它，复杂度才会上升。

Q6. 哈希表负载因子持续增大时，最直接的后果是？

单选题 · mid

  • A.哈希函数自动失效
  • B.冲突变多查询变慢← 正确答案
  • C.数组容量自动变小
  • D.所有链表都不会变长

答案：B。负载因子是元素数与桶数的比值，值越大，每个桶平均挂的元素越多，冲突概率越高，链地址法下的查询时间会从 O(1) 向 O(n) 退化。正确做法是扩容或重新哈希，而不是让哈希函数失效。

Q7. 向最小堆插入一个新元素后，一般需要做什么？

单选题 · hard

  • A.从根开始逐层下沉
  • B.从新位置向上比较← 正确答案
  • C.重建整棵二叉树
  • D.比较所有叶子节点

答案：B。插入时先把新元素放到数组末尾，也就是完全二叉树的最后一个位置，然后与父节点比较，如果不满足堆序就向上交换，这个过程叫“上浮”。从根下沉是取出堆顶后恢复堆序的操作，重建整棵树成本太高。

Q8. 哪些场景适合用队列，而不是栈？

多选题 · mid

  • A.订单按到达顺序处理← 正确答案
  • B.浏览器前进后退记录
  • C.消息队列削峰填谷← 正确答案
  • D.表达式括号匹配

答案：AC。订单按到达顺序处理是典型的先进先出，消息队列要缓冲突发流量、按顺序消费，也适合用队列。浏览器前进后退用两个栈实现，括号匹配用栈判断最近未匹配的括号，所以 B 和 D 不适合队列。

Q9. 关于二叉搜索树，下列说法正确的是？

多选题 · hard

  • A.左子树节点都小于根← 正确答案
  • B.右子树节点都大于根← 正确答案
  • C.中序遍历结果有序← 正确答案
  • D.任意操作都是 O(1)

答案：ABC。二叉搜索树要求左子树所有节点小于根、右子树所有节点大于根，因此中序遍历（左-根-右）会得到递增序列。但它的插入、删除、查找只在树平衡时是 O(log n)，退化成链表后会变成 O(n)，所以 D 错误。

Q10. 图的邻接表存储相比邻接矩阵，优势是？

多选题 · hard

  • A.判断任意两点相邻更快
  • B.稀疏图内存开销更小← 正确答案
  • C.遍历邻居节点更方便← 正确答案
  • D.删除边一定更快

答案：BC。邻接表只存储实际存在的边，所以稀疏图下内存是 O(V+E)，而邻接矩阵固定是 O(V²)；遍历邻居时直接扫当前顶点的链表即可。判断两点是否相邻是邻接矩阵 O(1) 的优势，删除边是否更快要看具体实现，不能绝对化，所以 A 和 D 错误。