线性数据结构

线性结构按序列组织元素，但它们的表示方式和允许的操作并不相同。

对比

结构	索引访问	末端插入/删除	已知内部位置的插入/删除	主要权衡
动态数组	$O(1)$	摊销 $O(1)$	$O(n)$ 次移动	局部性和随机访问
单链表	$O(n)$	有尾指针时插入为 $O(1)$；删除尾部为 $O(n)$	已知前驱后为 $O(1)$	间接寻址和节点开销
双链表	$O(n)$	维护两端时为 $O(1)$	已知节点后为 $O(1)$	每个节点多一条链接
栈	不属于接口契约	在栈顶压入/弹出	接口不允许	LIFO 纪律
队列	不属于接口契约	在相对两端入队/出队	接口不允许	FIFO 纪律

寻找内部节点或位置与修改它是两件事。“链表插入是 $O(1)$”这句话隐含了相关节点或前驱已经可用这一前提。

选择规则

• 通用序列和以迭代为主的工作，优先使用动态数组。
• 当稳定的节点身份和局部拼接占主导时，考虑链式节点。
• 如果受限访问比通用列表更能表达算法不变量，就暴露栈或队列接口。
• 有界队列若要求存储可预测，可使用环形缓冲区。

在 Python 中，list 是对象引用的动态数组；collections.deque 支持高效的双端操作。

按下一步操作选择

需要直接取第 100 项时，读数组。算法已经持有节点、需要在旁边拼接时，读链表；只知道数字位置，并不等于已经拿到节点。要匹配最近一个尚未闭合的分隔符，用栈。要按到达顺序处理，用队列。

这里的 $n$ 是已存元素数，移动一个槽位或沿一条链接访问的成本视为常数。摊销成本约束的是一整串操作，包括偶尔发生的扩缩容，不是对随机输入取平均。栈和队列两行描述接口，具体实现成本需要分别查看。这些比较针对内存中的顺序容器，不涉及并发消息投递或磁盘索引。

来源

• Open Data Structures：接口

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