数据结构与算法 / 系统课时

动态数组

动态数组

动态数组在固定长度数组之上增加了自动扩容能力。本课将区分长度与容量,拆解倍增扩容的执行过程,并通过一个可运行的 Java 示例验证追加操作为什么单次可能是 O(n)O(n),长期摊还后仍可视为 O(1)O(1)。

学习目标

  • 区分动态数组的有效长度 size 与底层容量 capacity。
  • 理解倍增扩容、元素复制和摊还复杂度的关系。
  • 实现支持追加、按下标读取和自动扩容的整数动态数组。

知识导图

text
动态数组
├── 状态
│   ├── size:有效元素数量
│   └── capacity:底层数组长度
├── 追加
│   ├── 容量足够:直接写入
│   └── 容量不足:扩容、复制、写入
└── 复杂度
    ├── 普通追加:O(1)
    ├── 单次扩容:O(n)
    └── 摊还追加:O(1)

问题背景或应用场景

普通数组创建后长度固定。程序无法预先知道最终数据量时,容量过小会导致无法继续写入,容量过大又会长期占用未使用空间。动态数组通过维护底层数组和有效元素数量,在空间不足时创建更大的数组并复制旧元素,从而兼顾连续存储、随机访问和可增长性。

Java 的 ArrayList、C++ 的 std::vector 都体现动态数组思路。Java API 承诺 ArrayList 的追加有摊还常数成本,未规定必须采用本课的倍增策略。本课先实现最小版本,重点关注容量管理和追加成本,为后续分析顺序表的插入、删除及摊还分析打基础。

核心原理

动态数组至少维护两个状态:size 表示已经存放的元素数量,elements.length 表示当前可用容量。合法元素只位于下标区间 [0, size);即使底层数组后面仍有位置,也不能把那些默认值当成有效数据。

追加元素时先判断 size == elements.length。若容量仍有剩余,就把新值写入 elements[size],再将 size 加一;若容量已满,则先创建更大的数组,把旧元素复制过去,再完成写入。

动态数组倍增扩容与元素复制过程

设初始容量为 C0>0C_0>0,无删除且成功追加 m 次后容量为 C。每次扩容复制整个已满数组,复制总数为 C−C0C-C_0,因为各次旧容量是倍增的等比和。只要发生过扩容,最后一次旧容量为 C/2,扩容追加时已有 C/2+1C/2+1 个有效元素,因此 C<2mC<2m。未发生扩容时复制量为 0。只计复制与新写入时,m≥1 的任意前缀总操作数小于 3m。固定初始容量下,即使把数组分配时的初始化计入,几何级数也保持线性总成本。

操作 最坏时间复杂度 摊还时间复杂度 说明
末尾追加 O(n)O(n) O(1)O(1) 扩容时需要复制旧元素
按下标读取 O(1)O(1) O(1)O(1) 通过连续内存直接定位
扩容复制 O(n)O(n) 不单独计算 与当前有效元素数量成正比

存储按容量 C 计为 Θ(C),若用户选择很大的初始容量,早期不能只按 size 估算。扩容复制期间新旧数组可同时存活,扩容完成后也可能保留空闲槽位。倍增策略用额外空间换取较少的复制次数;若每次只增加一个槽位,连续追加 nn 次可能产生 O(n2)O(n^2) 的总复制成本。

基础用法

实现追加操作时,可以把职责分成三步:add(value) 负责公开操作,ensureCapacity() 负责判断是否扩容,Arrays.copyOf() 负责创建新数组并复制内容。读取方法 get(index) 必须校验 0 <= index < size,不能使用底层容量作为合法下标上界。

初始容量应大于 0。扩容时使用 oldCapacity * 2 可以保持几何增长;本例在倍增前检查 int 溢出。实际可分配上限还取决于 JVM 和可用内存,即使整数计算没溢出,分配也可能失败。

完整可运行示例

将以下代码保存为 DynamicArrayDemo.java。示例使用 Java 17,可直接编译运行。

java
import java.util.Arrays;

public class DynamicArrayDemo {

    static class IntDynamicArray {
        private int[] elements;
        private int size;

        IntDynamicArray(int initialCapacity) {
            if (initialCapacity <= 0) {
                throw new IllegalArgumentException("initialCapacity must be positive");
            }
            elements = new int[initialCapacity];
        }

        void add(int value) {
            ensureCapacity();
            elements[size] = value;
            size++;
        }

        int get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
            }
            return elements[index];
        }

        int size() {
            return size;
        }

        int capacity() {
            return elements.length;
        }

        private void ensureCapacity() {
            if (size < elements.length) {
                return;
            }

            int oldCapacity = elements.length;
            int newCapacity = doubledCapacity(oldCapacity);
            elements = Arrays.copyOf(elements, newCapacity);
            System.out.println("扩容: " + oldCapacity + " -> " + newCapacity);
        }

        private static int doubledCapacity(int oldCapacity) {
            if (oldCapacity > Integer.MAX_VALUE / 2) {
                throw new IllegalStateException("容量过大,无法继续倍增");
            }
            return oldCapacity * 2;
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOf(elements, size));
        }
    }

    public static void main(String[] args) {
        IntDynamicArray numbers = new IntDynamicArray(2);

        for (int value = 10; value <= 80; value += 10) {
            numbers.add(value);
        }

        System.out.println("size = " + numbers.size());
        System.out.println("capacity = " + numbers.capacity());
        System.out.println("elements = " + numbers);
        System.out.println("get(3) = " + numbers.get(3));
    }
}

运行命令如下。

bash
javac -encoding UTF-8 DynamicArrayDemo.java
java DynamicArrayDemo

预期输出

text
扩容: 2 -> 4
扩容: 4 -> 8
size = 8
capacity = 8
elements = [10, 20, 30, 40, 50, 60, 70, 80]
get(3) = 40

输出中的两次扩容分别发生在追加第 3 个和第 5 个元素之前。最终 size 与 capacity 都为 8,因此没有空闲槽位;get(3) 按从 0 开始的下标读取到第 4 个元素 40。

Tips

  • 调试扩容问题时,同时打印扩容前后的 size 与 capacity,不要只观察元素内容。
  • 复制时只需要保证 [0, size) 范围的数据完整;底层数组后部的默认值不属于逻辑内容。
  • 追加后再更新 size,可以让写入位置始终明确为当前尾部下标。
  • 对外暴露容量通常没有业务意义,本课保留 capacity() 仅用于观察扩容过程。

常见错误

1. 把容量当成长度

错误表现是遍历到 elements.length,结果输出尚未写入的默认值。原因是容量表示可分配空间,不代表有效元素数量。正确做法是只遍历 [0, size),并在所有读取操作中使用 size 校验边界。

2. 容量满后直接写入

当 size == elements.length 时继续执行 elements[size] = value 会抛出 ArrayIndexOutOfBoundsException。修复方法是在写入前调用容量检查,并确保扩容完成后再访问新的尾部位置。

3. 每次只扩容一个槽位

这种策略功能上可用,但连续追加时会频繁创建数组并复制元素,在固定初始容量、每次扩容复制全部元素的模型下,总复制成本为 Θ(n2)\Theta(n^2)。使用倍增或其他几何增长策略,可以把复制总量控制在线性级别。

本课练习

  1. 为 IntDynamicArray 增加 set(index, value) 方法。要求只允许修改已有元素,下标非法时抛出异常;运行后验证 size 和 capacity 都不发生变化。
  2. 增加 removeLast() 方法。空数组调用时抛出异常,成功删除后返回原尾部元素,并将对应槽位重置为 0;验收时连续删除直到数组为空。
  3. 记录追加 1 到 32 时每次操作是否触发扩容,统计全部复制次数,并验证复制总数小于最终元素数量的 2 倍。

本课总结

  • size 描述有效元素数量,capacity 描述底层数组可容纳的元素数量,两者不能混用。
  • 倍增扩容使单次追加最坏为 O(n)O(n),但连续追加的摊还时间复杂度为 O(1)O(1)。
  • 动态数组以连续存储换取 O(1)O(1) 随机访问,同时需要承担扩容复制和空闲容量的空间成本。

下一课预告

下一课将学习“单向链表”,通过节点和指针组织非连续数据,并比较它与动态数组在访问、插入和删除方面的差异。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

动态数组

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通