动态数组

动态数组用空余空间购买增长余地。大多数追加只占用已经预留的下一个槽位，偶尔才整体搬家；昂贵搬迁不是消失了，而是由此前一长串便宜操作共同分摊。容量按常数因子增长的关键在于：每次搬迁后，新空位与已有元素同量级，所以在再次搬迁前必然发生足够多的新追加。

连续布局保留了普通数组理路数组Array以连续整数下标支持随机访问的有限序列结构。的地址计算与缓存局部性，却也继承了它的限制。中间插入或删除会改变后缀元素的位置，通常仍需 $\mathrm{\Theta }(n)$ 次搬移；“可变长”只解决容量管理，不会让所有位置的修改都变成常数时间。

从容量 $1$ 开始依次追加元素，容量沿 $1,2,4,8,\dots$ 增长。追加第五个元素时，容量从 $4$ 扩为 $8$，这次操作复制四个旧元素后再写入新元素，明显不是最坏 $O(1)$；但前四次追加已经跨过了足够多的便宜步骤，整段序列的总复制量受几何级数控制。对需要稳定低延迟的程序，这种摊还保证仍可能不够，因为某一次暂停会随数组大小增长。

若每次满时只把容量增加一格，第 $k$ 次扩容要复制 $k$ 个元素，前 $m$ 次追加的复制总量为 $1+2+\cdots +(m-1)=\mathrm{\Theta }(m^2)$，摊还常数界随即消失。收缩也会造成类似问题：若在装载率恰降到 $1/2$ 时立刻缩半，那么一次删除触发收缩后，紧接着一次追加便可能再次扩张，交替操作会令结构在两个容量间反复整体复制。扩张与收缩阈值之间的滞回区正是为阻止这种抖动。

扩容还会使指向旧存储区的地址、迭代器或引用失效；哪些引用保持有效取决于语言和容器契约。容量是实现状态，不等于可观察的逻辑长度，也不能把尚未初始化的槽位当成序列成员。

动态数组是向量、可变列表、字节缓冲区与许多哈希表桶数组的常见底层表示。它把 $O(1)$ 随机访问、良好局部性和摊还 $O(1)$ 尾部追加组合在一起；若主要操作落在两个端点，循环数组实现的双端队列理路双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。可避免首部操作搬移；若频繁修改中间位置，可以比较链表或分块结构，但还要计入定位位置的成本。

势能法理路势能法Potential method用数据结构状态势函数的增量调整单步记账，以控制操作序列的总成本。可把空余容量或装载率偏离目标的程度编码成势，统一证明扩张与收缩的摊还界。工程实现还需考虑增长因子对空间与复制次数的取舍：因子较大减少搬迁，代价是更多闲置空间；因子接近 $1$ 节省空位，却提高总复制量。渐近结论要求增长因子与 $1$ 保持固定距离。

顺序数组去摊还化理路去摊还化Deamortization把批量工作拆成有截止期的微步，以顺序动态数组的读、写、追加证明权威槽不变量、迁移期限和逐操作最坏界。把一次整体复制分成固定预算的微步，按迁移前沿决定读写旧区或新区，并证明下一次扩容前完成。它在明确的分配成本模型下支持最坏常数的追加、读、写；迁移期间逻辑序列跨两块存储，因此不直接保留单一连续缓冲区接口。