动态数组的基础概念
在Java中，动态数组（Dynamic Array）是一种能够根据数据量自动调整容量的数据结构，与静态数组（长度固定）不同，动态数组可以在运行时动态扩容或缩容，以适应不同规模的数据存储需求，Java标准库中的ArrayList就是动态数组的典型实现，它封装了数组的操作，提供了便捷的增删改查方法，理解动态数组的底层原理和实现方式，有助于开发者更好地使用ArrayList,并在特定场景下自定义动态数组逻辑。
动态数组的核心特性
动态数组的核心特性包括自动扩容、随机访问和动态容量管理，自动扩容是指在元素数量超过当前数组容量时，系统会创建一个更大的新数组，并将原有元素复制到新数组中，通常新容量为旧容量的1.5倍（ArrayList的实现逻辑），随机访问得益于数组连续存储的特性，可以通过索引直接定位元素，时间复杂度为O(1)，动态容量管理则通过维护一个capacity字段记录当前数组的最大容量，并通过size字段记录实际元素数量,确保内存使用效率。
创建动态数组的三种方式
使用ArrayList类（推荐）
Java标准库提供的ArrayList是最常用的动态数组实现，创建ArrayList时，可以通过以下方式初始化：
- 无参构造：默认初始容量为10。
List<Integer> list = new ArrayList<>();
- 指定初始容量：适合已知数据规模较大的场景，减少扩容次数。
List<Integer> list = new ArrayList<>(20); // 初始容量为20
- 通过集合初始化：从其他集合或数组创建动态数组。
List<Integer> existingList = Arrays.asList(1, 2, 3); List<Integer> newList = new ArrayList<>(existingList);
自定义动态数组类
为了深入理解动态数组的原理，可以手动实现一个简单的动态数组类，核心思路包括：
- 定义一个数组
data存储元素，size记录当前元素数量，capacity记录数组容量。 - 实现扩容方法：当
size == capacity时，创建新数组（容量通常为旧容量的2倍），复制元素并更新引用。 - 提供基本的增删改查方法。
示例代码：
public class DynamicArray<T> {
private Object[] data;
private int size;
private static final int DEFAULT_CAPACITY = 10;
public DynamicArray() {
this.data = new Object[DEFAULT_CAPACITY];
this.size = 0;
}
public void add(T element) {
ensureCapacity();
data[size++] = element;
}
private void ensureCapacity() {
if (size == data.length) {
Object[] newData = new Object[data.length * 2];
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
}
@SuppressWarnings("unchecked")
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return (T) data[index];
}
}
使用Arrays.copyOf扩容
在自定义动态数组时，Arrays.copyOf是扩容的便捷方法，该方法会创建一个新数组，并自动复制原数组元素，简化扩容逻辑。
data = Arrays.copyOf(data, data.length * 2); // 扩容为原容量的2倍
动态数组的扩容机制详解
扩容是动态数组的灵魂，以ArrayList为例，其扩容流程如下：
- 触发条件：当调用
add()方法时，若size == capacity，则触发扩容。 - 计算新容量：新容量为
oldCapacity + (oldCapacity >> 1)，即旧容量的1.5倍（右移1位相当于除以2）。 - 创建新数组：通过
Arrays.copyOf()或System.arraycopy()复制元素。 - 更新引用：将新数组赋值给
ArrayList的elementData数组，并更新capacity。
扩容操作的时间复杂度为O(n)，但由于扩容是低频操作（均摊时间复杂度为O(1)）,对整体性能影响较小。
动态数组的常用操作
添加元素
- 尾部添加：
list.add(element)，时间复杂度O(1)（均摊）。 - 指定位置添加：
list.add(index, element)，需要移动后续元素，时间复杂度O(n)。
删除元素
- 尾部删除：
list.remove(list.size() - 1)，时间复杂度O(1)。 - 指定位置删除：
list.remove(index)，需移动元素，时间复杂度O(n)。
查改元素
- 查询：
list.get(index)，时间复杂度O(1)。 - 修改：
list.set(index, element)，时间复杂度O(1)。
容量管理
- 获取当前容量：
list.capacity()（ArrayList可通过list.trimToSize()调整容量为实际元素数量）。 - 预扩容：
list.ensureCapacity(minCapacity)，提前扩容以避免频繁扩容。
动态数组的性能优化建议
- 合理设置初始容量：若已知数据规模，可通过构造方法指定初始容量，减少扩容开销，预计存储1000个元素时，初始化为
new ArrayList<>(1000)。 - 避免频繁扩容：在批量添加元素前，调用
ensureCapacity()一次性扩容。 - 使用
for-each或迭代器遍历：避免使用for循环通过索引遍历时的越界风险，迭代器遍历能安全处理并发修改问题。 - 谨慎使用
remove()：在遍历中删除元素时，建议使用迭代器的remove()方法，否则可能抛出ConcurrentModificationException。
动态数组的适用场景
动态数组适用于数据规模不固定、频繁随机访问的场景，
- 存储用户动态添加的列表数据（如购物车、收藏列表）。
- 需要通过索引快速访问元素的场景（如数组实现的数据结构）。
- 临时存储不确定数量的中间结果（如算法中的临时数组）。
但若数据规模固定且需要频繁插入/删除头部元素，LinkedList（链表）可能更合适，因为其头部插入/删除时间复杂度为O(1)。
动态数组通过自动扩容机制解决了静态数组长度固定的问题，在Java中以ArrayList的形式广泛应用，无论是直接使用ArrayList，还是自定义动态数组类，理解其底层原理（扩容、容量管理、随机访问）都能帮助开发者更高效地处理数据，在实际开发中，应根据场景选择合适的数据结构，并注意性能优化,以充分发挥动态数组的优势。
