模块一 · 数据结构基础
大模型再玄乎，底层数据还是一坨一坨摆在内存里的。数据结构就是"数据的摆法"：同样一百个数，排成一排、连成一条线、挂成一棵树、画成一张网，查起来、改起来的速度天差地别。这一模块教你七种最常用的摆法，以及什么时候该用哪一种。
从这里开始。别管什么大模型，先把"数据怎么摆"搞明白——你写的每一行代码，最后都是在往这些容器里塞东西、取东西。这一模块过八种摆法，学完你一眼就能判断一个操作该用什么容器、为什么快或慢。下一模块，我们去搬数学工具箱。
1.1 数组与链表
Array & Linked List · 连续格子 vs 手拉手想引子与大白话
引子：电影院一排座位，你知道几号在哪，走过去直接坐——这是数组。散场时大家手拉手排成一条长龙，你想找第三个人，只能从第一个人开始数——这是链表。
数组（Array）：内存里一连续的格子，每个格子大小一样，下标从 0 开始。知道下标，直接定位，O(1)。但要在中间插一个人，后面所有人都得往后挪一格——O(n)。
链表（Linked List）：每个节点存数据 + 指向下一个节点的"指针"。插入删除只需要改两个指针——O(1)。但想找第 k 个，只能从头一个一个爬——O(n)。
| 操作 | 数组 Array | 链表 Linked List |
|---|---|---|
| 按下标随机访问 | O(1) 直接算地址 | O(n) 从头爬 |
| 头部插入/删除 | O(n) 全体后移 | O(1) 改指针 |
| 尾部插入（已知尾指针） | 均摊 O(1) | O(1) |
| 中间插入/删除 | O(n) | O(n) 先找到位置 |
| 内存占用 | 连续、省 | 每个节点多存指针 |
生活里
排队叫号（数组按号找）、单向跑道只能从头跑（链表）。
职业里
Python 的 list 本质是动态数组；链表用在 LRU 缓存、浏览器前进后退。
坑：以为链表插入快就到处用。为什么错？链表虽然改指针快，但CPU 缓存对连续内存友好，数组遍历比链表快好几倍。工程上 90% 的场景数组更香，链表只在"频繁头尾插入删"时才赢。
练一练
基础数组 [3,1,4,1,5]，按下标访问 a[3] 得多少？
看答案
下标从 0 开始：a[0]=3, a[1]=1, a[2]=4, a[3]=1。答案是 1。这就是 O(1) 的快感。进阶在长度为 n 的数组头部插入一个元素，为什么是 O(n)？
看答案
所有元素都要往后挪一格，共移动 n 次。若频繁头插，应改用链表或双端队列。自评反馈：答对了就往下走；卡住说明"数组 O(1)/插入 O(n)"没吃透，回看上面数组与链表那一节。
① 数组：连续内存，随机访问 O(1)，中间插入 O(n)。
② 链表：指针串联，定位 O(n)，已定位插入 O(1)。
③ 选型：频繁按下标读用数组；频繁头尾增删用链表。
1.2 栈与队列
Stack & Queue · 一摞盘子 vs 排队买奶茶想引子与大白话
栈（Stack）：一摞盘子，你只能从顶上放、从顶上拿——后放上去的先被拿走。LIFO = Last In First Out。压栈 push、弹栈 pop，都是 O(1)。
队列（Queue）：排队买奶茶，先来的先喝。FIFO = First In First Out。入队 enqueue 尾、出队 dequeue 头，都是 O(1)。
两者本质都是"只能在两端操作的受限数组/链表"——限制越死，越不容易用错。
栈
函数调用栈（递归怎么返回）、表达式求值、括号匹配、编辑器 Undo。
队列
BFS 广度优先搜索（模块三会讲）、消息队列、打印任务排队、操作系统调度。
坑：用普通数组当队列，出队用 shift(0)。为什么错？数组删头元素要把后面 n−1 个全部前移，是 O(n)，队列变成 O(n) 就白设计了。正解：用环形数组（记录头尾指针）或双向链表，保证出队 O(1)。
练一练
基础入队顺序 1,2,3，连出队两次，剩下的是谁？
看答案
FIFO：先出 1，再出 2，剩下 3。进阶括号串 "[(])" 用栈能匹配吗？
看答案
不能。遇左括号压栈，遇右括号看栈顶是否配对：压 [ 压 (，遇 ] 栈顶是 (，不匹配。正确匹配应为 [()]。自评反馈：答对了继续；分不清栈和队列的进出顺序，回看栈/队列那一节的括号匹配例子。
① 栈 LIFO：后退、Undo、函数调用。② 队列 FIFO：排队、BFS、任务调度。③ 两者都只在端点操作，所有操作 O(1)。
1.3 哈希表
Hash Table · 钥匙直接换到柜子号想引子与大白话
引子：数组按下标查 O(1)，可你只知道"人名字"不知道"座位号"。哈希表就是一个魔法函数 hash()：把名字（key）算成一个编号，直接定位到格子。
平均查找/插入/删除都是 O(1)——这是它封神的原因。代价是不支持按顺序遍历、有哈希冲突。
哈希冲突：两个不同 key 算出同一个号怎么办？最常用链地址法：每个格子挂一条链表，冲突的都串在链上。理想情况链长≈1，退化成链表时是 O(n)。
生活里
字典查词、通讯录按名字找人、超市储物柜条码对应柜子。
技术里
数据库索引、缓存（Redis）、Python dict、JS Object、去重（set）。
坑：以为哈希表永远 O(1)。为什么错？哈希函数选得烂、或表太满，所有 key 挤到一条链上，就退化成 O(n)。工程上要及时扩容（load factor 超过阈值就 rehash），并把哈希函数打散。
练一练
基础判断数组里是否有重复元素，O(n) 怎么做？
看答案
遍历并用 set 存，每看到一个元素先查在不在 set 里，在则重复；不在就加入。O(n)。进阶两数之和：nums=[2,7,11,15], target=9，找两数下标。
看答案
一边遍历一边把见过的数存入哈希表。看 2 时，需要 9−2=7，没有，存 2→0；看 7 时，需要 9−7=2，哈希表里有，返回 [0,1]。O(n)。自评反馈：答对了继续；想不起来"两数之和"为什么是 O(n)，回看哈希表那一节。
① 哈希表：key→编号的映射，平均 O(1) 增删查。② 冲突用链地址法，靠扩容维持性能。③ 字典、缓存、去重、计数全靠它。
1.4 树与二叉树
Tree & Binary Tree · 公司组织架构图想引子与大白话
树：一个根节点往下分叉，每个节点挂若干子节点，没有环、不交叉。就像公司架构：CEO → VP → 总监 → 员工。
二叉树：每个节点最多俩孩子——左孩子、右孩子。
二叉搜索树（BST）：左子树所有值 < 根 < 右子树所有值。中序遍历它，就是排好序的序列。理想情况查找 O(log n)，退化成链表时 O(n)。
三种遍历：前序（根左右）、中序（左根右）、后序（左右根）。"前/中/后"指的是根在第几个被访问。
生活里
文件夹目录、家谱、比赛淘汰树、菜单层级。
技术里
数据库索引（B+ 树）、文件系统、HTML DOM、表达式树。
坑：把有序数据依次插进 BST，以为还是 O(log n)。为什么错？按 1,2,3,4,5 顺序插，树长成一条右斜链，退化成链表，查找变 O(n)。正解：用平衡树（AVL/红黑树）或跳表，保证高度始终 O(log n)。
练一练
基础二叉树共 3 层（根算第 1 层），最多有几个节点？
看答案
2⁰+2¹+2² = 7 个。第 k 层最多 2^(k−1) 个。进阶前序 [根,左,右] = [8,3,1,6,10]，中序 [左,根,右] = [1,3,6,8,10]，根是谁？
看答案
前序第一个必是根 = 8。在中序里 8 左边 [1,3,6] 是左子树，右边 [10] 是右子树。这就是树重建。自评反馈：答对了继续；树的层/遍历顺序还乱，回看二叉树那一节。
① 树=分层无环；二叉树=最多俩孩子。② BST 左小右大，理想 O(log n)。③ 前中后序按"根的位置"区分。
1.5 堆
Heap · 随时拿到最大/最小的那个想引子与大白话
堆是一棵完全二叉树，但存在数组里。规矩：父节点永远 ≥ 子节点（大顶堆），或永远 ≤ 子节点（小顶堆）。不要求兄弟之间有顺序。
核心能力：O(1) 拿到最值，O(log n) 插入、O(log n) 删除最值。这就是"优先队列"。
存在数组里时，下标 i 的左右孩子是 2i+1 和 2i+2（0-based），完全不用真的存指针。
生活里
任务调度（紧急任务先做）、医院急诊叫号、实时排行榜。
技术里
TopK 问题、堆排序、Dijkstra 算法优化、操作系统优先级调度。
坑：把堆当有序数组用。为什么错？堆只保证"堆顶最值"，不保证整体有序。想取第 2 大得先弹出堆顶再看新堆顶。要全排序请用堆排序或别的算法。
练一练
基础大顶堆堆顶是最大值还是最小值？
看答案
大顶堆堆顶是最大值；小顶堆堆顶是最小值。进阶找"最小的 k 个数"，应该用大顶堆还是小顶堆？
看答案
用大小为 k 的大顶堆：堆顶是这 k 个里最大的，新来一个比堆顶小就替换。（找最大 k 个才用小顶堆，别记反。）自评反馈：答对了继续；大小顶堆别记反，回看堆那一节的 TopK 例子。
① 堆=完全二叉树+父节点最值约束。② 取最值 O(1)，插入/删最值 O(log n)。③ TopK、优先队列的标配。
1.6 图
Graph · 节点和边织成的关系网想引子与大白话
图 = 节点（Vertex）+ 边（Edge）。树其实是图的特例（无环、连通）。地图、社交关系、网页链接、神经网络，全是图。
有向 vs 无向：微博"我关注你"是有向边（单向）；微信好友是无向边（双向）。
加权图：边有权重，比如地图上两点距离。
两种存法：邻接矩阵（n×n 表格，直观但 n² 空间）vs 邻接表（每个节点挂一串邻居，省空间）。稀疏图用邻接表，稠密图用矩阵。
度：一个节点连了几条边。有向图分入度、出度。
生活里
地铁线路图、朋友圈关系网、六度分隔理论。
技术里
推荐系统（你认识的人）、计算机网络路由、知识图谱、神经网络本身就是一张巨大的图。
坑：把图当树遍历，忘了"环"。为什么错？图里 A→B→C→A 会绕圈死循环。正解：遍历必须带 visited 标记，访问过的节点不再访问。这是图遍历和树遍历最大的区别。
练一练
基础5 个节点的完全无向图有几条边？
看答案
C(5,2) = 10 条。每两点之间一条边。进阶稀疏图（边很少）用邻接矩阵还是邻接表？
看答案
用邻接表。n=10000 的矩阵要 1 亿个格子但可能只有几百条边，浪费；邻接表只存真实边。自评反馈：答对了继续；邻接表 vs 邻接矩阵怎么选，回看图表示那一节。
① 图=节点+边，树是无环连通特例。② 有向/无向/加权按场景选；稀疏用邻接表。③ 遍历必带 visited 防环。
1.7 并查集
Union-Find · 咱俩是不是一伙的？想引子与大白话
并查集（Disjoint Set Union, DSU）专治一种问题："这两个元素是不是在同一个圈子里？"
两个操作：find(x) 找 x 的老大（根）；union(x, y) 把 x 和 y 所在两拨人合并成一拨。
两个神优化：路径压缩（find 时把沿途节点直接挂到根上）+ 按秩合并（小树挂大树）。加完之后，单次操作几乎是 O(α(n)) ≈ O(1)——α 是反阿克曼函数，比 log n 还小，可以当常数看。
生活里
社交圈聚类、判断两个文件是否属于同一目录树。
技术里
Kruskal 最小生成树算法、判断无向图连通分量、Kafka 分区分配。
坑：只 union 不优化，树长成一根筷子。为什么错？一路合并不挂好，find 变成 O(n)。正解：find 里做路径压缩（x.parent = find(x.parent)），union 时把矮树挂高树。这两招不加，等于白学并查集。
练一练
基础并查集能判断两个点之间的具体路径吗？
看答案
不能。它只回答"在不在同一集合"，不记录路径。要路径得用图遍历。进阶6 个节点，初始各自独立，union(1,2)(2,3)(4,5)，最后有几个连通分量？
看答案
{1,2,3}、{4,5}、{6} 共 3 个连通分量。自评反馈：答对了继续；并查集只回答"在不在一个集合"，回看并查集那一节。
① 并查集=查老大+认老大，专治"是否同组"。② 路径压缩+按秩合并 ≈ O(1)。③ 连通分量、Kruskal、朋友圈聚类的利器。
1.8 平衡二叉搜索树：AVL 与红黑树
Balanced BST · 不让树塌成一条链表想引子与大白话
引子：上一节说过，按 1,2,3,4,… 顺序把数据插进 BST，树会塌成一条右斜链，查找从 O(log n) 退化到 O(n)。怎么办？每次插完"扭一扭"，逼它保持平衡。这就是 AVL 和红黑树。
AVL 树：严格的体操运动员。每个节点记录左右子树高度差（平衡因子），插入后沿父链往上查，一旦差超过 ±1 就旋转。四种失衡 + 两种旋转：LL、RR 单旋；LR、RL 双旋。查找极快，但插入删除旋转多。
红黑树：放松的慢跑者。节点染红/黑，五条铁律：① 根黑；② 叶子（NIL）黑；③ 红节点的孩子必黑；④ 任一节点到其后代叶子，经过的黑节点数相同。弱平衡，树高不超过 2 log₂(n+1)。插入删除旋转少，查询稍慢一点。
技术里
C++ std::map/set、Java TreeMap/TreeSet 底层全是红黑树；Linux CFS 调度器用红黑树管进程。
面试里
AVL 考旋转四象限；红黑树考五条性质和"为什么不如 AVL 严但更常用"。
坑：把红黑树当成"B 树"。红黑树是二叉的，B 树是多叉的——红黑树是 B 树在内存里的远房亲戚（B 树为磁盘而生，红黑树为内存而生）。另外别把"红黑树高"记成严格 log₂n，它是弱平衡，高 ≤ 2 log₂(n+1)，常数更大但依然 O(log n)。
练一练
基础AVL 树按 1,2,3 插入，最后一次插入触发哪种旋转？
看答案
1→2→3 是右右链，根 1 平衡因子 −2，右孩子 2 平衡因子 −1，属 RR，对 1 左旋一次。进阶红黑树为什么规定"红节点不能有红孩子"？
看答案
这条规则防止一条路径上连续多个红节点，从而保证"任一节点到叶子的黑高相同"的前提下，最长路径不超过最短路径的两倍——这就是它"弱平衡"的数学来源。自评反馈：答对了继续；AVL 四种旋转还晕，回看平衡树那一节。
① AVL 严格平衡（平衡因子 ±1），查快写慢；红黑树弱平衡（五条色律），查写都 O(log n) 且写更省。② 插入删除都 O(log n)。③ 工程容器一律用红黑树。
1.9 B 树与 B+ 树：数据库索引的脊梁
B-Tree & B+Tree · 为什么数据库不用红黑树想引子与大白话
引子：你在 MySQL 里按 id 查一条记录，毫秒级就出来。它不是把千万行扫一遍，而是走一棵叫 B+ 树的多叉矮胖树。这棵树专门为磁盘 IO 设计。
B 树（多路平衡搜索树）：阶数 m 的 B 树，每个节点最多 m 个子节点、存 m−1 个 key。和二叉树比，它"矮胖"——100 万条数据、扇出 100，树高只有 log₁₀₀(10⁶) ≈ 3 层。每层读一次磁盘，3 次就读到。
B+ 树（B 树的数据库版）：① 数据只存在叶子节点；② 非叶子节点只存 key 当索引（叫"稀疏索引"）；③ 叶子节点用双向链表串起来。范围查询（where id between a and b）只要找到起点，顺着链表扫，不用回到根。
技术里
MySQL InnoDB 主键索引就是 B+ 树；MongoDB 文档索引用 B 树；NTFS/ext4 文件系统目录也是 B+ 树。
面试里
必考"B+ 树 vs B 树"：数据位置、叶子链表、范围查询；以及"为什么不用二叉树"。
坑：以为 B+ 树和 B 树一回事。三处关键区别：B 树每个节点都存数据，B+ 树只有叶子存数据；B+ 树叶子有链表支持范围扫描；B+ 树非叶节点不存数据，同样一个磁盘页能塞下更多 key，扇出更大，树更矮。
练一练
基础为什么范围查询（between）在 B+ 树里飞快？
看答案
叶子节点用双向链表串成一整串有序序列。找到区间起点后，顺着链表往后走即可，不用每次回根节点重新定位。进阶为什么数据库索引用 B+ 树而不是跳表？
看答案
B+ 树节点对齐磁盘页，一次 IO 读一页几百个 key，扇出大、树矮；跳表是链表结构，节点散落在内存各处，磁盘上不友好。内存里的 Redis ZSet 反而用跳表（见 1.10）。自评反馈：答对了继续；B+树为什么适合磁盘，回看 B+树那一节。
① B/B+ 树是多路平衡树，为磁盘 IO 设计，矮胖（3~4 层）。② B+ 树数据在叶子、叶子链表串联、非叶只存索引，范围查询快。③ MySQL InnoDB 索引底层。
1.10 高级数据结构：跳表 / 线段树 / 树状数组 / Trie
Skip List, Segment Tree, Fenwick, Trie · 区间查询与前缀加速想引子与大白话
引子：频繁查"数组第 3 到第 100 个数的和"，每次累加 O(n) 太慢；或输入"zhon"要秒出所有以它开头的词。这四个结构就是为这两类高频操作量身定做的。
① 树状数组（Fenwick / BIT）：利用 lowbit（x & −x）把数组切成巧妙的块。单点修改 add(i, δ) 和前缀和 query(i) 都 O(log n)，常数极小。
② 线段树：把数组建成一棵二叉树，每个节点存一段区间的和/最值。单点改、区间查询都是 O(log n)，还能加 lazy 标记做"区间整体更新"。
③ 跳表（Skip List）：给有序链表加多层"快车道"。从最高层开始跳，跳过头就下一层，查询 O(log n)。Redis 有序集合 ZSet 底层就是它。
④ Trie（前缀树/字典树）：字符路径树，根到节点拼出一个字符串，前缀天然共享。插入/查询 O(L)，L 是词长。
// 树状数组：单点加 δ，查前缀和（Python 风格伪代码） c = [0] * (n + 1) def lowbit(x): return x & (-x) # 取最低位的 1 所代表的数 def add(i, delta): # 位置 i 加 delta while i <= n: c[i] += delta; i += lowbit(i) def query(i): # 求 a[1]+...+a[i] s = 0 while i > 0: s += c[i]; i -= lowbit(i) return s
技术里
Redis ZSet 用跳表；LeetCode 区间和/区间最值用线段树/树状数组；输入法自动补全、搜索引擎建议用 Trie。
选型
只查前缀和、单点改 → 树状数组（最短最好写）；区间改+区间查 → 线段树；有序集合内存索引 → 跳表。
坑：把树状数组和线段树搞混。树状数组只能前缀和/单点改（配合差分能做区间改，但表达能力弱）；线段树能做任意区间查询和区间更新（lazy）。另外 Trie 不是哈希——它按字符路径走，前缀共享，省空间但每个节点要存 26 个子指针（或哈希）。
练一练
基础lowbit(6) 等于几？6 的二进制是 110。
看答案
6 & (−6)：取最低位的 1，即 10 = 2。进阶前缀和数组查区间和 O(1)，为什么还需要树状数组？
看答案
前缀和单点修改要 O(n) 重算一遍。树状数组单点改 O(log n)、查 O(log n)，在"改和查都频繁"时完胜。自评反馈：答对了继续；lowbit 和树状数组还绕，回看树状数组那一节。
① 树状数组 lowbit 分块，前缀和/单点改 O(log n)。② 线段树支持区间查询+区间更新（lazy）。③ 跳表是 Redis ZSet 底层；Trie 按字符路径做前缀检索。
1.11 布隆过滤器与 LRU 缓存：空间和淘汰的艺术
Bloom Filter & LRU · 用最少的空间回答"有没有"，用最聪明的规则决定"扔谁"想引子与大白话
引子：你要在 1 亿个网址里挡掉已知的恶意链接。把 1 亿个网址全存哈希表要好几个 G；但你其实只想回答"这个可能是恶意的吗"。布隆过滤器就是用一坨 bit 帮你干这事——说"没有"就一定没有，说"有"可能是误判。
① 布隆过滤器（Bloom Filter）：一个长度为 m 的 bit 数组，初始全 0。插入一个元素时，用 k 个不同哈希函数算出 k 个位置，全置 1。查询时，看这 k 个位置是否全为 1：只要有一个是 0，元素一定不在集合里；全为 1，才"可能"在（不同元素哈希撞一块儿了）。
② LRU 缓存（Least Recently Used）：内存缓存有限，新东西进来要扔旧的。规则：最久没被用过的先扔。实现 = 哈希表 + 双向链表：哈希表 O(1) 定位节点，双向链表 O(1) 把刚访问的节点移到表头、删表尾。get/put 都是 O(1)。
// LRU 缓存：哈希表 + 双向链表（Python 风格伪代码） cache = {} # key -> 双向链表节点 head, tail = 哨兵 # 双向链表头尾，表头=最近用过，表尾=最久没用 def get(key): if key not in cache: return -1 node = cache[key] move_to_head(node) # 刚访问过，提到表头 return node.value def put(key, value): if key in cache: node = cache[key]; node.value = value; move_to_head(node) else: if len(cache) == capacity: oldest = tail.prev # 表尾是最久没用的 remove(oldest); del cache[oldest.key] node = 新建节点(key, value) add_to_head(node); cache[key] = node
布隆过滤器
缓存前挡一下不存在的 key（穿透防护）、URL 去重、爬虫已访集合、邮件黑名单。Redis Bitmap / Guava BloomFilter。
LRU
CPU 高速缓存、浏览器前进后退、Redis 缓存淘汰策略（allkeys-lru）、MySQL Buffer Pool。
坑一：把布隆过滤器当精确查询用。它有误判率，k 和 m 没选好误判率飙升——说"有"必须再查真存储确认。另外它不支持删除（多个元素共享 bit），要删就得用计数布隆。坑二：LRU 用单链表实现——删除表尾能 O(1)，但定位中间节点要 O(n)，必须配哈希表。Python 的 OrderedDict / functools.lru_cache 就是这套。
练一练
基础布隆过滤器查询时只要有一个哈希位置是 0，说明什么？
看答案
说明这个元素一定不在集合里（插入时所有位置都被置 1 了），所以可以立刻拒绝，绝不漏判。进阶LRU 为什么用"最近最少使用"而不是"从未使用"？扫描一遍全是冷数据会怎样？
看答案
LRU 假设"刚用过的马上还会用"（局部性原理）。若一次冷数据扫描把热点全挤出缓存，就是经典的"缓存污染"——所以有 LRU-K、LFU（按访问频次）等改进策略。自评反馈：答对了继续；布隆只假阳不假阴、LRU 是哈希+双向链表，哪条还绕就回看。
① 布隆过滤器：k 个哈希 + bit 数组，说"没有"必没有，说"有"再确认。② LRU：哈希表+双向链表，get/put O(1)，扔最久没用的。③ 一个管"省空间的存在性"，一个管"有限内存的淘汰"。
① 用自己的话解释：挑两种数据结构（比如数组和链表），各自说一句"它擅长什么、怕什么"。
② 举个反例 / 生活例子：反例——什么场景下你以为用哈希表最快，结果反而拖慢了系统？（提示：哈希冲突、频繁扩容、需要有序遍历时）
③ 哪里还说不清：红黑树到底怎么旋转、B+树和跳表差在哪，哪一处还讲不顺？把它标成第一个要复习的点。