动态数组是一种数据结构,将有序的元素序列存储在数组中,其底层存储空间可随着序列增长而被替换或扩展。它支持常数时间的按索引访问;采用适当的扩容策略时,在末尾插入元素的摊还时间也是常数。与固定大小的数组不同,动态数组的逻辑长度可以在程序执行期间改变,而不必由调用者管理每一次存储分配。
表示方式与基本操作
传统的动态数组维护三项信息:
- 底层存储空间:一块连续的内存区域,用于存放元素。
- 长度或大小 :序列中当前的元素数量。
- 容量 :已分配的存储空间能够容纳的元素数量。
这三者满足以下不变式:
元素占据从 到 的位置;剩余容量是预留空间,而不是序列中的额外元素。有些实现会初始化这些未使用的槽位,另一些则不进行初始化。
由于各元素占用的槽位大小相同,元素 的位置可以按下式计算:
其中, 是基地址, 是槽位大小。槽位既可以直接存储值,也可以存储对其他位置上对象的引用。槽位连续并不一定意味着它们引用的对象也连续存放。
追加操作在发现有空余容量时,会将新元素写入下一个槽位,并增加长度。当数组已满时,通常会执行以下步骤:
- 分配一块更大的存储空间。
- 将现有元素复制或移动到新空间中。
- 释放原来的存储空间。
- 添加新元素。
有些内存分配器可以在原址扩展内存块,从而避免迁移元素,但常规的性能保证并不以此为前提。
“动态数组”一词有时也指长度在运行时确定、但此后不能再改变的数组。可调整大小的动态数组是一个更具体的概念:它的逻辑长度在构造完成后仍可反复改变。
操作与复杂度
常见操作的时间复杂度如下。这里假设对单个元素的访问、复制或移动以及销毁均耗费常数时间,并且容量采用几何增长策略。
| 操作 | 典型复杂度 |
|---|---|
| 按索引读取或替换元素 | |
| 读取长度或容量 | |
| 追加一个元素 | 摊还 ;最坏情况 |
| 删除最后一个元素 | 不缩容时为 ;缩容时可能为 |
| 在任意位置插入或删除 | 最坏情况 |
| 在无序序列中查找 | |
| 使用二分查找在有序序列中查找 | |
| 遍历所有元素 |
在位置 插入元素,通常需要将后面的 个元素向右移动一位。同样,删除元素时,如果需要保持元素顺序,就必须将后续元素向左移动。
如果不关心顺序,也可以用最后一个元素替换待删除元素,再减小长度。在不调整存储空间大小的情况下,这种做法只需常数时间,但会改变序列顺序。
有序动态数组支持二分查找,不过将新元素插入到适当的有序位置,通常仍需要线性时间来移动元素。
扩容策略与摊还分析
设计动态数组时,一个核心问题是:底层数组满后,应额外分配多少容量。
几何增长
一种常见策略是将容量乘以固定因子 ,同时考虑取整和最小初始容量:
容量翻倍是一种常见做法,但也有实现采用更小的增长因子。批量插入可能需要一次性分配更大的空间,以立即容纳所有待插入元素。
采用几何增长时,单次追加可能代价较高,但连续执行大量追加操作的总体效率很高。以容量翻倍为例,历次扩容时迁移的元素数量构成一个几何级数:
从具有固定初始容量的空数组开始,执行 次追加,元素迁移的总次数为 。再加上写入这 个新追加元素的操作,总工作量仍为 ,因此根据摊还分析,每次追加的代价为 。
摊还复杂度并不是对随机输入取平均,而是对一系列操作的总成本给出界限,即使其中某些操作会触发代价高昂的存储空间调整。单次追加仍可能耗费线性时间。
加法增长
每次仅增加固定数量的槽位,无法提供相同的保证。对于固定的正增量 ,反复扩容可能需要移动的元素总数约为:
当 固定时,总迁移成本为 ,因此追加操作的摊还代价是线性而非常数。
容量权衡
较大的增长因子可以降低分配频率和元素迁移的总工作量,但会在扩容后留下更多闲置空间。较小的增长因子可以减少这部分预留容量,代价是更频繁地重新分配存储空间。
从已满的容量 扩容到约 后,若不计新插入的元素和取整的影响,空余容量约为 。迁移期间,新旧存储块可能同时存在,因此内存使用峰值可能显著超过最终容量所需的内存。
缩容与预留
删除元素不一定会减小容量。保留存储空间可以避免序列再次增长时反复分配内存,但也可能使一个很短的序列仍占据一大块内存。
自动缩容需要采用使扩容阈值与缩容阈值相互分离的策略。如果数组在满时将容量翻倍,而在元素数量降至容量的一半时立即将容量减半,那么在该边界附近交替插入和删除,就可能反复触发线性时间的元素迁移。
因此,一种常见的教科书策略是:
- 数组满时,将容量翻倍;
- 长度降至容量的四分之一时,将容量减半;
- 保留一个最小容量。
这种阈值分离通常称为滞回,它使相邻两次重新分配之间有足够多的低成本操作,从而使尾部插入和删除保持摊还常数时间。
许多接口还区分以下三种操作:
- 预留(reserve):增加容量,但不改变长度。
- 调整长度(resize):改变逻辑长度,按需创建或删除元素。
- 压缩或缩容(trim 或 shrink):请求减少未使用的容量。
如果已知最终大小,提前预留空间可以避免反复迁移元素。不过,如果实现严格按照预留请求分配空间,那么每次只为下一个元素预留恰好够用的空间,就可能破坏几何增长策略。每次删除后都压缩容量也可能导致类似问题。预留和缩容的具体保证取决于接口。
编程语言中的实现
许多编程语言及其标准库都提供动态数组,例如 C++ 的 std::vector、Java 的 ArrayList、Rust 的 Vec 和 Python 的 list。
这些实现的总体设计相近,但在重要细节上有所不同:
- 有些直接存储元素值,有些则存储对单独分配的对象的引用。
- 有些公开容量信息,并提供显式的预留操作。
- 有些会初始化所有已分配的槽位,有些则仅在逻辑长度增长时构造元素。
- 增长因子和缩容策略可能属于实现细节,而不是接口保证。
- 对象的构造、移动、复制和销毁可能带来额外成本,超出简单的元素操作恒定成本模型。
在C编程语言中,动态数组通常使用指针、长度、容量和内存分配函数来实现。为了保证正确性,必须检查内存分配是否失败,并在计算所需字节数时避免整数溢出。
JavaScript 数组提供可调整大小的索引集合,但其语言层面的行为比传统的连续存储动态数组更广泛。引擎可能对稠密数组和稀疏数组采用不同的内部表示,因此,程序可见的数组抽象并不意味着其底层采用某一种固定的存储布局。
内存行为与引用有效性
连续存储通常使动态数组具有良好的空间局部性。顺序遍历可以有效利用 CPU 缓存,并且不需要传统链表中每个元素都要携带的链接字段。
重新分配存储空间会带来一个重要后果:元素地址可能改变。如果接口允许直接获取指向存储空间内部的指针、引用或迭代器,扩容就可能使这些句柄失效。即使没有重新分配存储空间,插入或删除也可能使指向被移动元素的句柄失效。确切的有效性规则取决于具体实现。
对于存储引用的数组,需要区分存储槽位和被引用的对象。移动槽位不一定会移动对象本身。
在使用垃圾回收的系统中,可能需要清除未使用槽位中残留的已删除引用,以免无意中使对象继续存活。在显式管理对象生命周期的系统中,删除元素可能会调用其析构函数。
普通动态数组并不会自动保证并发修改的安全。当多个线程共享动态数组时,调整存储空间大小和更新结构通常需要适当的同步(计算机科学)机制。
应用与替代方案
动态数组广泛用作通用序列、临时缓冲区、记录集合,以及其他数据结构的底层存储。
栈(数据类型)很适合用动态数组实现,因为入栈和出栈都在同一端进行。基于数组的二叉堆通过索引关系隐式存储树结构;尽管存储扩容的摊还时间为常数,恢复堆序仍使插入和删除操作需要对数时间。
如果需要频繁在开头插入元素,动态数组就不太适合。若队列(数据类型)在每次删除后都移动所有剩余元素,就会产生线性工作量。循环缓冲区允许逻辑序列在存储区域中回绕,从而避免这种移动。
与链表相比,动态数组支持高效的按索引访问,通常也具有更好的局部性;但链式结构可以在已知节点处以常数时间插入或删除,而不必移动后续元素。这一优势并不包含定位该节点的成本。
传统动态数组的主要局限包括元素迁移造成的停顿、闲置容量、必须分配足够大的连续内存,以及在中间按序插入或删除需要线性时间。采用几何增长并控制多余容量时,其空间复杂度为 ;但如果数组在大量删除元素后仍保留原有存储空间,容量就可能远大于当前长度。
对于严格要求单次操作延迟的工作负载,仅有摊还保证可能并不足够。分段存储或渐进式迁移可以减少大规模复制带来的长时间停顿,但会增加管理开销,也可能无法再保证所有元素都位于同一块连续内存中。