动态数组
动态数组在连续内存中保存元素，区分实际元素数 size 和可容纳数量 capacity。按索引访问只需计算 address + index × element_size，所以读写为 O(1)。连续布局的成本体现在插入、删除和扩容时。
可以把它看成右侧留有空位的一排编号格子。追加先使用第一个空位；没有空位时，申请两倍长度的新数组，搬走全部值，再释放旧数组。少数昂贵的扩容支持多数便宜的追加。
动态数组如何工作
底层数组有 capacity 个位置，前 size 个有效，其余备用。本课删除后不自动缩容。
- 索引访问：
get、set直接算地址，不经过邻居。索引 0 与 9,000 都是同类计算。 - 追加：先检查
size == capacity；有空位就写入索引size，然后增加size。 - 扩容：满时申请
2 × capacity，逐个复制size个元素，释放旧数组，最后追加。单次复制为 O(n)，但几何增长使多次追加的总成本保持线性，每次摊还 O(1)。 - 移位：索引 i 插入时，把从 i 开始的
size − i个元素右移；删除时把后面的size − i − 1个元素左移。最坏 O(n)，头部最贵，尾部无需移位。
插入必须从右向左复制，先把末尾搬到新位置，避免覆盖还没搬走的值。删除反过来，从左向右填补空位。
逐步演示
默认空数组 capacity = 4，运行九项操作：
append(5)：写索引 0，size = 1。append(8)：写索引 1，size = 2。append(2)：写索引 2，size = 3。append(9)：写索引 3，size == capacity == 4，数组已满。append(4)：先扩为容量 8，依次复制5、8、2、9，释放旧数组，再把4写入索引 4。结果[5, 8, 2, 9, 4]，size = 5、capacity = 8。这次追加包含四次复制。get(2)：直接读取索引 2，得到2，不扫描。set(2, 6)：直接改写为6，得到[5, 8, 6, 9, 4]。insert(1, 7)：按从后向前的顺序，把4移到索引 5、9到 4、6到 3、8到 2，再把7写入 1。得到[5, 7, 8, 6, 9, 4]，size = 6。一次插入移动四个元素。remove(3)：移除值6，把9从 4 移到 3、4从 5 移到 4，size减为 5。结果[5, 7, 8, 9, 4]，最后一个占用位置恢复备用。
结束时容量 8、元素 5，剩余三个空位。画布右侧虚线格表示备用容量，实线格下方的括号表示 size。
时间与空间复杂度
| 操作 | 时间 | 原因 |
|---|---|---|
get(i) / set(i, v) | O(1) | 按索引算地址 |
append(v) | 摊还 O(1)，扩容时 O(n) | 通常一次写入，偶尔复制到两倍数组 |
insert(i, v) | O(n) | 右移 size − i 个元素 |
remove(i) | O(n) | 左移 size − i − 1 个元素 |
存储占 O(capacity)。只追加、按倍数增长时，它是元素数的 O(n)，扩容刚完成时约有一半空位。由于本课不缩容，大量删除后的已分配空间取决于历史最大容量，不能再只用当前 size 估计。
本课每次扩大两倍。实现也可选择其他大于 1 的常数因子，仍可得到摊还 O(1) 追加。常见实现示例包括 Java ArrayList 约 1.5 倍、C++ std::vector 常见 1.5–2 倍、CPython list 约 1.125 倍；具体策略随实现和版本而异，不是接口承诺。
边界情况
- 尾部插入或删除：
insert(size, v)等同追加，无移位，但满时仍要扩容；remove(size − 1)只减小size，为 O(1)。 - 头部插入或删除：
insert(0, v)移动全部原元素，remove(0)移动全部剩余元素。这是最坏情况；链表的头插则为 O(1)。 - 索引越界：
get、set、remove要求0 ≤ i < size；insert允许0 ≤ i ≤ size。否则抛出IndexError；输入面板会禁用这类索引的按钮，动画不会执行。 - 空数组：
get、set、remove没有有效索引；insert(0, v)有效。 - 显示上限：画布在容量 16 停止翻倍，实际结构没有这个固定上限，受内存或实现限制。
常见错误
- 把每次追加都看作 O(1)。 触发扩容的单次追加复制全部元素。O(1) 是多次操作的摊还成本。
- 移位方向颠倒。 插入从低索引往高复制，会覆盖待移动的值，把同一值传播到后面。插入从高到低，删除从空位向后。
- 删除后留洞。 动态数组的有效区连续，不是在 i 留下
null。后面的元素必须补位。 - 混淆
size和capacity。 有备用位置不代表能读取；有效索引仍止于size − 1。 - 忽略工作负载。 动态数组擅长索引访问与顺序扫描，头部插入和删除较贵。按主要操作选择数组或链表。