一、概述
ArrayList 是 java 集合框架中比较常用的数据结构,继承自 AbstractList，实现了 List 接口。底层采用数组来实现。ArrayList 实现了java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
1.1、底层数据结构
底层采用数组进行数据存储，相当于动态数组。
1.2、特点
动态大小：ArrayList的大小是动态的，可以在运行时添加或删除元素。这意味着您不需要预先确定列表的大小。
数组实现：ArrayList基于数组实现，这使得它具有高效的内部数据结构，可以快速随机访问列表中的元素。但是，如果你需要从列表的中间位置插入或删除元素，这可能会涉及到数组元素的移动，所以可能相对较慢。
可修改：ArrayList是可修改的。这意味着您可以在列表中更改、添加或删除元素。
线程不安全的：ArrayList不是线程安全的。这意味着如果在多个线程同时修改ArrayList时，可能会导致数据的不一致性。如果需要线程安全，可以使用同步块或者考虑使用线程安全的集合类，如CopyOnWriteArrayList。
易于使用：ArrayList提供了许多有用的方法，如add(), remove(), get()等，可以方便地操作列表。同时，它也支持迭代器，可以进行遍历操作。
性能：由于ArrayList内部使用数组进行实现，所以在知道索引的情况下进行读取或写入操作的速度非常快，时间复杂度为O(1)。但是，如果需要从中间位置进行插入或删除操作，那么需要移动数组中的元素，所以时间复杂度为O(n)。
1.3、ArrayList类图
由源码可得知：
ArrayList继承了抽象类AbstractList，并实现了List、RandomAccess、Cloneable、Serializable等接口。
抽象类AbstractList继承了抽象类AbstractCollection，并实现了List接口；抽象类AbstractCollection实现了Collection接口，Collection接口继承了Iterable接口。
实现RandomAccess接口：表明ArrayList支持快速（通常是常量时间）的随机访问。
实现了Cloneable接口，表明它支持克隆。可以调用clone（）进行浅拷贝。
实现了Serializable接口，表明它支持序列化。
二、源码解析
2.1、属性解析
/**
* 默认的容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 定义了一个空的数组，用于在用户初始化代码的时候传入容量为0时使用
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 定义了一个空数组，用于在默认构造器中，赋值给顶级数组 elementData
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 底层数组，真正存储元素的地方
*/
transient Object[] elementData;
/**
* 表示集合中ArrayList含有元素的个数
*/
private int size;
/**
* 标记数组的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 记录对 List 操作的次数
*/
protected transient int modCount = 0;
2.2、构造方法解析
ArrayList默认提供了三种构造器，分别是：
- 无参构造器
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
解析：
当我们使用无参构造器时，将DEFAULTCAPACITY_EMPTY_ELEMENTDATA变量赋值给elementData，即把elementData初始化为一个空数组。
注意：在这里没有对数组容量进行分配大小；具体给数组分配容量大小是第一次增加元素时才分配的。
- 指定初始容量的构造器
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
解析：
当传入的容量大小大于0，elementData 赋值为一个容量指定容量为initialCapacity的数组。
当传入的容量等于0，elementData 赋值为 EMPTY_ELEMENTDATA。
其他情况下，抛出异常！
注意：
对比无参构造，与此时的initialCapacity传入0，两种情况有什么不同呢，又有什么作用呢？
// 无参构造
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
// initialCapacity传入0时的赋值
this.elementData = EMPTY_ELEMENTDATA;
这两个变量的作用：用于区分是通过哪个构造函数来进行初始化的。
- 提供一个
Collection集合的构造器
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
解析：
将传入的集合转化为数组，赋值给elementData，并计算集合的大小size；
若 size != 0，接着判断保证此刻数组elementData数组的类型和Object[]类型相同，若不同，则拷贝一个Object[]类型的数组赋值给elementData。
若size == 0，将 elementData 赋值为 EMPTY_ELEMENTDATA。
注：若传入的c为null，将会报空指针异常。
2.3、常用方法解析
add方法
// add方法
public boolean add(E e) {
// 判断数组用不用扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
// ensureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// calculateCapacity方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// ensureExplicitCapacity方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// grow方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
解析：
当我们调用add方法，首先调用ensureCapacityInternal()方法，传入当前元素的个数+1；紧接着调用calculateCapacity方法，进行容量的计算。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
在calculateCapacity 方法中，有个判断逻辑：elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个也正是我们使用默认构造器创建的。若为默认的构造器创建的话，把minCapacity（也就是我们的size+1）和DEFAULT_CAPACITY（默认容量是10）比较，取较大者返回，否则的话，就返回minCapacity。
该方法的作用：通过无参构造创建的 ArrayList 在第一次 add 时进行初始容量的设置。因为只要不相等，返回的还是minCapacity，与传入的相同；
因此通过无参构造创建的ArrayList，第一次add的时候，创始容量的大小为DEFAULT_CAPACITY（默认容量是10）。
接下来调用ensureExplicitCapacity 方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
进行判断：如果minCapacity大于底层数组的长度，则需要调用grow(minCapacity)方法进行扩容，否则的话，回到add()方法中，ensureCapacityInternal(size + 1)什么也不做。
过程解析
- 当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0 成立，所以会进入 grow(minCapacity) 方法。
- 当add第2个元素时，minCapacity 为2，此时elementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。
- 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大；进入grow方法进行扩容。
接下来进入grow方法：
// grow方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
解析：
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
oldCapacity为旧容量， newCapacity是扩容后的容量，即oldCapacity + (oldCapacity >> 1)，大概是oldCapacity的1.5倍。
oldCapacity为偶数就是1.5倍；否则是1.5倍左右，因为如果是奇数的话会丢掉小数。
接下来进行判断：
第一个判断：如果新容量小于我们设置的minCapacity的话，就把minCapacity赋值给newCapacity。
第二个判断：判断newCapacity是否大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）,（MAX_ARRAY_SIZE代表了所能设置的数组的最大容量，如果超过这个值，可能导致内存溢出的错误（OutOfMemoryError），当然，如果超过的话，会将数组的容量设置为INTEGER.MAX_VALUE，否则新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8）。
过程解析
- 当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity 赋值为minCapacity(minCapacity = 10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 hugeCapacity 方法。数组容量为10，add方法中 return true,size增为1。
- 当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true,size增为11。
- 以此类推... ...
总结：
如果 ArrayList 是通过无参构造创建的，那么初始化时并不会初始化数组的大小，只是把数组标记为通过无参构造初始化的；然后在第一次加入数据时，初始化数组大小为10。
如果超过了最大容量则需要扩容，扩容后的数组大小大概为原数组的1.5倍；扩容需要判断是否超过允许的最大的长度，并做相关的处理。
addAll方法
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
解析：
addAll方法与add方法基本相似
首先将传入的Collection转化为数组，然后将其容量numNew 加上ArrayList的大小，进行判断容量够不够，最后进行数组的拷贝，把传入的所有元素添加到底层数组elementData中，然后把ArrayList中元素个数的size重新计算。
最后如果传入的参数的元素不为空，则返回true，表示把元素添加了进去，如果为空的话，说明没有添加元素，则返回false。
获取ArrayList的大小
// 获取元素大小
public int size() {
return size;
}
直接返回size即可，因为属性size代表了ArrayList的大小。
获取元素的位置
获取元素第一次出现的索引位置使用indexOf方法；获取元素最后一次出现的索引位置使用lastIndexOf方法。
indexOf方法
// 获取元素第一次出现的索引位置
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
解析：
当参数是null的时候，循环遍历elementData 判断其位置，直接返回；
当参数不为null的时候，循环遍历elementData 判断其位置，直接返回；
如果没有找到则返回-1。
lastIndexOf方法
// 获取元素最后一次出现的索引位置
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
解析：
与indexOf方法类似，只不过遍历elementData是从后向前遍历的。
判断是否包含某个元素contains
// 判断是否包含某个元素
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
解析：
直接调用上面的indexof()方法即可，若该方法返回大于0，则存在该元素；否则不存在。
给某个位置设置元素
// 给某个位置设置元素
public E set(int index, E element) {
// 检查索引位置是否越界
rangeCheck(index);
// 查看底层elementData数组的某个元素
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
解析：
首先检查，传入的索引位置是否越界，越界抛出IndexOutOfBoundsException异常，然后获取elementData数组该位置的元素，接着将新元素放入该位置，最后返回该位置的旧值。
在指定位置的地方添加新的元素
public void add(int index, E element) {
// 范围检查
rangeCheckForAdd(index);
// 增加容量
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
解析：
首先检查一下参数索引位置是否符合，其次通过ensureCapacityInternal(size + 1)判断是否需要增加容量，如果需要则扩容，否则不需要则什么也不用做。
然后进行数组数组elementData元素的移动，最后把要添加的元素添加到指定的位置，然后进行元素个数size的累加。
移除指定位置的元素
// 移除指定位置的元素
public E remove(int index) {
// 范围检查
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
解析：
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
首先，rangeCheck方法对传入的索引参数范围检查，接着获取旧值赋值给变量oldValue;
在移动元素的时候，仍然选择进行数组的拷贝。首先计算需要移动的元素个数（size - index - 1）；如果移动的元素的个数大于0，下面进行数组的拷贝（其实就是起到了移动元素的功能）；否则的话直接在elementData[–size]处设置为空就可以了。记住最后需要返回移除了的值。
移除指定值的元素
// 移除指定值的元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// fastRemove方法
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
解析：
该方法对传入的参数进行是否为null的判断，两种情况下，对elementData数组进行循环遍历判断，是否与传入的值相等，相等的话调用fastRemove方法 进行元素的移除操作。
