1.数据结构
ArrayList的数据结构是一个数组，如上图所示，图中展示的是一个长度为10的数组，从1开始计数，index表示数组的下标，从0开始计数，elementData表示数组元素。除此之外，源码中还有三个基本概念。
源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//该值用于定义数组第一次扩容时的大小
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
//该值用于定义当前数组的大小
private int size;
}源码解析
- DEFAULT_CAPACITY表示数组第一次扩容时的大小，这个值在面试时经常会提到，在初始化时也会提到它。
- size表示当前数组的大小，类型是int，没有使用volatile修饰，是非线程安全的。
- modCount表示当前数组被修改的版本次数，数组结构有变动，就会 + 1。
2.初始化
ArrayList提供了三种初始化办法，无参数直接初始化、指定大小初始化、指定初始数据初始化，源码如下。
源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//无参数直接初始化，数组大小为空
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_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);
}
}
//指定数据初始化
public ArrayList(Collection<? extends E> c) {
//该值用于保存数组的容器，默认为null
elementData = c.toArray();
//如果给定的集合c有值
if ((size = elementData.length) != 0) {
//如果集合元素类型不是Object类型，则转成Object类型
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
} else {
//给定的集合c无值
this.elementData = EMPTY_ELEMENTDATA;
}
}
}源码解析
- ArrayList无参构造器初始化时，默认大小是空数组，并不是大家常说的10，10是在第一次添加元素的时候扩容的数组值。
- 指定数据初始化时，可以看到注释中含有这么一条注释“c.toArray might (incorrectly) not return Object[] (see 6260652)”。这是源码的一个bug，意思是当给定集合内的元素不是Object类型时，会将其转化成Object类型。一般情况下都不会触发此bug，只有在下列场景下才会触发:ArrayList初始化之后(ArrayList元素非Object类型)，再次调用toArray方法，得到Object数组，然后往Object数组赋值时，才会触发此bug，具体案例代码和运行结果截图如下。
public class App {
public static void main(String[] args) {
List<String> list = Arrays.asList("hello world");
Object[] objArray = list.toArray();
//打印的值为String[]
System.out.println(objArray.getClass().getSimpleName());
//抛出ArrayStoreException异常
objArray[0] = new Object();
}
}
3.新增和扩容
新增就是往数组中添加元素，主要分成两步，一是判断是否需要扩容，如果需要则执行扩容操作，二是直接赋值，具体源码如下。
源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
public boolean add(E e) {
//确保数组大小是否足够，不够执行扩容，size为当前数组的大小
ensureCapacityInternal(size + 1);
//直接赋值，这里是线程不安全的
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果初始化数组大小时，有给定初始值，以给定的大小为准，不走if逻辑
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//确保容积足够
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//记录数组被修改
modCount++;
//如果期望的最小容量大于目前数组的长度，即扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容，并把现有数据拷贝到新的数组里
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//oldCapacity >> 1是把oldCapacity除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后的值小于期望值，扩容后的值就等于期望值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果扩容后的值大于jvm所能分配的数组的最大值，那么就用Integer的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//通过复制进行扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
}源码解析
扩容完成后，通过elementData [size++] = e直接往数组上添加元素。也正是通过这种简单赋值，没有任何锁控制，所以这里的操作是线程不安全的。
总结
- 扩容的规则并不是翻倍，是原来容量大小加上容量大小的一半，直白来说，扩容后的大小是原来容量的1.5倍。
- ArrayList中的数组的最大值是Integer.MAX_VALUE，超过这个值，JVM就不会给数组分配内存空间。
- 新增时，并没有对值进行严格的校验，所以ArrayList是允许null值的。
4.迭代器
要实现迭代器，只需实现java.util.Iterator类即可，迭代器有三个重要的参数和方法，源码如下。
源码
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//迭代过程中，下一个元素的位置，默认从0开始
int cursor;
/**
* 新增场景表示上一次迭代过程中，索引的位置
* 删除场景为-1
*/
int lastRet = -1;
/**
* expectedModCount表示迭代过程中，期望的版本号
* modCount表示数组实际的版本号
*/
int expectedModCount = modCount;
public boolean hasNext() {
//cursor表示下一个元素的位置，size表示实际大小，如果两者相等，说明没有可以迭代的元素，如果不等，说明还有元素需要迭代
return cursor != size;
}
public E next() {
//迭代过程中，判断版本号是否被修改，若被修改，抛出ConcurrentModificationException异常
checkForComodification();
//本次迭代过程中，元素的索引位置
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
//下一次迭代时，元素的位置，为下一次迭代做准备
cursor = i + 1;
//返回元素值
return (E) elementData[lastRet = i];
}
//版本号比较
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
public void remove() {
//如果上一次操作时，数组的位置已经小于0，说明数组已经被删除完
if (lastRet < 0)
throw new IllegalStateException();
//迭代过程中，判断版本号是否被修改，若被修改，抛出ConcurrentModificationException异常
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
//-1表示元素已经被删除，这里也有防止重复删除的作用
lastRet = -1;
//删除元素时modCount的值已经发生变化，在此赋值给expectedModCount，下次迭代时，两者的值便是一致的
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}源码解析
- 从源码中可以看到，next方法完成了两件事情，第一是检验能不能继续迭代，第二是找到迭代的值，并为下一次迭代做准备(cursor + 1)。
- lastRet = -1的目的是防止重复删除。
- 成功删除元素，数组当前modCount就会发生变化，这里会把expectedModCount重新赋值，下次迭代时两者的值便会一致。