ArrayList的核心概念：它是什么，有什么特点。- 内部数据结构：
ArrayList是如何存储数据的。 - 核心源码分析：通过阅读源码，理解关键方法（如
add,get,remove）是如何工作的。 - 性能分析：不同操作的时间复杂度。
- 与
LinkedList的简单对比：帮助理解何时使用ArrayList。 - 代码示例：一个完整的、可运行的示例。
ArrayList 的核心概念
ArrayList 是 Java 集合框架中 List 接口的一个具体实现，它的主要特点是：
（图片来源网络，侵删）
- 动态数组：它本质上是一个可以自动扩容的数组，与 Java 中固定长度的原生数组（
[]）不同，ArrayList的大小可以在运行时动态改变。 - 有序：它维护了元素的插入顺序，你可以通过索引（0-based）来访问元素。
- 允许重复：可以存储多个
null值和重复的对象。 - 非线程安全：如果在多线程环境下并发修改
ArrayList，可能会导致数据不一致或ConcurrentModificationException，如果需要线程安全的版本，可以使用Collections.synchronizedList(new ArrayList<>())或CopyOnWriteArrayList。
内部数据结构
ArrayList 的核心在于其内部维护的两个关键属性：
// 源码中的关键字段 (简化版)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private transient Object[] elementData; // 存储元素的数组
private int size; // 当前元素的数量 (不是数组的长度)
elementData：这是一个Object类型的数组，是ArrayList的真正数据容器。transient关键字表示它不会被序列化。size：这是一个整数，记录了当前ArrayList中实际存储了多少个元素，它永远小于或等于elementData.length。DEFAULTCAPACITY_EMPTY_ELEMENTDATA：这是一个空的数组，用于无参构造函数初始化ArrayList时使用。
初始化：
当你使用 new ArrayList<>() 无参构造函数创建 ArrayList 时，elementData 会被初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA（一个空数组），size 为 0。
核心源码分析
理解了内部结构后,我们来看几个核心方法的实现。
a. add(E e) - 添加元素
这是 ArrayList 最核心也最复杂的操作，因为它涉及到扩容。
（图片来源网络，侵删）
public boolean add(E e) {
// 1. 确保内部数组有足够的空间，size + 1 是因为新加一个元素
// size + 1 后超过了数组的长度，就需要扩容
ensureCapacityInternal(size + 1);
// 2. 将新元素添加到数组的 size 位置（即当前最后一个元素的下一个位置）
elementData[size++] = e;
return true;
}
// ensureCapacityInternal 的实现
private void ensureCapacityInternal(int minCapacity) {
// 如果是刚创建的空 ArrayList，minCapacity 会是 1
// 这时会使用 DEFAULT_CAPACITY (10) 作为初始容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 检查是否需要扩容
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// minCapacity 大于当前数组的长度，就需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// grow() 方法是扩容的核心
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 新容量 = 旧容量的 1.5 倍 (位运算更高效)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 处理溢出情况，以及新容量仍然小于所需最小容量的问题
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量超过了 MAX_ARRAY_SIZE，则使用一个巨大的值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 使用 Arrays.copyOf 创建一个新数组，并将旧数组的内容复制过去
elementData = Arrays.copyOf(elementData, newCapacity);
}
add 操作流程总结：
- 检查容量：在添加元素前，先判断
size + 1是否会超出当前数组的长度。 - 扩容：如果超出，则进行扩容，扩容策略是容量变为原来的 1.5 倍（
oldCapacity + oldCapacity / 2），这是一个经过优化的策略，在空间和时间上取得了较好的平衡。 - 复制与替换：扩容不是在原数组上修改，而是创建一个更大的新数组，然后将旧数组中的所有元素（
elementData）复制到新数组中，最后让elementData引用指向这个新数组，这个过程是Arrays.copyOf()完成的。 - 添加元素：在新数组的
size位置（即末尾）放入新元素，并size++。
时间复杂度：
- 平均情况：
O(1)，大部分情况下，数组有足够空间，直接赋值即可。 - 最坏情况：
O(n)，当数组需要扩容时，需要复制所有n个元素到新数组，此时时间复杂度为O(n)，但由于扩容是指数级增长的（1.5倍），均摊下来，add操作的时间复杂度仍然是O(1)。
b. get(int index) - 获取元素
这个操作非常简单,因为数组是随机存取结构。
public E get(int index) {
// 1. 范围检查，防止索引越界
Objects.checkIndex(index, size);
// 2. 直接通过索引访问数组元素
return (E) elementData[index];
}
时间复杂度：O(1)，无论 index 是多少，访问速度都是恒定的。
（图片来源网络，侵删）
c. remove(int index) - 删除元素
删除操作比添加更复杂,因为它需要移动元素。
public E remove(int index) {
// 1. 范围检查
Objects.checkIndex(index, size);
// 2. 获取要删除的元素，用于返回
E oldValue = (E) elementData[index];
// 3. 计算需要移动的元素数量
int numMoved = size - index - 1;
// 4. 如果不是删除最后一个元素，就需要进行元素移动
if (numMoved > 0)
// 将 index+1 位置开始的 numMoved 个元素，向前移动到 index 位置
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
// 5. 清理最后一个元素，并让 size 减 1
elementData[--size] = null; // help GC
return oldValue;
}
remove 操作流程总结：
- 范围检查：确保索引有效。
- 获取旧值：记录要被删除的元素，以便方法返回。
- 移动元素：从
index+1开始，将后面的所有元素向前移动一位，覆盖掉被删除的元素，这是通过System.arraycopy()高效完成的。 - 清理与缩容：将被移动后空出来的最后一个元素（
elementData[size-1]）置为null（帮助垃圾回收），然后将size减一。
时间复杂度：
- 平均情况：
O(n)，因为最坏情况下（删除第一个元素），需要移动n-1个元素。 - 最好情况：
O(1)，当删除最后一个元素时，不需要移动任何元素，只需将size减一并将末尾置为null。
性能分析总结
| 操作 | 时间复杂度 | 备注 |
|---|---|---|
add(E e) (尾部添加) |
均摊 O(1) | 大部分情况是 O(1)，扩容时为 O(n)，但均摊后是 O(1)。 |
get(int index) |
O(1) | 数组随机访问的巨大优势。 |
remove(int index) |
O(n) | 需要移动被删除元素之后的所有元素。 |
set(int index, E e) |
O(1) | 直接通过索引赋值，不涉及移动。 |
contains(E e) |
O(n) | 需要遍历整个数组进行线性查找。 |
ArrayList vs LinkedList
| 特性 | ArrayList |
LinkedList |
|---|---|---|
| 数据结构 | 动态数组 | 双向链表 |
随机访问 (get) |
快 (O(1)) | 慢 (O(n))，需要从头或尾遍历 |
尾部添加 (add) |
快 (均摊 O(1)) | 快 (O(1)) |
中间插入 (add) |
慢 (O(n))，需要移动元素 | 快 (O(1))，只需修改指针 |
中间删除 (remove) |
慢 (O(n))，需要移动元素 | 快 (O(1))，只需修改指针 |
| 内存开销 | 较小，只有数组本身 | 较大，每个节点需要额外存储 prev 和 next 指针 |
| 适用场景 | 频繁查询，少量增删，例如缓存、列表数据 | 频繁增删，少量查询，例如队列、栈 |
代码示例
下面是一个完整的示例,演示了 ArrayList 的基本用法和性能特点。
import java.util.ArrayList;
import java.util.Arrays;
public class ArrayListImplementationDemo {
public static void main(String[] args) {
// 1. 创建 ArrayList
ArrayList<String> fruits = new ArrayList<>();
// 2. 添加元素 (add)
System.out.println("--- 添加元素 ---");
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
System.out.println("添加后: " + fruits); // [Apple, Banana, Orange]
System.out.println("当前容量: " + getCapacity(fruits) + ", 大小: " + fruits.size());
// 3. 在中间插入元素
fruits.add(1, "Mango");
System.out.println("在索引1插入Mango后: " + fruits); // [Apple, Mango, Banana, Orange]
System.out.println("当前容量: " + getCapacity(fruits) + ", 大小: " + fruits.size());
// 4. 获取元素 (get)
System.out.println("\n--- 获取元素 ---");
String fruit = fruits.get(2);
System.out.println("索引2处的元素是: " + fruit); // Banana
// 5. 修改元素 (set)
System.out.println("\n--- 修改元素 ---");
fruits.set(0, "Pineapple");
System.out.println("将索引0修改为Pineapple后: " + fruits); // [Pineapple, Mango, Banana, Orange]
// 6. 删除元素 (remove)
System.out.println("\n--- 删除元素 ---");
String removedFruit = fruits.remove(3);
System.out.println("删除索引3的元素(" + removedFruit + ")后: " + fruits); // [Pineapple, Mango, Banana]
System.out.println("当前容量: " + getCapacity(fruits) + ", 大小: " + fruits.size());
// 7. 演示扩容
System.out.println("\n--- 演示自动扩容 ---");
System.out.println("当前容量: " + getCapacity(fruits));
// ArrayList的初始容量是10，我们添加到第11个元素时会触发扩容
for (int i = fruits.size(); i < 11; i++) {
fruits.add("Fruit-" + i);
}
System.out.println("添加到11个元素后: " + fruits);
System.out.println("扩容后容量: " + getCapacity(fruits)); // 应该是15 (10 * 1.5)
}
/**
* 一个辅助方法，用于反射获取 ArrayList 的容量（elementData.length）
* 注意：这只是一个演示用的工具方法，在生产代码中应避免使用反射。
*/
private static int getCapacity(ArrayList<?> list) {
try {
// 获取 elementData 字段
java.lang.reflect.Field field = ArrayList.class.getDeclaredField("elementData");
field.setAccessible(true);
// 获取 elementData 数组
Object[] elementData = (Object[]) field.get(list);
return elementData.length;
} catch (NoSuchFieldException | IllegalAccessException e) {
e.printStackTrace();
return -1;
}
}
}
运行结果分析：
- 你会看到
add操作后，size增加。 - 当
ArrayList从空开始添加第一个元素时，它的容量会自动扩容到 10。 - 当你添加第11个元素时,你会看到容量从 10 变为 15 (10 * 1.5)，这正是我们源码分析中看到的扩容策略。
希望这个详细的解释能帮助你彻底理解 ArrayList 在 Java 中的实现原理！
