这份速查表按抽象数据类型重新分类。原文把对称矩阵、稀疏矩阵列为链表变种，也把 KMP、查找等算法混入数据结构层级，容易造成概念混淆。

类别 常见实现或变体 典型操作与复杂度
动态数组 Vector、ArrayList 随机访问 $O(1)$；尾部均摊插入 $O(1)$；中间插删 $O(n)$
链表 单链表、双向链表、循环链表 已知位置后插入通常为 $O(1)$；单链表删除还需要前驱，双向链表持有目标节点即可 $O(1)$ 删除；按下标访问 $O(n)$
栈 数组栈、链式栈 入栈、出栈、查看栈顶通常为 $O(1)$
队列 循环队列、链式队列、双端队列 普通队列的入队、出队通常为 $O(1)$；双端队列依实现可在两端达到 $O(1)$
哈希表 链地址法、开放寻址法 在散列质量和负载因子受控时，期望查找/删除 $O(1)$、插入均摊期望 $O(1)$；最坏 $O(n)$
并查集 Union-Find / DSU 路径压缩 + 按秩或按大小合并后，每次操作的均摊复杂度为 $O(\alpha(n))$
树 二叉树、BST、AVL、红黑树、Trie、B/B+ 树 有序平衡树查找/更新通常为 $O(\log n)$
堆 二叉堆、d 叉堆、二项堆、斐波那契堆、配对堆 查看极值 $O(1)$；二叉堆插入/删除极值 $O(\log n)$
图 邻接表、邻接矩阵、边集 BFS/DFS 使用邻接表为 $O(V+E)$，使用邻接矩阵为 $O(V^2)$；稠密图或频繁判边时可考虑邻接矩阵
字符串索引 Trie、后缀数组、后缀自动机 用于前缀、子串和字典匹配；KMP/BM 属于匹配算法而非数据结构

这里的 $\alpha(n)$ 是反 Ackermann 函数，在实际可达到的数据规模下增长极慢，但它并不等同于严格的 $O(1)$。

复杂度只描述增长趋势，实际选择还要考虑缓存局部性、内存开销、数据规模和语言标准库实现。例如小规模数据上，连续数组常因缓存友好而优于理论复杂度相近的指针结构。

参考资料