数据结构

数据结构由一种表示和一组不变量组成，它们共同使某些操作变得高效。应当根据工作负载做选择，而不是套用笼统的“优缺点”排名。

从操作开始

需求	典型表示	优势
按位置随机访问	数组 / 动态数组	$O(1)$ 索引，局部性好
已知节点处局部插入	链表	只需重接指针
后进先出访问	栈 ADT	单端访问纪律
先进先出访问	队列 ADT	按顺序处理
精确键查找	哈希表	期望常数时间查找
有序键与范围	平衡搜索树	对数时间的有序操作
反复取得最小值或最大值	堆	对数时间更新，常数时间访问根
任意关系	图表示	遍历和路径算法

表示与接口

栈或队列是抽象数据类型：它的契约限制了可以移除哪个元素。底层可以用数组、链式节点或其他容器实现。数组和链表描述的则是存储组织方式。

需要追问的问题

1. 哪些操作占主导？它们的最坏或摊销成本是多少？
2. 修改后，引用、索引或迭代顺序是否必须保持稳定？
3. 容量是否有界？操作期间是否允许分配内存？
4. 缓存局部性和单元素开销有多重要？
5. 并发、持久化或所有权是否属于契约的一部分？

渐近复杂度是必要信息，但并不完整：两个 $O(1)$ 操作在内存分配、间接寻址和局部性方面可能相差很大。

看整套工作，而非孤立操作

假设程序先收到 $n$ 个任务，再按到达顺序处理。把它们追加到动态数组末端，总工作量为线性；但如果反复删除位置零，就会移动 $(n-1)+(n-2)+\cdots+1$ 个引用，产生平方级成本。使用两端操作成本恒定的队列，总成本仍为线性。如果任务需要经常按数字位置访问，动态数组可能反而更合适。线性结构对比把这些需求与具体实现联系起来。

表格只为含 $n$ 个元素的内存结构提供选型方向，不是通用保证。哈希查找要求控制装载率并采用合适的哈希方式，而且仍需计算键的哈希并比较键；碰撞可能使最坏查找退化为线性。平衡树的界计算的是比较次数；访问堆根则要求堆非空。分不清最坏、期望与摊销成本时，先读时间复杂度。

来源

• Open Data Structures

我的阅读 · 打开过的笔记会记在当前浏览器里。