ArrayList源码解析

概述

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

顶部注释

List接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括null在内的所有元素。除了实现List接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于Vector类，除了此类是不同步的。）

size、isEmpty、get、set、iterator和listIterator操作都以固定时间运行。add操作以分摊的固定时间运行，也就是说，添加n个元素需要O(n)时间。其他所有操作都以线性时间运行（大体上讲）。与用于LinkedList实现的常数因子相比，此实现的常数因子较低。

每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。

在添加大量元素前，应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量。这可以减少递增式再分配的数量。

注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。（结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改。）这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象，则应该使用Collections.synchronizedList方法将该列表“包装”起来。这最好在创建时完成，以防止意外对列表进行不同步的访问：
List list = Collections.synchronizedList(new ArrayList(…));

此类的iterator和listIterator方法返回的迭代器是快速失败的：在创建迭代器之后，除非通过迭代器自身的remove或add方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，因为一般来说，不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此，为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法：迭代器的快速失败行为应该仅用于检测bug。

此类是Java Collections Framework的成员。

从上面的内容中可以总结出以下几点：

底层：ArrayList是List接口的大小可变数组的实现。
是否允许null：ArrayList允许null元素。
时间复杂度：size、isEmpty、get、set、iterator和listIterator方法都以固定时间运行，时间复杂度为O(1)。add和remove方法需要O(n)时间。与用于LinkedList实现的常数因子相比，此实现的常数因子较低。
容量：ArrayList的容量可以自动增长。
是否同步：ArrayList不是同步的。
迭代器：ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的。

类图

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

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

java.util.List接口，提供数组的添加、删除、修改、迭代遍历等操作。
java.util.RandomAccess 接口，表示 ArrayList 支持快速的随机访问。

RandomAccess 是 List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。如果 List 子类实现了 RandomAccess 接口，那表示它能快速随机访问存储的元素，这时候你想到的可能是数组，通过下标 index 访问，实现了该接口的 ArrayList 底层实现就是数组，同样是通过下标访问，只是我们需要用 get() 方法的形式， ArrayList 底层仍然是数组的访问形式。

同时你应该想到链表， LinkedList 底层实现是链表， LinkedList 没有实现 RandomAccess 接口，发现这一点就是突破问题的关键点。

数组支持随机访问，查询速度快，增删元素慢；链表支持顺序访问，查询速度慢，增删元素快。所以对应的 ArrayList 查询速度快，LinkedList 查询速度慢， RandomAccess 这个标记接口就是标记能够随机访问元素的集合，简单来说就是底层是数组实现的集合。

为了提升性能，在遍历集合前，我们便可以通过 instanceof 做判断，选择合适的集合遍历方式，当数据量很大时，就能大大提升性能。

随机访问列表使用循环遍历，顺序访问列表使用迭代器遍历。
java.io.Serializable接口，表示 ArrayList 支持序列化的功能。

Java序列化是指把Java对象转换为字节序列的过程；Java反序列化是指把字节序列恢复为Java对象的过程。

java的序列化有两种方式：
1. 实现序列化接口Serializable，这个使用的比较多。Serializable接口是一个空的接口，它的主要作用就是标识这个类的对象是可序列化的。
2. 实现接口Externalizable。Exterinable继承了Serializable，是Serializable的一个扩展，对于哪些属性可以序列化，哪些可以反序列化可以做详细地约束。
相关工具类：
1. java.io.ObjectOutputStream：表示对象输出流它是OutputStream类的一个子类，对应的ObjectOutputStream.WriteObject(Object object)就要求参数object实现Serializable接口。
2.java.io.ObjectInputStream：表示对象输入流相应地，它的readObject(Object object)方

法从输入流中读取字节序列，再把它们反序列化成为一个对象，并返回。

方式一：实现Serializable接口

Serializable源码
```
/*
 * Copyright (c) 1996, 2005, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package java.io;
/**
 * Serializability of a class is enabled by the class implementing the
 * java.io.Serializable interface. Classes that do not implement this
 * interface will not have any of their state serialized or
 * deserialized.  All subtypes of a serializable class are themselves
 * serializable.  The serialization interface has no methods or fields
 * and serves only to identify the semantics of being serializable.
 *
 * @author  unascribed
 * @see java.io.ObjectOutputStream
 * @see java.io.ObjectInputStream
 * @see java.io.ObjectOutput
 * @see java.io.ObjectInput
 * @see java.io.Externalizable
 * @since   JDK1.1
 */
public interface Serializable {
}
```
中间还省略了很多注释，再忽略上面留下的注释，发现这个接口是空的！没有字段，没有方法，只是标识一个类的对象是否可序列化（实现了这个接口，就表示可以序列化）。

实现Serializable接口前后并没有增加新方法，只是多了一个serialVersionUID，其实这个字段也不是必须的。若不写serialVersionUID。程序也能运行成功，不过eclipe会显示警告。

其实，Java的序列化机制是通过在运行时判断类的serialVersionUID来验证版本一致性的。在进行反序列化时，JVM会把传来的字节流中的serialVersionUID与本地相应实体类的serialVersionUID进行比较，如果相同就认为是一致的，可以进行反序列化，否则就会出现序列化版本不一致的异常(InvalidCastException)。

所以最好有这个字段，那么要如何添加呢？鼠标移动到警告处，eclipse在给出警告的同时也给出了解决方法：
1. 添加默认值，即1L;
2. 添加自动产生的ID值，我的是86853763327914859890L;（推荐）
3. 通过@SuppressWarnings 批注取消特定代码段（即，类或方法）中的警告。
transicent的作用

如果，不希望某些字段被序列化，如LoginInfo中的username，只需在对应字段的定义时使用关键词transient：

方式二：实现Externalizable接口

Externalizable源码
```
/*
 * Copyright (c) 1996, 2004, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package java.io;
import java.io.ObjectOutput;
import java.io.ObjectInput;

/**
 * @author  unascribed
 * @see java.io.ObjectOutputStream
 * @see java.io.ObjectInputStream
 * @see java.io.ObjectOutput
 * @see java.io.ObjectInput
 * @see java.io.Serializable
 * @since   JDK1.1
 */
public interface Externalizable extends java.io.Serializable {
    /**
     * @param out the stream to write the object to
     * @exception IOException Includes any I/O exceptions that may occur
     */
    void writeExternal(ObjectOutput out) throws IOException;
    /**
     * @param in the stream to read data from in order to restore the object
     * @exception IOException if I/O errors occur
     * @exception ClassNotFoundException If the class for an object being
     *              restored cannot be found.
     */
    void readExternal(ObjectInput in) throws IOException, ClassNotFoundException;
}
```
Externalizable继承了Serializable接口，并添加了两个新的方法，分别表示在哪些字段能被序列化和哪些字段能够反序列化。

在Serializable接口实现的类中，transient修饰的字段不参与序列化过程；在Externalizable接口实现的类中，transient无效。即：transient只能与Serializable搭配使用。

Externalizable实现的类对象，序列化与反序列化由writeExternal与readExternal两个函数控制（内部操作的字段要对应），而且反序列时会先调用无参构造函数创建实例对象，再通过readExternal读取数据。所以Externalizable实现的类若想反序列化，必须有无参构造函数。而恢复Serializable对象，完全以之前存储的二进制为基础来构造，不调用构造函数。
java.lang.Cloneable接口，表示 ArrayList 支持克隆。

实现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制。如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法，则会导致抛出 CloneNotSupportedException 异常。

具体的可以参考R大的回答

继承了 java.util.AbstractList 抽象类，而 AbstractList 提供了 List 接口的骨架实现，大幅度的减少了实现迭代遍历相关操作的代码。

属性

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

 /**
     * 初始化默认容量。
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 指定该ArrayList容量为0时，返回该空数组。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。
     * 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 保存添加到ArrayList中的元素。
     * ArrayList的容量就是该数组的长度。
     * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，数组将扩容值DEFAULT_CAPACITY。
     * 被标记为transient，在对象被序列化的时候不会被序列化。至于没有使用private修饰，后面注释是写的“为了简化嵌套类的访问”，但是楼主实测加了private嵌套类一样可以访问。
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList的实际大小（数组包含的元素个数）。
     * @serial
     */
    private int size;

构造方法

ArrayList 一共有三个构造方法

ArrayList(int initialCapacity)：构造一个指定容量为capacity的空ArrayList。

传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于0抛出异常。

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 如果传入的初始容量大于0，就新建一个数组存储元素
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 如果传入的初始容量等于0，使用空数组EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 如果传入的初始容量小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
}

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

2.ArrayList()：构造一个初始容量为 10 的空列表。

public ArrayList() {
        // 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        // 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

3.ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

传入集合并初始化elementData，这里会使用拷贝把传入集合的元素拷贝到elementData数组中，如果元素个数为0，则初始化为EMPTY_ELEMENTDATA空数组。

/**
 * 把传入集合的元素初始化到ArrayList中
*/
public ArrayList(Collection<? extends E> c) {
        // 集合转数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 检查c.toArray()返回的是不是Object[]类型，如果不是，重新拷贝成Object[].class类型
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果c的空集合，则初始化为空数组EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        }
}

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

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

为什么c.toArray();返回的有可能不是Object[]类型呢？请看下面的代码：

// ArrayListTest.java

public static void test02() {
    List<Integer> list = Arrays.asList(1, 2, 3);
    Object[] array = list.toArray(); // JDK8 返回 Integer[] 数组，JDK9+ 返回 Object[] 数组。
    System.out.println("array className ：" + array.getClass().getSimpleName());

    // 此处，在 JDK8 和 JDK9+ 表现不同，前者会报 ArrayStoreException 异常，后者不会。
    array[0] = new Object();
}

jdk8执行下:

jdk9执行下:

在 JDK8 中，返回的实际是 Integer [] 数组，那么我们将 Object 对象设置到其中，肯定是会报错的。具体怎么修复的，看 JDK-6260652 的最末尾一段。

add(E e)方法

顺序添加单个元素到数组，平均时间复杂度为O(1)。代码如下：

public boolean add(E e) {
        // 检查是否需要扩容
        ensureCapacityInternal(size + 1);
        // 把元素插入到最后一位
        elementData[size++] = e;
        return true;
}
 private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            // 扩容
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新容量发现比需要的容量还小，则以需要的容量为准
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果新容量已经超过最大容量了，则使用最大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 以新容量拷贝出来一个新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
}

（1）检查是否需要扩容；

（2）如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA则初始化容量大小为DEFAULT_CAPACITY；

（3）新容量是老容量的1.5倍（oldCapacity + (oldCapacity >> 1)），如果加了这么多容量发现比需要的容量还小，则以需要的容量为准；

（4）创建新容量的数组并把老数组拷贝到新数组；

add(int index, E element)方法

添加元素到指定位置，平均时间复杂度为O(n)。

 public void add(int index, E element) {
        // 检查是否越界
        rangeCheckForAdd(index);
        // 检查是否需要扩容
        ensureCapacityInternal(size + 1);
        // 将inex及其之后的元素往后挪一位，则index位置处就空出来了
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将元素插入到index的位置
        elementData[index] = element;
        // 大小增1
        size++;
    }
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

（1）检查索引是否越界；

（2）检查是否需要扩容；

（3）把插入索引位置后的元素都往后挪一位；

（4）在插入索引位置放置插入的元素；

（5）大小加1；

addAll 方法

求两个集合的并集。

  /**
    * 将集合c中所有元素添加到当前ArrayList中
    */
    public boolean addAll(Collection<? extends E> c) {
        // 将集合c转为数组
        Object[] a = c.toArray();
        int numNew = a.length;
        // 检查是否需要扩容
        ensureCapacityInternal(size + numNew);
        // 将c中元素全部拷贝到数组的最后
        System.arraycopy(a, 0, elementData, size, numNew);
        // 大小增加c的大小
        size += numNew;
        // 如果c不为空就返回true，否则返回false
        return numNew != 0;
    }

（1）拷贝c中的元素到数组a中；

（2）检查是否需要扩容；

（3）把数组a中的元素拷贝到elementData的尾部；

get(int index)方法

获取指定索引位置的元素，时间复杂度为O(1)。

 public E get(int index) {
        // 检查是否越界
        rangeCheck(index);
        // 返回数组index位置的元素
        return elementData(index);
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

（1）检查索引是否越界，这里只检查是否越上界，如果越上界抛出IndexOutOfBoundsException异常，如果越下界抛出的是ArrayIndexOutOfBoundsException异常。

（2）返回索引位置处的元素；

remove(int index)方法

删除指定索引位置的元素，时间复杂度为O(n)。

public E remove(int index) {
        // 检查是否越界
        rangeCheck(index);
        modCount++;
        // 获取index位置的元素
        E oldValue = elementData(index);
        // 如果index不是最后一位，则将index之后的元素往前挪一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        // 将最后一个元素删除，帮助GC
        elementData[--size] = null; // clear to let GC do its work
        // 返回旧值
        return oldValue;
}

（1）检查索引是否越界；

（2）获取指定索引位置的元素；

（3）如果删除的不是最后一位，则其它元素往前移一位；

（4）将最后一位置为null，方便GC回收；

（5）返回删除的元素。

可以看到，ArrayList删除元素的时候并没有缩容。

remove(Object o)方法

删除指定元素值的元素，时间复杂度为O(n)。

  public boolean remove(Object o) {
        if (o == null) {
            // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
            for (int index = 0; index < size; index++)
                // 如果要删除的元素为null，则以null进行比较，使用==
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除
            for (int index = 0; index < size; index++)
                // 如果要删除的元素不为null，则进行比较，使用equals()方法
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    private void fastRemove(int index) {
        // 少了一个越界的检查
        modCount++;
        // 如果index不是最后一位，则将index之后的元素往前挪一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        // 将最后一个元素删除，帮助GC
        elementData[--size] = null; // clear to let GC do its work
    }

（1）找到第一个等于指定元素值的元素；

（2）快速删除；

fastRemove(int index)相对于remove(int index)少了检查索引越界的操作，可见jdk将性能优化到极致。

retainAll方法

求两个集合的交集。

    public boolean retainAll(Collection<?> c) {
        // 集合c不能为null
        Objects.requireNonNull(c);
        // 调用批量删除方法，这时complement传入true，表示删除不包含在c中的元素
        return batchRemove(c, true);
    }
    /**
    * 批量删除元素
    * complement为true表示删除c中不包含的元素
    * complement为false表示删除c中包含的元素
    */
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        // 使用读写两个指针同时遍历数组
        // 读指针每次自增1，写指针放入元素的时候才加1
        // 这样不需要额外的空间，只需要在原有的数组上操作就可以了
        int r = 0, w = 0;
        boolean modified = false;
        try {
            // 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准）
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 正常来说r最后是等于size的，除非c.contains()抛出了异常
            if (r != size) {
                // 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // 将写指针之后的元素置为空，帮助GC
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）
                size = w;
                modified = true;
            }
        }
        // 有修改返回true
        return modified;
    }

（1）遍历elementData数组；

（2）如果元素在c中，则把这个元素添加到elementData数组的w位置并将w位置往后移一位；

（3）遍历完之后，w之前的元素都是两者共有的，w之后（包含）的元素不是两者共有的；

（4）将w之后（包含）的元素置为null，方便GC回收；

removeAll方法

求两个集合的单方向差集，只保留当前集合中不在c中的元素，不保留在c中不在当前集体中的元素。

public boolean removeAll(Collection<?> c) {
        // 集合c不能为空
        Objects.requireNonNull(c);
        // 同样调用批量删除方法，这时complement传入false，表示删除包含在c中的元素
        return batchRemove(c, false);
}

与retainAll(Collection<?> c)方法类似，只是这里保留的是不在c中的元素。

set( int index, E element)方法

  /**
     * 替换指定索引的元素
     *
     * @param 被替换元素的索引
     * @param element 即将替换到指定索引的元素
     * @return 返回被替换的元素
     * @throws IndexOutOfBoundsException 如果参数指定索引index>=size，抛出一个越界异常
     */
    public E set(int index, E element) {
        //检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
        rangeCheck(index);

        //记录被替换的元素
        E oldValue = elementData(index);
        //替换元素
        elementData[index] = element;
        //返回被替换的元素
        return oldValue;
    }

removeRange(int fromIndex, int toIndex)方法

批量移除 [fromIndex, toIndex) 的多个元素，注意不包括 toIndex 的元素噢。代码如下：

 // ArrayList.java

protected void removeRange(int fromIndex, int toIndex) {
    // 范围不正确，抛出 IndexOutOfBoundsException 异常
    if (fromIndex > toIndex) {
        throw new IndexOutOfBoundsException(
                outOfBoundsMsg(fromIndex, toIndex));
    }
    // 增加数组修改次数
    modCount++;
    // <X> 移除 [fromIndex, toIndex) 的多个元素
    shiftTailOverGap(elementData, fromIndex, toIndex);
}

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

clear()方法

public void clear() {
        modCount++;

        // 将每个元素置为空这样gc便能回收
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
}

isEmpty()方法

判断列表是否为空

public boolean isEmpty() {
        return size == 0;
}

writeObject(java.io.ObjectOutputStream s)方法

实现 ArrayList 的序列化

// ArrayList.java

@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out element count, and any hidden stuff
    // 获得当前的数组修改次数
    int expectedModCount = modCount;

    // 写入非静态属性、非 transient 属性
    s.defaultWriteObject();

    // Write out size as capacity for behavioral compatibility with clone()
    // 写入 size ，主要为了与 clone 方法的兼容
    s.writeInt(size);

    // Write out all elements in the proper order.
    // 逐个写入 elementData 数组的元素
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }

    // 如果 other 修改次数发生改变，则抛出 ConcurrentModificationException 异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

因为 elementData 数组，并不一定是全满的，而可能是扩容的时候有一定的预留，如果直接序列化，会有很多空间的浪费，所以只序列化从 [0, size) 的元素，减少空间的占用。

readObject(java.io.ObjectInputStream s) 方法

反序列化

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

    // Read in size, and any hidden stuff
    // 读取非静态属性、非 transient 属性
    s.defaultReadObject();

    // Read in capacity
    // 读取 size ，不过忽略不用
    s.readInt(); // ignored

    if (size > 0) {
        // like clone(), allocate array based upon size not capacity
        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); 
        // 创建 elements 数组
        Object[] elements = new Object[size];

        // Read in all elements in the proper order.
        // 逐个读取
        for (int i = 0; i < size; i++) {
            elements[i] = s.readObject();
        }

        // 赋值给 elementData
        elementData = elements;
    } else if (size == 0) {
        // 如果 size 是 0 ，则直接使用空数组
        elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new java.io.InvalidObjectException("Invalid size: " + size);
    }
}

indexOf(Object o)

返回指定元素在此列表中首次出现的索引；如果此列表不包含该元素，则返回-1。更正式地，返回最低索引i ，使（o == null？get（i）== null：o.equals（get（i）））；如果没有这样的索引，则返回-1。

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

clone() 方法

// ArrayList.java

public Object clone() {
    try {
        // 调用父类，进行克隆
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 拷贝一个新的数组
        v.elementData = Arrays.copyOf(elementData, size);
        // 设置数组修改次数为 0
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

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

创建子数组

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

// ArrayList.java

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

private static class SubList<E> extends AbstractList<E> implements RandomAccess {

    /**
     * 根 ArrayList
     */
    private final ArrayList<E> root;
    /**
     *  父 SubList
     */
    private final SubList<E> parent;
    /**
     * 起始位置
     */
    private final int offset;
    /**
     * 大小
     */
    private int size;

    // ... 省略代码
}

实际使用时，一定要注意，SubList 不是一个只读数组，而是和根数组 root 共享相同的 elementData 数组，只是说限制了 [fromIndex, toIndex) 的范围。

创建 Iterator 迭代器

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

// ArrayList.java

public Iterator<E> iterator() {
    return new Itr();
}

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

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

/**
 * 下一个访问元素的位置，从下标 0 开始。
 */
int cursor;       // index of next element to return
/**
 * 上一次访问元素的位置。
 *
 * 1. 初始化为 -1 ，表示无上一个访问的元素
 * 2. 遍历到下一个元素时，lastRet 会指向当前元素，而 cursor 会指向下一个元素。这样，如果我们要实现 remove 方法，移除当前元素，就可以实现了。
 * 3. 移除元素时，设置为 -1 ，表示最后访问的元素不存在了，都被移除咧。
 */
int lastRet = -1; // index of last element returned; -1 if no such
/**
 * 创建迭代器时，数组修改次数。
 *
 * 在迭代过程中，如果数组发生了变化，会抛出 ConcurrentModificationException 异常。
 */
int expectedModCount = modCount;

// prevent creating a synthetic constructor
Itr() {}

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

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

// ArrayList.java#Itr

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

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

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

// ArrayList.java#Itr

public E next() {
    // 校验是否数组发生了变化
    checkForComodification();
    // 判断如果超过 size 范围，抛出 NoSuchElementException 异常
    int i = cursor; // i 记录当前 cursor 的位置
    if (i >= size)
        throw new NoSuchElementException();
    // 判断如果超过 elementData 大小，说明可能被修改了，抛出 ConcurrentModificationException 异常
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    // cursor 指向下一个位置
    cursor = i + 1;
    // 返回当前位置的元素
    return (E) elementData[lastRet = i]; // 此处，会将 lastRet 指向当前位置
}

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

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

// ArrayList.java#Itr

public void remove() {
    // 如果 lastRet 小于 0 ，说明没有指向任何元素，抛出 IllegalStateException 异常
    if (lastRet < 0)
        throw new IllegalStateException();
    // 校验是否数组发生了变化
    checkForComodification();

    try {
        // 移除 lastRet 位置的元素
        ArrayList.this.remove(lastRet);
        // cursor 指向 lastRet 位置，因为被移了，所以需要后退下
        cursor = lastRet;
        // lastRet 标记为 -1 ，因为当前元素被移除了
        lastRet = -1;
        // 记录新的数组的修改次数
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

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

// ArrayList.java#Itr

@Override
public void forEachRemaining(Consumer<? super E> action) {
    // 要求 action 非空
    Objects.requireNonNull(action);
    // 获得当前数组大小
    final int size = ArrayList.this.size;
    // 记录 i 指向 cursor
    int i = cursor;
    if (i < size) {
        // 判断如果超过 elementData 大小，说明可能被修改了，抛出 ConcurrentModificationException 异常
        final Object[] es = elementData;
        if (i >= es.length)
            throw new ConcurrentModificationException();
        // 逐个处理
        for (; i < size && modCount == expectedModCount; i++)
            action.accept(elementAt(es, i));
        // update once at end to reduce heap write traffic
        // 更新 cursor 和 lastRet 的指向
        cursor = i;
        lastRet = i - 1;
        // 校验是否数组发生了变化
        checkForComodification();
    }
}

listIterator(...) 方法

 ArrayList.java

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

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

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

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

// ArrayList.java#ListItr

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

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

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

// ArrayList.java#ListItr

/**
 * @return 是否有前一个
 */
public boolean hasPrevious() {
    return cursor != 0;
}

/**
 * @return 下一个位置
 */
public int nextIndex() {
    return cursor;
}

/**
 * @return 前一个位置
 */
public int previousIndex() {
    return cursor - 1;
}

/**
 * @return 前一个元素
 */
@SuppressWarnings("unchecked")
public E previous() {
    // 校验是否数组发生了变化
    checkForComodification();
    // 判断如果小于 0 ，抛出 NoSuchElementException 异常
    int i = cursor - 1;
    if (i < 0)
        throw new NoSuchElementException();
    // 判断如果超过 elementData 大小，说明可能被修改了，抛出 ConcurrentModificationException 异常
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    // cursor 指向上一个位置
    cursor = i;
    // 返回当前位置的元素
    return (E) elementData[lastRet = i]; // 此处，会将 lastRet 指向当前位置
}

/**
 * 设置当前元素
 *
 * @param e 设置的元素
 */
public void set(E e) {
    // 如果 lastRet 无指向，抛出 IllegalStateException 异常
    if (lastRet < 0)
        throw new IllegalStateException();
    // 校验是否数组发生了变化
    checkForComodification();

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

/**
 * 添加元素当当前位置
 *
 * @param e 添加的元素
 */
public void add(E e) {
    // 校验是否数组发生了变化
    checkForComodification();

    try {
        // 添加元素到当前位置
        int i = cursor;
        ArrayList.this.add(i, e);
        // cursor 指向下一个位置，因为当前位置添加了新的元素，所以需要后挪
        cursor = i + 1;
        // lastRet 标记为 -1 ，因为当前元素并未访问
        lastRet = -1;
        // 记录新的数组的修改次数
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

lastIndexOf(Object o)

返回指定元素在此列表中最后一次出现的索引；如果此列表不包含该元素，则返回-1。更正式地，返回最高索引i ，使（o == null？get（i）== null：o.equals（get（i）））；如果没有这样的索引，则返回-1。

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

toArray()方法

以正确的顺序（从第一个元素到最后一个元素）返回一个包含此列表中所有元素的数组。
返回的数组将是“安全的”，因为此列表不保留对其的引用。（换句话说，此方法必须分配一个新数组）。因此，调用者可以自由修改返回的数组。此方法充当基于数组的API和基于集合的API之间的桥梁。
返回值：包含此列表中所有元素的序列按适当顺序的数组

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
}

contains()方法

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

别废话,拿你代码给我看。