动态数组实现：从理论到代码
raw/articles/2026/05/数组实现（动态数组）
侧重：动态数组的完整 Java 代码实现，包括扩缩容策略、索引检查、内存泄漏防护
前置知识
本文是 数组基础 的续篇，建议先阅读数组基础篇了解静态数组的内存模型。
核心内容
1. 动态数组的本质
动态数组 ≠ 新的数据结构
动态数组（如 Java ArrayList、C++ std::vector）底层仍然是静态数组，只是封装了：
- 自动扩缩容逻辑
- 增删查改的 API
本文提供了完整的 Java 实现 MyArrayList<E>，包含以下核心功能：
| 操作 | 方法 | 时间复杂度 |
|---|---|---|
| 尾部添加 | addLast(E e) |
O(1) 均摊 |
| 任意位置插入 | add(int index, E e) |
O(n) |
| 尾部删除 | removeLast() |
O(1) 均摊 |
| 任意位置删除 | remove(int index) |
O(n) |
| 查询 | get(int index) |
O(1) |
| 修改 | set(int index, E element) |
O(1) |
2. 自动扩缩容策略
本文实现了经典的扩缩容策略：
扩容触发条件：size == capacity（元素个数达到容量上限）
扩容策略：newCap = 2 * oldCap（扩大为原来的2倍）
缩容触发条件：size == capacity / 4（元素个数降至容量的1/4）
缩容策略：newCap = oldCap / 2（缩小为原来的1/2）
为什么缩容条件是 1/4 而不是 1/2？
这是为了避免抖动（thrashing）：
- 如果缩容条件是 1/2，那么当元素在临界点附近反复增删时，会频繁触发扩缩容
- 使用 1/4 作为阈值，留出缓冲空间，减少扩缩容频率
时间复杂度分析：
- 单次扩缩容：O(n)（需要复制所有元素）
- 均摊时间复杂度：O(1)（每个元素被复制的次数有限）
3. 索引越界检查的两种模式
实现中区分了两种索引检查：
| 方法 | 条件 | 用途 |
|---|---|---|
checkElementIndex |
index >= 0 && index < size |
检查元素访问/删除的合法性 |
checkPositionIndex |
index >= 0 && index <= size |
检查插入位置的合法性 |
关键区别：插入操作允许 index == size（在末尾插入），而访问/删除操作不允许。
数组: [5, 6, 7, 8]
索引: 0 1 2 3
插入位置: [ | 5 | 6 | 7 | 8 | ]
0 1 2 3 4 ← 允许插入到索引4（末尾）
4. 内存泄漏防护
问题：在 Java 等带垃圾回收的语言中，删除元素后如果不手动置 null，可能造成内存泄漏。
原因：垃圾回收基于可达性分析。如果 data[size-1] 仍然持有对象引用，即使逻辑上已删除，垃圾回收器也不会释放该对象的内存。
解决方案：删除元素时，显式置为 null：
public E removeLast() {
E deletedVal = data[size - 1];
data[size - 1] = null; // 防止内存泄漏
size--;
return deletedVal;
}
相关概念：垃圾回收、内存泄漏（仅1篇来源，暂不创建独立页）
5. 其他实现细节
- 数组复制：示例使用 for 循环，实际可用更高效的
System.arraycopy（Java） - 初始容量：默认
INIT_CAP = 1，可自定义 - 验证方法：可用力扣第 707 题「设计链表」测试实现
相关概念
相关实体
- labuladong：算法学习平台作者
总结
动态数组的核心是封装静态数组 + 自动扩缩容。理解其实现需要掌握：连续内存的特性、扩缩容的触发条件与策略、索引检查的边界处理、以及内存管理的最佳实践。
代码实现要点
完整的 Java 实现包含：
- 底层数组
data：实际存储数据的静态数组 - 元素计数
size：记录当前元素个数 - 扩容方法
resize()：申请新数组 + 复制数据 - 边界检查：防止索引越界
- 内存管理：删除时置
null