数据结构可视化
数据结构不仅保存值，也决定哪些操作快、哪些操作慢。本组把哈希冲突、树查找、堆上浮等过程与代码同步，展示这些取舍。
选择结构应从常做的操作出发。栈只开放最近压入的一端；哈希表通过键计算位置，平均查询快，但不提供按键排序；平衡树保持排序，以对数级操作成本换取有序访问。
如何阅读数据结构
运行一个操作时，观察三件事：
- 快在哪里，代价是什么：栈的压入弹出为 O(1)，但只能接触栈顶。哈希表平均查找为 O(1)，却不支持按键顺序遍历的保证。
- 如何定位：链表逐个追指针，哈希表从键计算索引，二叉搜索树比较后向左或向右，堆则主要提供极值端，不擅长任意键查找。
- 保留哪种顺序：链表、栈和队列保留特定序列或进入顺序，BST 保持键序，堆只保留足够确定极值的局部顺序。哈希表本课不维护键序。
操作比较
下表注明平均、最坏或摊还成本。普通哈希表严重冲突、未平衡 BST 退化时，都可能达到 O(n)。链表的常数操作假设已知所需节点或前驱，不包含寻找位置的成本。栈与队列的 O(1) 假设两端操作都是常数时间；队列课代码用列表 pop(0) 出队，为 O(n)。
| 结构 | 查找 | 插入 | 删除 | 顺序 |
|---|---|---|---|---|
| 动态数组 | O(n)，按索引 O(1) | 末尾摊还 O(1)，位置 i 为 O(n) | 位置 i 为 O(n) | 索引顺序 |
| 栈 | 不提供任意查找 | 压入 O(1) | 弹出 O(1) | LIFO，只用顶端 |
| 单调栈（右侧第一个更大值） | 整体扫描 O(n) | 压入 O(1) | 弹出 O(1) | 等待候选值从底到顶非递增 |
| 队列 | 不提供任意查找 | 入队 O(1) | 出队 O(1) | FIFO，操作两端 |
| 单链表 | O(n) | 已知插入前驱时 O(1) | 已知所需前驱时 O(1) | 链接顺序 |
| 双向链表 | O(n)，可从两端走 | 已知节点时 O(1) | 已知节点时 O(1) | 双向链接顺序 |
| 循环链表 | O(n)，可从任一节点走 | 已知所需节点时 O(1) | 已知所需前驱时 O(1) | 尾部回到头部 |
| 哈希表 | 平均 O(1) | 平均 O(1) | 平均 O(1) | 不维护键序 |
| 二叉搜索树 | 平均 O(log n) | 平均 O(log n) | 平均 O(log n) | 键序 |
| AVL 树 | 最坏 O(log n) | 最坏 O(log n) | 最坏 O(log n) | 高度平衡的键序 |
| 红黑树 | 最坏 O(log n) | 最坏 O(log n) | 最坏 O(log n) | 颜色不变量约束的键序 |
| Trie | O(L) | O(L) | O(L) | 前缀路径 |
| 堆 | 不提供高效任意查找 | O(log n) | 取出极值 O(log n) | 局部优先顺序 |
| 并查集 | 查根摊还近 O(1)（按秩合并＋路径压缩） | 合并摊还近 O(1) | 不提供普通删除 | 不相交集合 |
| 图：邻接表／矩阵 | 查边 O(deg(u))／O(1) | 加边 O(1)／O(1) | 删边 O(deg(u))／O(1) | 邻接关系 |
栈和队列限制访问方式，哈希表不提供键序，树放弃数组式 O(1) 索引以支持有序动态操作。不同取舍适合不同工作负载，不能只比较某一列。
建议学习顺序
先学动态数组。连续后备存储提供 O(1) 索引，中间插删需要 O(n) 搬移；空间满时扩容、复制，因此追加的常数成本是摊还结果。接着学栈和队列，理解 LIFO 与 FIFO 的限制。普通栈之后紧接着学习单调栈：它仍然只使用 push/pop，却通过只保留按值有序的未解决候选，把“右侧第一个更大值”这类扫描压到 O(n)，并直接展示“每个下标只进一次、最多出一次”的摊还分析。
单链表用指针链替代连续槽位，已知位置时插入可为 O(1)，寻找位置仍是 O(n)。双向链表每节点多存一个指针，换来双向遍历和已知节点的 O(1) 删除。循环链表把尾部接回头部，适合轮转；循环边界也从遇到空指针变成是否回到起点。
再学两种哈希表：链式冲突和开放寻址。键计算位置后，还要处理不同键落到同一个槽位。进入搜索树前，先学树基础，在小树上理解根、叶、高度、深度和三种遍历。
二叉搜索树按比较向左或右走，查找成本取决于高度。AVL 树维护高度，插入后用 LL、RR、LR、RL 旋转保证最坏路径为对数级。红黑树用较宽松的颜色不变量保持同样的最坏上界，叔节点的颜色决定向上重染色，还是用一到两次旋转修复。
Trie每条边对应字符，共享前缀只存一次，适合前缀查询。图的表示把同一组边分别存为邻接行或方阵，比较查边与稀疏遍历的成本。并查集回答两个元素是否属于同组，结合按秩合并与路径压缩达到近常数摊还成本，也是 Kruskal 判环的工具。
最后学堆。它放弃完整排序，只维护极值所需的顺序：看堆顶为 O(1)，插入和取出极值为 O(log n)。这是优先队列和堆排序的基础。
全部数据结构可视化课程
选择结构，执行操作，改变输入，逐步检查代码高亮与状态变化。