数组与动态数组

数组连续存储固定大小的槽位，因此位置 $i$ 的地址可以由基地址和步长计算：

$$\operatorname{address}(i)=\operatorname{base}+i\cdot\operatorname{stride}.$$

这带来了常数时间的索引访问和良好的空间局部性。

静态与动态

• 静态数组的容量固定。
• 动态数组同时记录长度和容量。容量用尽时，它会分配更大的底层数组并复制已有槽位。

按几何比例扩容，可使末端追加的摊销成本为 $O(1)$，即使某次扩容本身需要 $O(n)$。这是总体保证，不代表每次追加都具有恒定延迟。

操作成本

操作	典型成本
按索引读写	$O(1)$
顺序遍历	$O(n)$
末端追加	摊销 $O(1)$
末端弹出	不缩容时 $O(1)$；合理缩容策略下摊销 $O(1)$
在前端或中间插入/删除	$O(n)$ 次移动
搜索无序值	$O(n)$

二分搜索只有在维持有序且能够随机访问时才是 $O(\log n)$；维持顺序可能让更新变得昂贵。

语言边界

底层类型化数组通常内联存储同质值。Python list 则是对象引用的动态数组：引用槽位连续，但所引用对象可以位于别处，也可以具有不同类型。

使用边界

随机访问、紧凑迭代、排序、矩阵和堆的底层存储适合使用数组。如果频繁移动元素将成为主要成本，就不要用数组前端操作实现队列。

这些复杂度从何而来

表中按长度为 $n$ 的序列计算固定大小槽位的操作次数，采用 Open Data Structures 的分析方式。下标运算、移动或比较一个槽位视为常数时间；昂贵的元素比较、对象销毁和分配延迟需要另算。地址公式使用从零开始的下标，有效范围为 $0$ 到 $n-1$。容量是已分配的存储空间，长度是实际元素数，满足 $0 \le n \le \text{capacity}$；空余槽位不属于有效序列。

假设初始容量为 1，每次扩为两倍。追加八个元素时，三次扩容分别复制 1、2、4 个旧槽位，总共七次复制，加上八次新元素写入。一般而言，从空数组追加 $m$ 次，所复制容量的几何级数之和小于 $2m$，所以总工作量是 $O(m)$。若每次只增加一个槽位，则要复制 $1+2+\cdots+(m-1)$ 个槽位，总成本变成平方级。两倍扩容只是分析示例，不是 Python 规定的扩容比例。

末端删除无需移动元素。它的 $O(1)$ 成本以不调整底层容量为前提：会缩容的实现可能在某次删除中复制 $O(n)$ 个槽位，只能给出摊销保证。等到占用率明显降低再缩容（例如占用四分之一时把容量减半），可避免交替插入、删除不断触发大量复制。

一次具体的插入

values = [10, 20, 30]
values.insert(1, 15)
assert values == [10, 15, 20, 30]
assert values.pop(1) == 15
assert values == [10, 20, 30]

插入时把 20 和 30 右移，删除时再左移。因此，保存的下标在修改后可能指向另一个元素。底层重新分配内存还可能使指向旧数组的指针失效；Python 对象引用与这种槽位地址不是一回事。Python 越界读取，以及对空列表执行 pop()，都会抛出 IndexError。

来源

• Open Data Structures：基于数组的列表

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