动态数组

普通数组通常有确定的槽位数，而集合的元素数量会变化。动态数组记录已经存放多少元素，并允许后备数组保留尚未使用的位置。合法下标根据逻辑长度判断，容量则决定何时需要扩大存储。

在元素或引用占固定大小的常见模型中，按下标访问可以直接定位槽位，而不必从第一个元素开始逐一追踪。保留空余容量会消耗存储，却能让一段追加操作共用已经分配好的数组。

参考：[1]

数组满后，可以另分配较大的数组，把原有元素复制过去，再让结构使用新存储。容量按固定倍数增长，是控制长期复制总量的一种办法；扩容时单次复制的成本仍与已有元素数量有关。

删除后的收缩通常采用另一条阈值。教材中的栈在数组满时翻倍，而在占用降到约四分之一时才减半。增长与缩小之间留有空隙，避免结构刚缩小就被下一次插入迫使再次扩容。

参考：[1] [2]

从空结构开始，按适当翻倍策略连续在末尾追加，可以取得常数摊还成本；在中间插入却还要为新元素腾出位置，把后面的内容向后移动。删除中间元素也可能需要移动其后的内容来填补空位。

因此，动态数组适合随机访问和较多末尾操作的工作方式，但不能只凭“动态”就推断任何位置的修改都便宜。评估时还要分清逻辑操作次数、搬移元素数量和容量占用，以及应用是否能接受偶尔发生的较长扩容。

参考：[1]