精尽 JDK 源码解析 —— 集合（一）数组 ArrayList - 《精尽 JDK》

ArrayList ，基于 [] 数组实现的，支持自动扩容的动态数组。相比数组来说，因为其支持自动扩容的特性，成为我们日常开发中，最常用的集合类，没有之一。

在前些年，实习或初级工程师的面试，可能最爱问的就是 ArrayList 和 LinkedList 的区别与使用场景。不过貌似，现在问的已经不多了，因为现在信息非常发达，这种常规面试题已经无法区分能力了。当然即使如此，也不妨碍我们拿它开刀，毕竟是咱的 “老朋友”。

ArrayList 实现的接口、继承的抽象类，如下图所示：
类图

实现了 4 个接口，分别是：

java.util.List 接口，提供数组的添加、删除、修改、迭代遍历等操作。
java.util.RandomAccess 接口，表示 ArrayList 支持快速的随机访问。> 关于 RandomAccess 标记接口，我们这里先不展开，胖友可以自行阅读《RandomAccess 这个空架子有何用？》文章。

java.io.Serializable 接口，表示 ArrayList 支持序列化的功能。> 关于 Serializable 标记接口，我们这里先不展开，胖友可以自行阅读《Java 序列化与反序列化》文章。

java.lang.Cloneable 接口，表示 ArrayList 支持克隆。> 关于 Cloneable 标记接口，我们这里先不展开，胖友可以自行阅读《在 Java 中为什么实现了 Cloneable 接口，就能调用 Object 的 clone 方法？》讨论，特别是 R 大的回答。

继承了 java.util.AbstractList 抽象类，而 AbstractList 提供了 List 接口的骨架实现，大幅度的减少了实现迭代遍历相关操作的代码。可能这样表述有点抽象，胖友点到 java.util.AbstractList 抽象类中看看，例如说 #iterator()、#indexOf(Object o) 等方法。

😈 不过实际上，在下面中我们会看到，ArrayList 大量重写了 AbstractList 提供的方法实现。所以，AbstractList 对于 ArrayList 意义不大，更多的是 AbstractList 其它子类享受了这个福利。

ArrayList 的属性很少，仅仅 2 个。如下图所示：

ArrayList

elementData 属性：元素数组。其中，图中红色空格代表我们已经添加元素，白色空格代表我们并未使用。
size 属性：数组大小。注意，size 代表的是 ArrayList 已使用 elementData 的元素的数量，对于开发者看到的 #size() 也是该大小。并且，当我们添加新的元素时，恰好其就是元素添加到 elementData 的位置（下标）。当然，我们知道 ArrayList 真正的大小是 elementData 的大小。

对应代码如下：

transient Object[] elementData;

private int size;

ArrayList 一共有三个构造方法，我们分别来看看。

① #ArrayList(int initialCapacity)

#ArrayList(int initialCapacity) 构造方法，根据传入的初始化容量，创建 ArrayList 数组。如果我们在使用时，如果预先指到数组大小，一定要使用该构造方法，可以避免数组扩容提升性能，同时也是合理使用内存。代码如下：

private static final Object[] 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);
}
}

比较特殊的是，如果初始化容量为 0 时，使用 EMPTY_ELEMENTDATA 空数组。在添加元素的时候，会进行扩容创建需要的数组。

② #ArrayList(Collection<? extends E> c)

#ArrayList(Collection<? extends E> c) 构造方法，使用传入的 c 集合，作为 ArrayList 的 elementData 。代码如下：

public ArrayList(Collection<? extends E> c) {

elementData = c.toArray();

if ((size = elementData.length) != 0) {

if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);

} else {

this.elementData = EMPTY_ELEMENTDATA;
}
}

比较让人费解的是，在 <X> 处的代码。它是用于解决 JDK-6260652 的 Bug 。它在 JDK9 中被解决，😈 也就是说，JDK8 还会存在该问题。

我们来看一段能够触发 JDK-6260652 的测试代码，然后分别在 JDK8 和 JDK13 下执行。代码如下：

public static void test02() {
List list = Arrays.asList(1, 2, 3);
Object[] array = list.toArray();
System.out.println(“array className ：” + array.getClass().getSimpleName());

array[0] = new Object();
}

③ #ArrayList()

无参数构造方法 #ArrayList() 构造方法，也是我们使用最多的构造方法。代码如下：

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

在我们学习 ArrayList 的时候，一直被灌输了一个概念，在未设置初始化容量时，ArrayList 默认大小为 10 。但是此处，我们可以看到初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个空数组。这是为什么呢？ArrayList 考虑到节省内存，一些使用场景下仅仅是创建了 ArrayList 对象，实际并未使用。所以，ArrayList 优化成初始化是个空数组，在首次添加元素时，才真正初始化为容量为 10 的数组。
那么为什么单独声明了 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组，而不直接使用 EMPTY_ELEMENTDATA 呢？在下文中，我们会看到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 首次扩容为 10 ，而 EMPTY_ELEMENTDATA 按照 1.5 倍扩容从 0 开始而不是 10 。😈 两者的起点不同，嘿嘿。

#add(E e) 方法，顺序添加单个元素到数组。代码如下：

@Override
public boolean add(E e) {

modCount++;

add(e, elementData, size);

return true;
}

private void add(E e, Object[] elementData, int s) {

if (s == elementData.length)
elementData = grow();

elementData[s] = e;

size = s + 1;
}

<1> 处，增加数组修改次数 modCount 。在父类 AbstractList 上，定义了 modCount 属性，用于记录数组修改次数。
<2> 处，如果元素添加的位置就超过末尾（数组下标是从 0 开始，而数组大小比最大下标大 1），说明数组容量不够，需要进行扩容，那么就需要调用 #grow() 方法，进行扩容。稍后我们在「6. 数组扩容」小节来讲。
<3> 处，设置到末尾。
<4> 处，数量大小加一。

总体流程上来说，抛开扩容功能，和我们日常往 [] 数组里添加元素是一样的。

看懂这个方法后，胖友自己来看看 #add(int index, E element) 方法，插入单个元素到指定位置。代码如下：

public void add(int index, E element) {

rangeCheckForAdd(index);

modCount++;

final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();

System.arraycopy(elementData, index,
elementData, index + 1,
s - index);

elementData[index] = element;

size = s + 1;
}

private void rangeCheckForAdd(int index) {
if (index> size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

#grow() 方法，扩容数组，并返回它。整个的扩容过程，首先创建一个新的更大的数组，一般是 1.5 倍大小（为什么说是一般呢，稍后我们会看到，会有一些小细节），然后将原数组复制到新数组中，最后返回新数组。代码如下：

private Object[] grow() {

return grow(size + 1);
}

private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;

if (oldCapacity> 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity,
oldCapacity >> 1 );
return elementData = Arrays.copyOf(elementData, newCapacity);

} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}

<1> 处，调用 #grow(int minCapacity) 方法，要求扩容后至少比原有大 1 。因为是最小扩容的要求，实际是允许比它大。
<2> 处，如果原容量大于 0 时，又或者数组不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，则计算新的数组大小，并创建扩容。
- ArraysSupport#newLength(int oldLength, int minGrowth, int prefGrowth) 方法，计算新的数组大小。简单来说，结果就是 Math.max(minGrowth, prefGrowth) + oldLength ，按照 minGrowth 和 prefGrowth 取大的。
- 一般情况下，从 oldCapacity >> 1 可以看处，是 1.5 倍扩容。但是会有两个特殊情况：1）初始化数组要求大小为 0 的时候，0 >> 1 时（>> 1 为右移操作，相当于除以 2）还是 0 ，此时使用 minCapacity 传入的 1 。2）在下文中，我们会看到添加多个元素，此时传入的 minCapacity 不再仅仅加 1 ，而是扩容到 elementData 数组恰好可以添加下多个元素，而该数量可能会超过当前 ArrayList 0.5 倍的容量。
<3> 处，如果是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组，直接创建新的数组即可。思考下，如果无参构造方法使用 EMPTY_ELEMENTDATA 的话，无法实现该效果了。

既然有数组扩容方法，那么是否有缩容方法呢？在 #trimToSize() 方法中，会创建大小恰好够用的新数组，并将原数组复制到其中。代码如下：

public void trimToSize() {

modCount++;

if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

同时，提供 #ensureCapacity(int minCapacity) 方法，保证 elementData 数组容量至少有 minCapacity 。代码如下：

public void ensureCapacity(int minCapacity) {
if (minCapacity> elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {

modCount++;

grow(minCapacity);
}
}

比较简单，我们可以将这个方法理解成主动扩容。

#addAll(Collection<? extends E> c) 方法，批量添加多个元素。在我们明确知道会添加多个元素时，推荐使用该该方法而不是添加单个元素，避免可能多次扩容。代码如下：

public boolean addAll(Collection<? extends E> c) {

Object[] a = c.toArray();

modCount++;

int numNew = a.length;
if (numNew == 0)
return false;

Object[] elementData;
final int s;
if (numNew> (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);

System.arraycopy(a, 0, elementData, s, numNew);

size = s + numNew;
return true;
}

<1> 处，如果 elementData 剩余的空间不足，则进行扩容。要求扩容的大小，至于能够装下 a 数组。当然，在「6. 数组扩容」的小节，我们已经看到，如果要求扩容的空间太小，则扩容 1.5 倍。
<2> 处，将 a 复制到 elementData 从 s 开始位置。

总的看下来，就是 #add(E e) 方法的批量版本，优势就正如我们在本节开头说的，避免可能多次扩容。

看懂这个方法后，胖友自己来看看 #addAll(int index, Collection<? extends E> c) 方法，从指定位置开始插入多个元素。代码如下：

public boolean addAll(int index, Collection<? extends E> c) {

rangeCheckForAdd(index);

Object[] a = c.toArray();

modCount++;

int numNew = a.length;
if (numNew == 0)
return false;

Object[] elementData;
final int s;
if (numNew> (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);

int numMoved = s - index;
if (numMoved> 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);

System.arraycopy(a, 0, elementData, index, numNew);

size = s + numNew;
return true;
}

重点看【差异点】部分。

#remove(int index) 方法，移除指定位置的元素，并返回该位置的原元素。代码如下：

public E remove(int index) {

Objects.checkIndex(index, size);
final Object[] es = elementData;

@SuppressWarnings(“unchecked”) E oldValue = (E) es[index];

fastRemove(es, index);

return oldValue;
}

重点是 <X> 处，调用 #fastRemove(Object[] es, int i) 方法，快速移除。代码如下
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
- <Y> 处，看起来比较复杂，胖友按照 “如果 i 不是移除最末尾的元素，则将 i + 1 位置的数组往前挪” 来理解，就很好懂了。

#remove(Object o) 方法，移除首个为 o 的元素，并返回是否移除到。代码如下：

public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;

int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}

return false;
}

fastRemove(es, i);

return true;
}

和 #remove(int index) 差不多，就是在 <Z> 处，改成获得首个为 o 的位置，之后就调用 #fastRemove(Object[] es, int i) 方法，快速移除即可。

我们先来看 #removeRange(int fromIndex, int toIndex) 方法，批量移除 [fromIndex, toIndex) 的多个元素，注意不包括 toIndex 的元素噢。代码如下：

protected void removeRange(int fromIndex, int toIndex) {

if (fromIndex> toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}

modCount++;

shiftTailOverGap(elementData, fromIndex, toIndex);
}

private static String outOfBoundsMsg(int fromIndex, int toIndex) {
return “From Index:” + fromIndex + “> To Index:” + toIndex;
}

<X> 处，调用 #shiftTailOverGap(Object[] es, int lo, int hi) 方法，移除 [fromIndex, toIndex) 的多个元素。代码如下：
private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
- 和 #fastRemove(Object[] es, int i) 方法一样的套路，先挪后置 null 。
- 有一点要注意，ArrayList 特别喜欢把多行代码写成一行。所以，可能会有胖又会有疑惑，貌似这里没有修改数组的大小 size 啊？答案在 i = (size -= hi - lo) ，简直到精简到难懂。

#removeAll(Collection<?> c) 方法，批量移除指定的多个元素。实现逻辑比较简单，但是看起来会比较绕。简单来说，通过两个变量 w（写入位置）和 r（读取位置），按照 r 顺序遍历数组 (elementData)，如果不存在于指定的多个元素中，则写入到 elementData 的 w 位置，然后 w 位置 + 1 ，跳到下一个写入位置。通过这样的方式，实现将不存在 elementData 覆盖写到 w 位置。可能理解起来有点绕，当然看代码也会有点绕绕，嘿嘿。代码如下：

public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}

调用 #batchRemove(Collection<?> c, boolean complement, final int from, final int end) 方法，批量移除指定的多个元素。代码如下：
boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {
Objects.requireNonNull(c);
final Object[] es = elementData;
int r;
for (r = from;; r++) {
if (r == end)
return false;
if (c.contains(es[r]) != complement)
break;
}
int w = r++;
try {
for (Object e; r < end; r++)
if (c.contains(e = es[r]) == complement)
es[w++] = e;
} catch (Throwable ex) {
System.arraycopy(es, r, es, w, end - r);
w += end - r;
throw ex;
} finally {
modCount += end - w;
shiftTailOverGap(es, w, end);
}
return true;
}
- 不要慌，我们先一起看下每一小块的逻辑。然后，胖友自己调试下，妥妥的就明白了。
- complement 参数，翻译过来是 “补足” 的意思。怎么理解呢？表示如果 elementData 元素在 c 集合中时，是否保留。
  - 如果 complement 为 false 时，表示在集合中，就不保留，这显然符合 #removeAll(Collection<?> c) 方法要移除的意图。
  - 如果 complement 为 true 时，表示在集合中，就暴露，这符合我们后面会看到的 #retainAll(Collection<?> c) 方法要求交集的意图。
- <1> 处，首先我们要知道这是一个基于 Optimize 优化的目的。我们是希望先判断是否 elementData 没有任何一个符合 c 的，这样就无需进行执行对应的移除逻辑。但是，我们又希望能够避免重复遍历，于是就有了这样一块的逻辑。总的来说，这块逻辑的目的是，优化，顺序遍历 elementData 数组，找到第一个不符合 complement ，然后结束遍历。
  - <1.1> 处，遍历到尾，都没不符合条件的，直接返回 false 。也就是说，丫根就不需要进行移除的逻辑。
  - <1.2> 处，如果包含结果不符合 complement 时，结束循环。可能有点难理解，我们来举个例子。假设 elementData 是 [1, 2, 3, 1] 时，c 是 [2] 时，那么在遍历第 0 个元素 1 时，则 c.contains(es[r]) != complement => false != false 不符合，所以继续缓存；然后，在遍历第 1 个元素 2 时，c.contains(es[r]) != complement => true != false 符合，所以结束循环。此时，我们便找到了第一个需要移除的元素的位置。当然，移除不是在这里执行，我们继续往下看。😈 淡定~
- <2> 处，设置开始写入 w 为 r ，注意不是 r++ 。这样，我们后续在循环 elementData 数组，就会从 w 开始写入。并且此时，r 也跳到了下一个位置，这样间接我们可以发现，w 位置的元素已经被 “跳过” 了。
- <3> 处，继续遍历 elementData 数组，如何符合条件，则进行移除。可能有点难理解，我们继续上述例子。遍历第 2 个元素 3 时候，c.contains(es[r]) == complement => false == false 符合，所以将 3 写入到 w 位置，同时 w 指向下一个位置；遍历第三个元素 1 时候，c.contains(es[r]) == complement => true == false 不符合，所以不进行任何操作。
- <4> 处，如果 contains 方法发生异常，则将 es 从 r 位置的数据写入到 es 从 w 开始的位置。这样，保证我们剩余未遍历到的元素，能够挪到从从 w 开始的位置，避免多出来一些元素。
- <5> 处，是不是很熟悉，将数组 [w, end) 位置赋值为 null 。
- 还是那句话，如果觉得绕，多调试，可以手绘点图，辅助理解下哈。

#retainAll(Collection<?> c) 方法，求 elementData 数组和指定多个元素的交集。简单来说，恰好和 #removeAll(Collection<?> c) 相反，移除不在 c 中的元素。代码如下：

public boolean retainAll(Collection<?> c) {
return batchRemove(c, true, 0, size);
}

试着按照艿艿上面解释的，自己走一波。

#indexOf(Object o) 方法，查找首个为指定元素的位置。代码如下：

public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
Object[] es = elementData;

if (o == null) {
for (int i = start; i < end; i++) {
if (es[i] == null) {
return i;
}
}

} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) {
return i;
}
}
}

return -1;
}

而 #contains(Object o) 方法，就是基于该方法实现。代码如下：

public boolean contains(Object o) {
return indexOf(o) >= 0;
}

有时我们需要查找最后一个为指定元素的位置，所以会使用到 #lastIndexOf(Object o) 方法。代码如下：

public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}

int lastIndexOfRange(Object o, int start, int end) {
Object[] es = elementData;

if (o == null) {
for (int i = end - 1; i>= start; i—) {
if (es[i] == null) {
return i;
}
}

} else {
for (int i = end - 1; i>= start; i—) {
if (o.equals(es[i])) {
return i;
}
}
}

return -1;
}

#get(int index) 方法，获得指定位置的元素。代码如下：

public E get(int index) {

Objects.checkIndex(index, size);

return elementData(index);
}

E elementData(int index) {
return (E) elementData[index];
}

随机访问 index 位置的元素，时间复杂度为 O(1) 。

#set(int index, E element) 方法，设置指定位置的元素。代码如下：

public E set(int index, E element) {

Objects.checkIndex(index, size);

E oldValue = elementData(index);

elementData[index] = element;

return oldValue;
}

#toArray() 方法，将 ArrayList 转换成 [] 数组。代码如下：

public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}

public static T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}

注意，返回的是 Object[] 类型噢。

实际场景下，我们可能想要指定 T 泛型的数组，那么我们就需要使用到 #toArray(T[] a) 方法。代码如下：

public T[] toArray(T[] a) {

if (a.length < size)

return (T[]) Arrays.copyOf(elementData, size, a.getClass());

System.arraycopy(elementData, 0, a, 0, size);

if (a.length> size)
a[size] = null;

return a;
}

分成 2 个情况，根据传入的 a 数组是否足够大。
<1> 处，如果传入的数组小于 size 大小，则直接复制一个新数组返回。一般情况下，我们不会这么干。
<2> 处，将 elementData 复制到 a 中。
- <2.1> 处，如果传入的数组大于 size 大小，则将 size 位置赋值为 null 。额，有点没搞懂这个有啥目的。
- <2.2> 处，返回传入的 a 。很稳。
考虑到 <1> 处，可能会返回一个新数组，所以即使 <2> 返回的就是 a 数组，最好使用还是按照 a = list.toArray(a) 。

#hashCode() 方法，求 ArrayList 的哈希值。代码如下：

public int hashCode() {

int expectedModCount = modCount;

int hash = hashCodeRange(0, size);

checkForComodification(expectedModCount);
return hash;
}

int hashCodeRange(int from, int to) {
final Object[] es = elementData;

if (to> es.length) {
throw new ConcurrentModificationException();
}

int hashCode = 1;
for (int i = from; i < to; i++) {
Object e = es[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}

可能胖友会好奇，为什么使用 31 作为乘子呢？可以看看《科普：为什么 String hashCode 方法选择数字 31 作为乘子》。

#equals(Object o) 方法，判断是否相等。代码如下：

public boolean equals(Object o) {

if (o == this) {
return true;
}

if (!(o instanceof List)) {
return false;
}

final int expectedModCount = modCount;

boolean equal = (o.getClass() == ArrayList.class)
? equalsArrayList((ArrayList<?>) o)
: equalsRange((List<?>) o, 0, size);

checkForComodification(expectedModCount);
return equal;
}

可能第一眼让胖友比较费解的是，为什么根据类型是否为 ArrayList ，调用了两个不同的方法去比对呢？因为普通的 List ，我们只能使用 Iterator 进行迭代，相比 ArrayList 的 elementData 属性遍历，性能会略低一些。😈 处处是细节哈。
这两个方法的代码如下，已经添加详细注释。代码如下：
boolean equalsRange(List<?> other, int from, int to) {
final Object[] es = elementData;
if (to> es.length) {
throw new ConcurrentModificationException();
}
var oit = other.iterator();
for (; from < to; from++) {
if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
return false;
}
}
return !oit.hasNext();
}
private boolean equalsArrayList(ArrayList<?> other) {
final int otherModCount = other.modCount;
final int s = size;
boolean equal;
if (equal = (s == other.size)) {
final Object[] otherEs = other.elementData;
final Object[] es = elementData;
if (s> es.length || s > otherEs.length) {
throw new ConcurrentModificationException();
}
for (int i = 0; i < s; i++) {
if (!Objects.equals(es[i], otherEs[i])) {
equal = false;
break;
}
}
}
other.checkForComodification(otherModCount);
return equal;
}

#clear() 方法，清空数组。代码如下：

public void clear() {

modCount++;

final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}

#writeObject(java.io.ObjectOutputStream s) 方法，实现 ArrayList 的序列化。代码如下：

@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {

int expectedModCount = modCount;

s.defaultWriteObject();

s.writeInt(size);

for (int i = 0; i < size; i++) {
s.writeObject(elementData[i]);
}

if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

<1> 处，调用 ObjectOutputStream#defaultWriteObject() 方法，写入非静态属性、非 transient 属性。可能有些胖友不了解 Java 的序列化相关的知识，可以看看《Serializable 原理》文章。
<2> 处，写入 size ，主要为了与 clone 方法的兼容。不过艿艿也觉得挺奇怪的，明明在 <1> 处，已经写入了 size ，这里怎么还来这么一出呢？各种翻查资料，暂时只看到《源码分析：ArrayList 的 writeobject 方法中的实现是否多此一举？》有个讨论。
<3> 吹，逐个写入 elementData 元素的数组。我们回过来看下 elementData 的定义，它是一个 transient 修饰的属性。为什么呢？因为 elementData 数组，并不一定是全满的，而可能是扩容的时候有一定的预留，如果直接序列化，会有很多空间的浪费，所以只序列化从 [0, size) 的元素，减少空间的占用。

#readObject(java.io.ObjectInputStream s) 方法，反序列化数组。代码如下：

@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {

s.defaultReadObject();

s.readInt();

if (size> 0) {

SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);

Object[] elements = new Object[size];

for (int i = 0; i < size; i++) {
elements[i] = s.readObject();
}

elementData = elements;
} else if (size == 0) {

elementData = EMPTY_ELEMENTDATA;
} else {
throw new java.io.InvalidObjectException(“Invalid size:” + size);
}
}

和序列化的过程，恰好相反（哈哈哈，不然还想咋样），一眼就看的明白。

#clone() 方法，克隆 ArrayList 对象。代码如下：

public Object clone() {
try {

ArrayList v = (ArrayList) super.clone();

v.elementData = Arrays.copyOf(elementData, size);

v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {

throw new InternalError(e);
}
}

注意，elementData 是重新拷贝出来的新的数组，避免和原数组共享。

#subList(int fromIndex, int toIndex) 方法，创建 ArrayList 的子数组。代码如下：

public List subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList<>(this, fromIndex, toIndex);
}

private static class SubList extends AbstractList implements RandomAccess {

private final ArrayList root;

private final SubList parent;

private final int offset;

private int size;

}

实际使用时，一定要注意，SubList 不是一个只读数组，而是和根数组 root 共享相同的 elementData 数组，只是说限制了 [fromIndex, toIndex) 的范围。
这块的源码，并不复杂，所以这里也就不展开了。一般情况下，我们也不需要了解它的源码，嘿嘿。

#iterator() 方法，创建迭代器。一般情况下，我们使用迭代器遍历 ArrayList、LinkedList 等等 List 的实现类。代码如下：

public Iterator iterator() {
return new Itr();
}

创建 Itr 迭代器。Itr 实现 java.util.Iterator 接口，是 ArrayList 的内部类。虽然说 AbstractList 也提供了一个 Itr 的实现，但是 ArrayList 为了更好的性能，所以自己实现了，在其类上也有注释 “An optimized version of AbstractList.Itr”。

Itr 一共有 3 个属性，如下：

int cursor;

int lastRet = -1;

int expectedModCount = modCount;

Itr() {}

每个属性，胖友自己看看注释噢。

下面，让我们来看看 Itr 对 Iterator 的 4 个实现方法。

#hasNext() 方法，判断是否还可以继续迭代。代码如下：

public boolean hasNext() {
return cursor != size;
}

cursor 如果等于 size ，说明已经到数组末尾，无法继续迭代了。

#next() 方法，下一个元素。代码如下：

public E next() {

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();
}

<1> 处，记录当前 cursor 的位置。因为我们当前返回的就是要求 cursor 位置的元素。
<2> 处，cursor 指向下一个位置。
<3> 处，返回当前位置的元素。同时在 <4> 处，会将 lastRet 指向当前位置。

#remove() 方法，移除当前元素。代码如下：

public void remove() {

if (lastRet < 0)
throw new IllegalStateException();

checkForComodification();

try {

ArrayList.this.remove(lastRet);

cursor = lastRet;

lastRet = -1;

expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

<1> 处，调用 #remove(int index) 方法，移除 lastRet 位置的元素。所以，如果要注意，如果移除元素比较前面，会将后面位置的往前挪，即复制，可能比较消耗性能。
<2> 处，cursor 指向 lastRet 位置，因为被移了，所以需要后退下。
<3> 处，lastRet 标记为 -1 ，因为当前元素被移除了。
<4> 处，记录新的数组的修改次数。因为此处修改了数组，如果不修改下，后续迭代肯定会报错。

#forEachRemaining(Consumer<? super E> action) 方法，消费剩余未迭代的元素。代码如下：

@Override
public void forEachRemaining(Consumer<? super E> action) {

Objects.requireNonNull(action);

final int size = ArrayList.this.size;

int i = cursor;
if (i < size) {

final Object[] es = elementData;
if (i>= es.length)
throw new ConcurrentModificationException();

for (; i < size && modCount == expectedModCount; i++)
action.accept(elementAt(es, i));

cursor = i;
lastRet = i - 1;

checkForComodification();
}
}

比较简单，胖友自己瞅瞅。貌似平时这个方法用的不是很多。

艿艿：可能一些胖友不了解 ListIterator 迭代器，因为平时使用不多。可以先去看看《Java 集合框架之 Iterator 和 ListIterator》。简单来说，ListIterator 是为 List 设计的，功能更强大的 Iterator 迭代器。

#listIterator(...) 方法，创建 ListIterator 迭代器。代码如下：

public ListIterator listIterator(int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}

public ListIterator listIterator() {
return new ListItr(0);
}

创建 ListItr 迭代器。ListItr 实现 java.util.ListIterator 接口，是 ArrayList 的内部类。虽然说 AbstractList 也提供了一个 ListItr 的实现，但是 ArrayList 为了更好的性能，所以自己实现了，在其类上也有注释 “An optimized version of AbstractList.ListItr”。

ListItr 直接继承 Itr 类，无自定义的属性。代码如下：

ListItr(int index) {
super();
cursor = index;
}

可以手动设置指定的位置开始迭代。

因为 ListItr 的实现代码比较简单，我们就不逐个来看了，直接贴加了注释的代码。代码如下：

public boolean hasPrevious() {
return cursor != 0;
}

public int nextIndex() {
return cursor;
}

public int previousIndex() {
return cursor - 1;
}

@SuppressWarnings(“unchecked”)
public E previous() {

checkForComodification();

int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();

Object[] elementData = ArrayList.this.elementData;
if (i>= elementData.length)
throw new ConcurrentModificationException();

cursor = i;

return (E) elementData[lastRet = i];
}

public void set(E e) {

if (lastRet < 0)
throw new IllegalStateException();

checkForComodification();

try {

ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

public void add(E e) {

checkForComodification();

try {

int i = cursor;
ArrayList.this.add(i, e);

cursor = i + 1;

lastRet = -1;

expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

咳咳咳，比想象中的长的多的一篇文章。并且实际上，我们还有几个 ArrayList 的方法的解析没有写，如下：

#spliterator()
#removeIf(Predicate<? super E> filter)
#replaceAll(UnaryOperator<E> operator)
#sort(Comparator<? super E> c)
#forEach(Consumer<? super E> action)

哈哈，也是比较简单的方法，胖友自己可以解决一波的哈。就当，课后作业？！嘿嘿。

下面，我们来对 ArrayList 做一个简单的小结：

ArrayList 是基于 [] 数组实现的 List 实现类，支持在数组容量不够时，一般按照 1.5 倍自动扩容。同时，它支持手动扩容、手动缩容。
ArrayList 随机访问时间复杂度是 O(1) ，查找指定元素的平均时间复杂度是 O(n) 。> 可能胖友对时间复杂度的计算方式不是很了解，可以看看《算法复杂度分析（上）：分析算法运行时，时间资源及空间资源的消耗》和《算法复杂度分析（下）：最好、最坏、平均、均摊等时间复杂度概述》两文。

ArrayList 移除指定位置的元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。> 最好时间复杂度发生在末尾移除的情况。

ArrayList 移除指定元素的时间复杂度是 O(n) 。> 因为首先需要进行查询，然后在使用移除指定位置的元素，无论怎么计算，都需要 O(n) 的时间复杂度。

ArrayList 添加元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。> 最好时间复杂度发生在末尾添加的情况。

结尾在抛个拓展，在 Redis String 的数据结构，实现方式是类似 Java ArrayList 的方式，感兴趣的胖友可以自己去瞅瞅。
http://svip.iocoder.cn/JDK/Collection-ArrayList/