动态数组的扩容思想

学习目标

本节学习动态数组的扩容思想。

很多语言中的列表或动态数组看起来可以一直追加元素，但底层并不是无限空间。它们通常会维护一个容量。当元素数量超过当前容量时，就申请更大的空间，并把原有元素搬过去。

理解扩容思想，有助于你理解为什么尾部追加通常很快，但偶尔会出现一次较大的搬移成本。

---

长度和容量不是一回事

动态数组通常有两个概念：

• 长度：当前已经存放了多少个元素。
• 容量：当前底层空间最多能容纳多少个元素。

例如：

长度 length = 3
容量 capacity = 6

元素: 10  20  30  _  _  _

这里已经存放了 3 个元素，但底层空间可以放 6 个元素。后面三个空位可以用于继续追加。

当长度小于容量时，追加元素通常很简单，只需要把新元素放到下一个空位。

---

容量不足时会发生什么

当长度等于容量时，再追加元素就没有空位了。这时动态数组通常会扩容。

扩容一般包含几个步骤：

1. 申请一块更大的连续空间。

2. 把旧空间中的元素依次复制到新空间。

3. 释放或丢弃旧空间。

4. 把新元素放入新空间的下一个位置。

5. 更新长度和容量信息。

这个过程说明：追加元素平时可能很快，但遇到扩容时，需要搬移已有元素，因此那一次操作会比较贵。

---

一个简化的追加过程

下面的示例用伪简化代码表达动态数组追加元素时的核心逻辑。真实语言库的实现会更复杂，但思想相似。

C++

void add(int value) {
    if (size == capacity) {
        resize(capacity * 2);
    }

    data[size] = value;
    size++;
}

Java

void add(int value) {
    if (size == capacity) {
        resize(capacity * 2);
    }

    data[size] = value;
    size++;
}

Python

def add(value):
    global size, capacity, data

    if size == capacity:
        resize(capacity * 2)

    data[size] = value
    size += 1

C#

void Add(int value)
{
    if (size == capacity)
    {
        Resize(capacity * 2);
    }

    data[size] = value;
    size++;
}

这段代码表达了两个动作：如果容量不够，先扩容；然后把新元素放到末尾。

扩容倍数不一定总是 2，不同语言或库可能采用不同策略。但“容量不足时申请更大空间并搬移元素”是核心思想。

---

为什么尾部追加通常仍然很快

虽然扩容时需要复制旧元素，但并不是每次追加都扩容。

如果容量从 4 扩到 8，再从 8 扩到 16，再从 16 扩到 32，那么大量普通追加操作只是把元素放到下一个空位。只有少数几次触发扩容。

从整体平均看，动态数组尾部追加通常可以认为具有很好的效率，常见说法是“摊还时间复杂度”为 $O(1)$。

摊还分析的意思是：把偶尔发生的高成本扩容分摊到多次追加操作上，平均每次追加仍然接近常数级。

---

扩容带来的空间取舍

动态数组为了减少频繁扩容，通常会预留一部分空余容量。这意味着它可能会暂时占用比实际元素数量更多的空间。

这是一种典型取舍：

• 多预留一些空间，可以减少扩容次数，提高追加效率。
• 预留空间太多，会造成内存浪费。
• 预留空间太少，会导致频繁扩容，增加复制成本。

这类“用空间换时间”的思想，在后续学习哈希表、堆和其他结构时也会反复出现。

---

本节小结

动态数组之所以能不断追加元素，是因为它在容量不足时会申请更大的连续空间，并把旧元素复制过去。

普通尾部追加通常很快，但触发扩容的那一次会比较贵。从长期平均看，尾部追加通常可以认为是摊还 $O(1)$。理解长度、容量和扩容，有助于你更准确地理解顺序表的实际行为。