Java数据结构之ArrayList-EW帮帮网

一、ArrayList 是什么？

ArrayList 是一个可动态扩容的数组容器，实现了 List 接口，底层基于对象数组实现。

它解决了普通数组长度固定的问题，允许你在运行时动态添加、删除元素。

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
System.out.println(list); // [Java, Python]

二、核心特性

特性	说明
有序	元素按插入顺序存储
可重复	允许重复元素
索引访问	支持通过索引（0-based）快速访问
线程不安全	非同步，多线程需手动同步或使用 `Collections.synchronizedList`
允许 null	可以存储 null 值
自动扩容	当容量不足时自动增长（通常1.5倍）

三、底层结构：基于数组

ArrayList 的本质是一个动态数组。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    transient Object[] elementData; // 存储元素的底层数组（非私有是为了序列化优化）
    private int size;               // 当前元素个数
}

elementData：是一个 Object[] 数组，用来存放元素。
size：记录当前实际存储的元素个数，不等于数组长度（elementData.length）。

所以 ArrayList 支持随机访问（Random Access），时间复杂度 O(1)。

四、构造方法

1. 无参构造（最常用）

ArrayList<String> list = new ArrayList<>();
// 初始容量为 0，第一次 add 时才扩容为 10（JDK 1.8+ 懒加载）

2. 指定初始容量

ArrayList<String> list = new ArrayList<>(20); // 初始容量为20

3. 从集合构造

List<String> copy = new ArrayList<>(otherList);

提示：如果预估元素数量，建议指定初始容量，避免频繁扩容带来的性能开销。

五、添加元素：add(E e)

list.add("Hello");

执行流程：

检查是否需要扩容
- ensureCapacityInternal(size + 1)
将元素放入 elementData[size]
size++

扩容机制（关键！）

// 扩容公式：新容量 = 旧容量 + 旧容量右移1位（即 1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);

例如：

从 10 → 15 → 22 → 33 → 49 → ...

扩容会触发 Arrays.copyOf()，创建新数组并复制数据，时间复杂度 O(n)，所以应尽量避免频繁扩容。

六、随机访问 vs 插入/删除

操作	时间复杂度	说明
`get(index)`	O(1)	直接通过数组下标访问
`set(index, e)`	O(1)	修改指定位置元素
`add(e)`	均摊 O(1)	尾部添加，偶尔扩容 O(n)
`add(index, e)`	O(n)	需要移动后续元素
`remove(index)`	O(n)	需要移动后续元素
`contains(e)`	O(n)	需要遍历查找

所以：ArrayList 适合读多写少、尾部操作多的场景。

七、删除元素

list.remove(0);        // 按索引删除
list.remove("Java");   // 按对象删除（删除第一个匹配项）

删除后会将后面的元素向前移动。
不会自动缩容（除非手动调用 trimToSize()）。

八、遍历方式（推荐与陷阱）

错误方式（并发修改异常）：

for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals("bad")) {
        list.remove(i); // 可能出错或漏删
    }
}

问题：删除后索引错位，且会触发 ConcurrentModificationException（fail-fast 机制）。

九、fail-fast 机制

ArrayList 在迭代过程中如果被其他线程或当前线程修改，会抛出 ConcurrentModificationException。

modCount++; // 修改次数计数器

迭代器在每次 next() 前会检查 modCount == expectedModCount，不一致就抛异常。

解决方案：使用 Iterator.remove() 或 CopyOnWriteArrayList（并发场景）。

十、ArrayList vs 数组 vs LinkedList（下期说LinkedList）

对比项	数组	ArrayList	LinkedList
大小	固定	动态	动态
访问速度	O(1)	O(1)	O(n)
插入/删除	O(n)	O(n)	O(1)（已知位置）
内存开销	小	中等	大（双向指针）
底层结构	连续数组	对象数组	双向链表
是否支持随机访问	是	是	是（但慢）

十一、一些理论知识

ArrayList 扩容机制？

答：初始容量10（懒加载），每次扩容为 1.5倍，使用 Arrays.copyOf 复制。
如何实现线程安全的 ArrayList？

答：Collections.synchronizedList(new ArrayList<>()) 或使用 CopyOnWriteArrayList。
ArrayList 和 Vector 的区别？

Vector 是线程安全的（方法加 synchronized），但性能差；ArrayList 非线程安全。

如何删除 ArrayList 中的重复元素？

List<String> distinct = new ArrayList<>(new LinkedHashSet<>(list));

总结：ArrayList 是：

底层是 Object[] 数组，支持随机访问。
自动扩容（1.5倍），但扩容成本高。
线程不安全，适合单线程场景。
尾部操作高效，中间插入/删除慢。
是 List 接口最常用实现。

Java数据结构之ArrayList