动态数组（Dynamic Array）
一种能够自动调整容量的数组数据结构，底层仍是静态数组，但通过封装扩缩容逻辑，提供了更灵活的使用接口。
定义
动态数组是在静态数组基础上封装的数据结构，能够在运行时自动调整存储容量。当元素数量超过当前容量时自动扩容，当元素数量过少时可能缩容以节约内存。
常见实现：
- Java:
ArrayList - C++:
std::vector - Python:
list（本质是可变数组） - JavaScript:
Array（引擎自动管理）
核心原理
1. 底层结构
动态数组 = 静态数组 + 元信息 + 扩缩容逻辑
MyArrayList<E>
├── data: E[] // 底层静态数组
├── size: int // 当前元素个数
└── 扩缩容方法 // resize()
2. 扩缩容策略
本文实现的扩缩容策略（参见 扩缩容 概念页）：
| 操作 | 触发条件 | 策略 |
|---|---|---|
| 扩容 | size == capacity |
新容量 = 旧容量 × 2 |
| 缩容 | size == capacity / 4 |
新容量 = 旧容量 / 2 |
为什么缩容阈值是 1/4？
避免抖动（thrashing）：如果缩容阈值是 1/2，当元素个数在临界点反复增减时，会频繁触发扩缩容，严重影响性能。使用 1/4 留出缓冲空间。
3. 时间复杂度
| 操作 | 最坏情况 | 均摊分析 |
|---|---|---|
addLast() |
O(n)（触发扩容） | O(1) |
add(index, e) |
O(n) | O(n) |
removeLast() |
O(n)（触发缩容） | O(1) |
remove(index) |
O(n) | O(n) |
get(index) |
O(1) | O(1) |
set(index, e) |
O(1) | O(1) |
均摊时间复杂度：虽然单次扩缩容需要 O(n)，但每个元素被复制的次数有限，长期平均下来每次操作的成本是 O(1)。
4. 与静态数组的关系
动态数组并没有改变静态数组的本质：
- 底层仍然是连续内存空间
- 随机访问依然是 O(1)
- 增删操作仍然需要数据搬移
区别：动态数组自动处理了容量管理，用户无需手动申请新数组和复制数据。
实现要点
索引越界检查
需要区分两种检查模式：
| 方法 | 条件 | 用途 |
|---|---|---|
checkElementIndex |
0 ≤ index < size |
访问、删除元素 |
checkPositionIndex |
0 ≤ index ≤ size |
插入元素（允许在末尾插入） |
内存泄漏防护
在 Java 等带垃圾回收的语言中，删除元素后需要显式置 null：
E deleted = data[size - 1];
data[size - 1] = null; // 断开引用，让 GC 可以回收
size--;
相关概念
总结
动态数组通过封装静态数组 + 自动扩缩容，在保持 O(1) 随机访问的同时，提供了更灵活的使用方式。理解其实现有助于掌握数据结构设计中的空间换时间、均摊分析等核心思想。