ArrayList源码阅读

ArrayList的数据结构

ArrayList往往被人用来与LinkedList对比，它们俩最重要的差异之一就是：ArrayList的底层是由数组组成的，而LinkedList的底层则是由链表组成，对于LinkedList不再多赘述，具体可以看一下LinkedList的文章。回到ArrayList中来，其实现的数据结构是一个名为elementData的Object数组，可以存放所有Object对象，因此我们对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扔出ConcurrentModificationException 。 因此，编写依赖于此异常的程序的正确性将是错误的： 迭代器的故障快速行为应仅用于检测错误。

这个类是Java Collections Framework的成员。

总结上面的顶部注释可以得到以下几点：

• 底部实现：可调整大小的数组实现的。
• 是否允许null值：允许所有元素，包括null。
• 是否是线程安全的：不是线程安全的。
• 迭代器： 迭代器是fast-fail，但是迭代器的快速失败行为不能得到保证。
• 运行时间：在get，set，size等操作中，都是以常数时间运行，而add操作需要O(n)时间运行。

ArrayList的定义

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• ArrayList：支持泛型的存储模式。
• extends AbstractList：继承于AbstractList，继承了其中的方法，方便操作。
• implements List：实现了List接口，与继承AbstractList作用相同，实现该接口提供的方法，方便了实现。但是据开发这个collection 的作者Josh说：这其实是一个mistake，因为他写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。
• implements RandomAccess：实现了RandomAccess接口，表明支持固定时间的快速随机访问，这也是其在get和set方法时已固定时间运行的原因
• implements Cloneable：实现了Cloneable接口，内部可以调用clone()方法来返回实例的浅拷贝(shallow copy)。
• implements Serializable：实现了Serializable接口，表明该类时可以序列化的。

静态全局变量

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

   /**
    *	  用于空实例的共享空数组实例。
    *	 也就是说当传入的指定容量为0的时候建立数组。
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

   /**
    * 	共享空数组实例，用于默认大小的空实例。
    * 	我们将其与EMPTY_ELEMENTDATA区分开来，以了解添加第一个元素时应该膨胀多少。
    * 	当无指定的容量传入时，返回的数组。其与EMPTY_ELEMENTDATA的区别在于：
    * 	EMPTY_ELEMENTDATA是当传入的指定容量为时候返回的
    * 	DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为传入指定容量参数时候返回的。 
    */
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    * 	存储ArrayList元素的数组缓冲区。
    * 	ArrayList的容量是这个数组缓冲区的长度。
    * 	当添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。
    * 	也就是底层用来存储元素的数组
    */
   transient Object[] elementData; // 非私有以简化嵌套类访问,这里是用来为subList方法使用的。

   /**
    * 	ArrayList的大小(它包含的元素的数量)。
    * 	ArrayList中实际包含的元素的数量
    *
    * @serial
    */
   private int size;

       /**
   	* 	最大可分配的数组大小，减去8是为了一些vm在数组中保留一些头信息。
   	* 	试图分配更大的数组可能会导致OutOfMemoryError:请求的数组大小超过VM限制
   	*/
  	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法

指定初始容量

/**
    *	构造具有指定初始容量的空列表。
    *
    * @param  initialCapacity  列表的初始容量
    * @throws IllegalArgumentException 如果指定初始容量是负的       
    */
   public ArrayList(int initialCapacity) {
   	/**
   	 * 如果指定的初始容量大于零，则创建一个指定初始容量大小的数组
   	 */
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
       	/**
       	 * 如果指定的初始等于零，则使用空数组EMPTY_ELEMENTDATA
       	 */
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
       	/**
       	 * 如果指定的初始为负数，抛出异常
       	 */
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }

• 如果传入的指定初始容量大于零，那就创建一个指定初始容量大小的数组用来存放数据
• 如果指定的初始等于零，则使用静态全局变量中的空数组EMPTY_ELEMENTDATA
• 如果指定的初始为负数，抛出异常

无指定初始容量

 /**
 * 	当无指定初始容量参数时，使用默认容量，构造一个初始容量为10的空列表。
 * 	但是其实在初始化后，此时的数组容量为0，当第一次存入数据时，才对这个空数组进行扩容，变为长度为10的数组
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

传入集合初始化

/**
 *	构造包含指定集合的元素的列表，按集合的迭代器返回元素的顺序排列。
 *
 * @param c 要将其元素放入此列表的集合
 * @throws NullPointerException 如果指定的集合为空
 */
public ArrayList(Collection<? extends E> c) {
	/**
	 * 把传入的集合转化为数组
	 */
    elementData = c.toArray();
    /**
     * 判断传入的集合是否为空，如果为空则初始化为EMPTY_ELEMENTDATA数组，也就是等于指定初始容量为0时的情况
     */
    if ((size = elementData.length) != 0) {
        // 为了防止传入集合转型后的数组的类型不是Object类型，所以在这里进行验证
        // 如果不是Object类型，则使用Arrays.copyOf()的方法重新拷贝成Object[].class类型
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 用空数组替换。
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

核心方法

trimToSize 方法

/**
 * 修改此ArrayList实例的容量成为列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。 
 */
public void trimToSize() {
	/**
	 * 因为是对结构进行了修改，所以modCount加一次
	 */
    modCount++;
    /**
     * 如果当前数组中的元素数量小于数组长度，就对数组进行修改
     */
    if (size < elementData.length) {
    	/**
    	 * 如果数组中的元素数量为0，则把数组变为EMPTY_ELEMENTDATA
    	 * 如果数组中的元素数量不为0，则把当前数组中的所有元素拷贝到一个新的数组，数组长度为元素的数量
    	 */
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

该方法用于回收多余的内存。也就是说一旦我们确定集合不在添加多余的元素之后，调用 trimToSize() 方法会将实现集合的数组大小刚好调整为集合元素的大小。
注意：该方法会花时间来复制数组元素，所以应该在确定不会添加元素之后在调用。

ensureCapacity 方法

/**
 * 如果需要，增加此 ArrayList实例的容量，以确保它至少能够容纳最小容量参数指定的元素数。 
 *
 * @param minCapacity 所需的最小容量 
 */
public void ensureCapacity(int minCapacity) {
	/**
	 * 先判断是否满足增加容量的条件：
	 * 1.新的容量大于当前数组的长度，不然没有必要扩容
	 * 2.数组中有数据，或者数组中没有数据并且新的容量大于默认的容量长度
	 * 满足上面的两个条件后，modCount加一，然后调用grow方法进行数组的扩容和复制
	 */
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

grow 方法

/**
 * 增加容量，以确保它至少可以容纳由最小容量参数指定的元素数目。
 *
 * @param minCapacity 所需的最小容量
 * @throws OutOfMemoryError 如果minCapacity小于零
 */
private Object[] grow(int minCapacity) {
	/**
	 * 使用newCapacity方法获得新的合适的容量大小，因为minCapacity不一定时最合适的扩容容量
	 */
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

newCapacity 方法

/**
 * 返回至少与给定的最小容量相同大的容量。返回当前容量增加50%(如果足够的话)。
 * 除非给定的最小容量大于MAX_ARRAY_SIZE，否则不会返回大于MAX_ARRAY_SIZE的容量。
 * 
 * @param minCapacity 所需的最小容量
 * @throws OutOfMemoryError 如果minCapacity小于零
 */
private int newCapacity(int minCapacity) {
    /**
     * 旧的容量是现在数组的长度
     * 默认的新的容量是旧容量的1.5倍
     */
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    /**
     * 如果传入的要求的最小容量（newCapacity）大于等于默认的新的容量，就进入if做边界条件的判断
     */
    if (newCapacity - minCapacity <= 0) {
    	/**
    	 * 如果当前数组是空数组，这种情况下就是数组进行了初始化，但是没有放入任何数据，还是一个空数组，所以上面得到的oldCapacity和newCapacity都是0
    	 * 那么就取要求的最小容量和默认容量（16）二者中较大的那个进行扩容。
    	 */
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        /**
    	 * 因为上面的if判断的是 <= 的情况，所以有可能传入的 minCapacity是负数
    	 */
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        /**
         * 边界没有溢出的话，就扩大为minCapacity
         */
        return minCapacity;
    }
    /**
     * 如果传入的要求的最小容量（newCapacity）小于默认的新的容量，就不使用传入的minCapacity
     * 如果默认的新的容量小于数组最大容量Integer.MAX_VALUE-8，那么就使用它，也就是数组扩容1.5倍
     * 但是如果大于数组最大容量Integer.MAX_VALUE-8，就尝试使用minCapacity，进入hugeCapacity函数判断
     */
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 溢出
        throw new OutOfMemoryError();
    /**
     * 如果newCapacity大于数组最大容量Integer.MAX_VALUE-8，但是minCapacity没有，就使用Integer.MAX_VALUE-8
     * 但是如果newCapacity和minCapacity都大于了Integer.MAX_VALUE-8的话，就把数组扩容为Integer.MAX_VALUE
     */
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

总结来说，对于数组容量扩容过程如下：

1. 先确定三个变量：传入的所需的最小容量（minCapacity），旧容量（oldCapacity）也就是当前现在数组的长度，默认的新的容量（newCapacity）是旧容量的1.5倍。
2. 对比minCapacity和newCapacity，如果对比minCapacity大于等于（>=）newCapacity,那么进入3，否则进入5。
3. 如果elementData是只进行初始化，但是还没有存入数据的数组，那么它的长度肯定是0，所以这种情况下上面得到的oldCapacity和newCapacity是0，因此取默认初始容量（16）和minCapacity中的较大值，作为扩容后的容量。否则进入4。
4. 判断如果传入的minCapacity是负数，那么抛出异常。否则将其作为扩容后的容量。
5. 如果newCapacity小于等于MAX_ARRAY_SIZE（Integer.MAX_VALUE-8），那么newCapacity就是扩容大小，也就是扩容1.5倍。否则进行6。
6. 如果newCapacity大于minCapacity，但是minCapacity其实是负数，那么直接抛出异常。否则再次判断minCapacity与MAX_ARRAY_SIZE的大小关系，如果minCapacity也大于MAX_ARRAY_SIZE，那么newCapacity和minCapacity都大于了MAX_ARRAY_SIZE，就把数组扩容为Integer.MAX_VALUE。否则进行7。
7. 否则就只有newCapacity大于MAX_ARRAY_SIZE，而minCapacity小于等于MAX_ARRAY_SIZE，则数组扩容为MAX_ARRAY_SIZE。

size 方法

/**
 * 以常数时间返回此列表中的元素数量。
 *
 * @return 列表中元素的数量
 */
public int size() {
    return size;
}

isEmpty 方法

/**
 * 如果此列表不包含任何元素，则返回true。
 *
 * @return {@code true} 如果此列表不包含任何元素
 */
public boolean isEmpty() {
    return size == 0;
}

contains 方法

/**
 * 如果此列表包含指定的元素，则返回true 。
 * 更正式地说，返回true当且仅当此列表包含至少一个元素e这样Objects.equals(o, e) 。
 *
 * @param o 其在此列表中的存在性将被测试
 * @return {@code true} 如果此列表包含指定的元素
 */
public boolean contains(Object o) {
	/**
	 * 实则调用了indexOf方法得到其下标，只需判断得到的下标是否小于零即可
	 */
    return indexOf(o) >= 0;
}

indexOf 于 lastIndexOf 方法

/**
 * 以常数时间返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。
 * 更正式地，返回最低下标i ，使得Objects.equals(o, get(i)) ，如果没有这样的下标则返回-1。 
 */
public int indexOf(Object o) {
	/**
	 * 如果要寻找的对象是null，那么就遍历数组，找第一个null的下标
	 */
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
    	/**
    	 * 如果要寻找的对象非null，那么就遍历数组，找第一个为o的元素的下标
    	 */
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    /**
     * 如果找不到的话，就返回-1
     */
    return -1;
}

/**
 * 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。
 * 更正式地说，返回满足i这样Objects.equals(o, get(i)) ，如果没有这样的索引则返回-1。 
 * 搜索方法与indexOf相似，同为遍历整个数组，区别就是该方法从后向前寻找。
 */
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;
}

该方法需要遍历整个数组，寻找对应的元素的下标，所以时间复杂度为O(N)。

clone​ 方法

/**
 * 返回此ArrayList实例的浅拷贝。（元素本身不被复制。） 
 *
 * @return 这个 ArrayList实例的克隆 
 */
public Object clone() {
    try {
    	/**
    	 * 调用AbstractList的clone方法得到一个ArrayList
    	 * 然后给这个v的elementData数组复制为当前数组，同时modCount重置为0
    	 * 返回这个ArrayList。
    	 */
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        /**
         * 这不应该发生，因为我们是可克隆的
         */
        throw new InternalError(e);
    }
}

该方法只返回此ArrayList实例的浅拷贝，元素本身不被复制。

toArray 方法

/**
 * 以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。 
 * 返回的数组将是“安全的”，因为该列表不保留对它的引用。 （换句话说，这个方法必须分配一个新的数组）。
 * 因此，调用者可以自由地修改返回的数组。 
 * 
 * 此方法充当基于阵列和基于集合的API之间的桥梁。 
 *
 * @return 一个包含该列表中所有元素的数组
 */
public Object[] toArray() {
	/**
	 * 使用Arrays的copyOf拷贝elementData，得到并且返回一个新的数组。
	 */
    return Arrays.copyOf(elementData, size);
}

/**
 * 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。 
 * 如果列表适合指定的数组，则返回其中。 否则，将为指定数组的运行时类型和此列表的大小分配一个新数
 * 如果列表符合指定的数组，则有剩余空间（即数组的列表数量较多），则紧跟在集合结束后的数组中的元素设置为null 。 
 * （这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。） 
 *
 * @param a 要存储列表的元素的数组，如果它足够大; 否则，为此目的分配相同运行时类型的新数组。 
 * 
 * @return 包含列表元素的数组
 * @throws ArrayStoreException 如果指定数组的运行时类型不是此列表中每个元素的运行时类型的超类型 
 * 
 * @throws NullPointerException 如果指定的数组为空
 */
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        /**
         * 如果传入的数组的长度小于当前的元素数量，则创建一个新的数组a的运行时类型的数组，把elementData数组中的元素复制到该数组中。
         */
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    /**
     * 否则直接把elementData数组中的元素复制到该数组中。
     */
    System.arraycopy(elementData, 0, a, 0, size);
    /**
     * 如果传入数组长度大于元素数量，那么就把最后一个元素的后面的元素设置为null。
     */
    if (a.length > size)
        a[size] = null;
    return a;
}

toArray 方法主要有两种方式，一种是无参方法，直接返回包含此列表中所有元素的数组；另一种是传入一个数组，然后把此列表中所有元素复制到该数组中，然后返回该数组。

get 方法

/**
 * 因为底层是数组，所以以常数时间返回此列表中指定位置的元素。 
 *
 * @param  index 要返回的元素的索下标
 * @return 该列表中指定位置的元素 
 * @throws IndexOutOfBoundsException  如果下标超出范围（ index < 0 || index >= size() ） 
 */
public E get(int index) {
	/**
	 * Objects.checkIndex方法调用了Preconditions.checkIndex(index, length, null)检查下标是否超出范围
	 * Preconditions.checkIndex() 方法判断如果index < 0 || index >= size()，就抛出异常，否则返回传出的index。
	 */
    Objects.checkIndex(index, size);
    /**
     * 如果下标满足要求，返回elementData数组中对应下标处的元素。
     */
    return elementData(index);
}

set 方法

/**
 * 用指定的元素替换此列表中指定位置的元素。 
 *
 * @param index 要替换的元素的下标
 * @param element 要存储在指定位置的元素 
 * @return 该元素以前在指定的位置 
 * @throws IndexOutOfBoundsException  如果索引超出范围（ index < 0 || index >= size() ） 
 */
public E set(int index, E element) {
	/**
	 * 同get方法一样，先判断下表是否越界，如果越阶就抛出异常。
	 */
    Objects.checkIndex(index, size);
    /**
     * 记录下elementData数组中指定位置处的旧元素，用于返回。
     * 将elementData数组中指定位置处的元素设置为传入的元素，然后返回旧的元素
     */
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

add 方法

将指定的元素追加到此列表的末尾

/**
 * 以常数时间，将指定的元素追加到此列表的末尾。 
 *
 * @param e 要附加到此列表的元素 
 * @return {@code true} (由 Collection.add(E)指定)
 */
public boolean add(E e) {
	/**
	 * 因为往数组中添加元素，所以结构发生了改变，因此modCount加一
	 * 调用内部的add方法添加元素，add方法见下面。
	 */
    modCount++;
    add(e, elementData, size);
    return true;
}

内部的add方法添加元素

/**
 * 这个helper方法从add(E)中分离出来，以将方法字节码大小保持在35以下(-XX:MaxInlineSize默认值)，这有助于在c1编译的循环中调用add(E)。
 * 
 */
private void add(E e, Object[] elementData, int s) {
	/**
	 * 先判断数组中的元素数量是否达到了数组长度
	 * 如果达到，则对数组进行扩容，扩容大小是原数组长度的1.5倍
	 */
    if (s == elementData.length)
        elementData = grow();
    /**
     * 然后将传入的元素添加到数组尾部，元素数量加一
     */
    elementData[s] = e;
    size = s + 1;
}

在指定位置插入指定的元素

/**
 * 以O(N)的时间，在此列表中的指定位置插入指定的元素。 
 * 将当前位于该位置的元素（如果有）和任何后续元素（向其索引添加一个）移动。 
 *
 * @param index  要在其中插入指定元素的下标 
 * @param element 要插入的元素 
 * @throws IndexOutOfBoundsException  如果索引超出范围（ index < 0 || index > size() ） 
 */
public void add(int index, E element) {
	/**
	 * rangeCheckForAdd方法见下面；
	 * 同样把数组修改次数加一；
	 */
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    /**
     * 如果数组中的元素数量是否达到了数组长度，对数组进行扩容，扩容大小是原数组长度的1.5倍
     */
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    /**
     * 然后将该index位置的元素和它后面的所有元素后移一位
     * 把index的位置空出来，然后将其赋值为传入的元素
     * 元素数量加一。
     */
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}


/**
 * 由add和addAll使用的rangeCheck的一个版本。同为对下标范围的判断，本质与之前的checkIndex方法没什么区别。
 * 只是自己自定义了抛出异常的语句而已
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

总结来说，如果在指定位置插入指定的元素，因为要移动指定位置后面的所有元素，那么O(N)的时间；如果将指定的元素追加到此列表的末尾，那么仅花费常数的时间，但是如果数组需要扩容的话，将花费时间对数组进行扩容，所以尽量在初始化该List时就指定好容量大小。

remove 方法

删除指定位置的元素

/**
 * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。  
 *
 * @param index 要删除的元素的下标
 * @return 从列表中删除的元素 
 * @throws IndexOutOfBoundsException 如果索引超出范围（ index < 0 || index >= size() ） 
 */
public E remove(int index) {
	/**
	 * 依旧先对下标范围进行检查
	 */
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    /**
     * 把旧的元素暂存下来，调用fastRemove方法把指定位置的元素删除，等删除后返回。
     */
    @SuppressWarnings("unchecked")
    E oldValue = (E) es[index];
    /**
     * fastRemove方法见下面
     */
    fastRemove(es, index);
    return oldValue;
}

删除第一个出现的指定元素

/**
 * 从列表中删除第一个出现的指定元素（如果存在）。 
 * 如果列表不包含该元素，则它不会更改。
 * 更正式地，删除具有最低索引i的元素，使得Objects.equals(o, get(i)) （如果这样的元素存在）。
 *  如果此列表包含指定的元素（或等效地，如果此列表作为调用的结果而更改），则返回true 。 
 * 
 * @param o 要从此列表中删除的元素（如果存在） 
 * @return {@code true} 如果此列表包含指定的元素
 */
public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
    	/**
    	 * 遍历整个数组，查找指定元素o的下标，如果数组中不存在该元素，就直接返回false
    	 */
        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方法进行删除。
     */
    fastRemove(es, i);
    return true;
}

fastRemove 方法

/**
 * 私有的remove方法，该方法跳过边界检查，并且不返回已删除的值。
 */
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);
    /**
     * 然后将最后那个空出来的元素变赋值为null，同时size减小1
     */
    es[size = newSize] = null;
}

clear 方法

/**
 * 从列表中删除所有元素。 此呼叫返回后，列表将为空。 
 */
public void clear() {
	/**
	 * 数组修改次数加一
	 */
    modCount++;
    final Object[] es = elementData;
    /**
     * 遍历整个数组，把所有下标置为null，同时size设置为0
     */
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

addAll 方法

将指定集合中的所有元素追加到列表的末尾

/**
 * 按指定集合的Iterator返回的顺序	。
 * 如果在操作进行中修改了指定的集合，则此操作的行为是不确定的。（这意味着如果指定的集合是此列表，则此调用的行为是不确定的，并且此列表是非空的。） 
 *
 * @param c 包含要添加到此列表的元素的集合 
 * @return {@code true} 如果此列表因调用而更改 
 * @throws NullPointerException  如果指定的集合为空 
 */
public boolean addAll(Collection<? extends E> c) {
	/**
	 * 把传入的集合转化为数组，方便进行拷贝，同时修改次数加一
	 */
    Object[] a = c.toArray();
    modCount++;
    /**
     * 如果传入的集合中没有元素，那么此列表没有更改，因此返回false 
     */
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData;
    final int s;
    /**
     * elementData.length- size 得到数组剩余的空闲空间，
     * 如果传入的集合长度numNew大于数组剩余的空闲空间，因此当前数组放不下传入的元素，所以要对数组进行扩容
     * 扩容的后的大小最小值为：当前元素数量加将要添加的元素数量
     */
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    /**
     * 将传入的集合元素数组拷贝到列表数组的后面
     */
    System.arraycopy(a, 0, elementData, s, numNew);
    /**
     * 元素数量加上传入的元素数量
     */
    size = s + numNew;
    return true;
}

从指定的位置开始，将指定集合中的所有元素插入到此列表中。

/**
    * 将指定集合中的所有元素插入到此列表中，从指定的位置开始。
    * 将当前位于该位置（如果有的话）的元素和随后的任何元素移动到右边（增加其索引）。
    * 新元素将按照指定集合的迭代器返回的顺序显示在列表中。 
    *
    * @param index 从中指定集合插入第一个元素的索引 
    * @param c 包含要添加到此列表的元素的集合 
    * @return {@code true} 如果此列表因呼叫而更改
    * @throws IndexOutOfBoundsException 如果索引超出范围（ index < 0 || index > size() ）
    * @throws NullPointerException 如果指定的集合为空 
    */
   public boolean addAll(int index, Collection<? extends E> c) {
   	/**
   	 * 使用自定义的方法对下标是否越界进行检查
   	 */
       rangeCheckForAdd(index);
       /**
        * 将传入的集合转化为数组，方便拷贝
        * 同时修改次数加一
        */
       Object[] a = c.toArray();
       modCount++;
       /**
        * 如果传入的集合中没有元素，那么此列表没有更改，因此返回false 
        */
       int numNew = a.length;
       if (numNew == 0)
           return false;
       Object[] elementData;
       final int s;
       /**
        * elementData.length- size 得到数组剩余的空闲空间，
        * 如果传入的集合长度numNew大于数组剩余的空闲空间，因此当前数组放不下传入的元素，所以要对数组进行扩容
        * 扩容的后的大小最小值为：当前元素数量加将要添加的元素数量
        */
       if (numNew > (elementData = this.elementData).length - (s = size))
           elementData = grow(s + numNew);
       /**
        * s - index 计算得到需要向右移动的元素的长度
        * 然后将其向右移动该长度
        */
       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;
   }

removeAll 与 retainAll 方法

removeAll 方法

/**
 * 从此列表中删除指定集合中包含的所有元素。
 *
 * @param c 包含要从此列表中删除的元素的集合 
 * @return {@code true} 如果此列表因调用而更改
 * @throws ClassCastException 如果此列表的元素的类与指定的集合不兼容（ 可选 ） 
 * @throws NullPointerException 如果此列表包含空元素，并且指定的集合不允许空元素（ 可选 ），或者如果指定的集合为空
 */
public boolean removeAll(Collection<?> c) {
	/**
	 * batchRemove 方法见下面
	 */
    return batchRemove(c, false, 0, size);
}

retainAll 方法

/**
 * 仅保留此列表中包含在指定集合中的元素。 
 * 换句话说，从此列表中删除其中不包含在指定集合中的所有元素。
 * 本质就是求交集。
 *
 * @param c 包含要保留在此列表中的元素的集合
 * @return {@code true} 如果此列表因调用而更改
 * @throws ClassCastException 如果此列表的元素的类与指定的集合不兼容（ 可选 ） 
 * @throws NullPointerException 如果此列表包含空元素，并且指定的集合不允许空元素（ 可选 ），或者如果指定的集合为空
 */
public boolean retainAll(Collection<?> c) {
    return batchRemove(c, true, 0, size);
}

batchRemove 方法

/**
 * 对比removeAll和retainAll方法，同样都是调用了batchRemove方法，唯一的区别就是传入的complement参数
 * removeAll的参数是false，而retainAll方法传入的是true，所导致的结果则截然不同，所以这个complement是决定结果的关键
 */
private boolean batchRemove(Collection<?> c, boolean complement,
           final int from, final int end) {
	/**
	 * 该方法判断传入的集合c是否为null，如果是null则抛出异常，代码见下方
	 */
	Objects.requireNonNull(c);
	final Object[] es = elementData;
	int r;
	/**
	 * 从头开始遍历数组，它的作用就是找到数组中第一个在集合c包含或者不包含的元素的位置，具体看下面
	 */
	for (r = from;; r++) {
		/**
		 * 如果r走到了最后依旧没找到任何一个集合c中包含或者不包含的元素
		 * 那么数组将不会发生任何变化，返回false
		 */
		if (r == end)
			return false;
		/**
		 * 如果complement是false，那么在找到数组中第一个存在于集合c中的元素时，结束循环
		 * 如果complement是true，那么在找到数组中第一个不存在于集合c中的元素时，结束循环
		 */
		if (c.contains(es[r]) != complement)
			break;
	}
	/**
	 * 看到w和r，顾名思义，w是write，r是read，也就是写和读，具体作用看下面就知道了
	 * 这里把r赋给了w，r加一
	 */
	int w = r++;
	try {
		for (Object e; r < end; r++)
			/**
			 * 从上一次循环中，扎到数组中第一个存在/不存在于集合c中的元素的下标开始遍历
			 * 
			 * 如果complement是false，那么在找到数组中一个不存在于集合c中的元素时，把他覆盖到刚刚找到的第一个存在于集合c中的元素的位置处
			 * 这里可能难以理解一点，可以这样想：
			 * 因为complement是false的情况是删除重复的元素嘛，所以用数组后面不重复的元素覆盖前面的元素，以此代替了删除。
			 * 
			 * 同样如果complement是true，那么在找到数组中一个存在于集合c中的元素时，把他覆盖到刚刚找到的第一个不存在于集合c中的元素的位置处
			 */
			if (c.contains(e = es[r]) == complement)
				es[w++] = e;
	} catch (Throwable ex) {
		/**
		 * 即使c.contains()抛出异常，也可以保持与AbstractCollection的兼容性
		 * 将已经覆盖的元素后面重复出来的元素删除掉
		 */
		System.arraycopy(es, r, es, w, end - r);
		w += end - r;
		throw ex;
	} finally {
		/**
		 * 修改此处对应增加改变的数量
		 */
		modCount += end - w;
		shiftTailOverGap(es, w, end);
	}
	return true;
}

   public static <T> T requireNonNull(T obj) {
       if (obj == null)
           throw new NullPointerException();
       return obj;
   }
   
   /**通过以下元素向下滑动，消除从lo到hi的间隔。 */
   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;
   }

这里总结一下removeAll，retainAll和addAll方法之间的关系吧：

• removeAll 方法就是把存在于指定的集合中的元素全部删除掉，也就是求补集。
• retainAll 方法就是把不存在于指定的集合中的元素全部删除掉，也就是求交集。
• addAll 方法就把不存在于指定的集合中的元素全部添加到列表中，也就是求并集。

subList 方法

/**
 * 返回指定的fromIndex （含）和toIndex之间的列表部分的视图。 （如果fromIndex和toIndex相等，返回的列表为空。）
 * 返回的列表由此列表支持，因此返回列表中的非结构更改将反映在此列表中，反之亦然。 返回的列表支持所有可选列表操作。 
 * 该方法消除了对显式范围操作（对于数组通常存在的排序）的需要。 
 * 任何期望列表的操作都可以通过传递一个子列表视图而不是整个列表来用作范围操作。 例如，以下成语从列表中移除了一系列元素： list.subList(from, to).clear();
 * 可以为indexOf(Object)和lastIndexOf(Object)构造类似的成语，并且可以将Collections类中的所有算法应用于子列表。 
 * 如果支持列表（即，此列表）以除了通过返回的列表之外的任何方式进行结构修改 ，则此方法返回的列表的语义将变为不正确。 
 * （结构修改是那些改变此列表的大小，或以其他方式扰乱它，使得正在进行的迭代可能产生不正确的结果）。
 * 
 * 简单的来说，就是返回整个列表中，指定范围那部分的列表的视图。
 * 但是！！如果对返回的这部分列表进行修改，那么同时原列表的对应位置也会发生修改
 * 所以本质就是返回了一部分引用而已。
 *
 * @throws IndexOutOfBoundsException 如果端点索引值超出范围 (fromIndex < 0 || toIndex > size) 
 * @throws IllegalArgumentException 如果端点索引不正确 (fromIndex > toIndex) 
 */
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList<>(this, fromIndex, toIndex);
}

所以总结来说，尽量不要使用subList方法，如果要使用的话，一定要注意下面几点使用方法：

1. 千万不要再对原 List 进行任何改动的操作(例如: 增删改), 查询和遍历倒是可以. 因为如果对原 List 进行了改动, 那么后续只要是涉及到子 List 的操作就一定会出问题. 而至于会出现什么问题呢? 具体来说就是:
   (1) 如果是对原 List 进行修改 (即: 调用 set() 方法) 而不是增删, 那么子 List 的元素也可能会被修改 (这种情况下不会抛出并发修改异常).
   (2) 如果是对原 List 进行增删, 那么此后只要操作了子 List , 就一定会抛出并发修改异常.
2. 千万不要直接对子 List 进行任何改动的操作(例如: 增删改), 但是查询和间接改动倒是可以. 不要对子 List 进行直接改动, 是因为如果在对子 List 进行直接改动之前, 原 List 已经被改动过, 那么此后在对子 List 进行直接改动的时候就会抛出并发修改异常.
3. 如果要进行操作，则使用例如：List subList = new ArrayList<>(list.subList(2, list.size())); 的方法，把分割出来的数组转化为一个新的列表，在新的列表基础上操作就不会对原列表产生任何影响。

补充

考虑一点：elementData设置成了transient，那ArrayList是怎么把元素序列化的呢？

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // 防止序列化期间有修改
    int expectedModCount = modCount;
    // 写出非transient非static属性（会写出size属性）
    s.defaultWriteObject();

    // 写出元素个数
    s.writeInt(size);

    // 依次写出元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    // 如果有修改，抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
    // 声明为空数组
    elementData = EMPTY_ELEMENTDATA;

    // 读入非transient非static属性（会读取size属性）
    s.defaultReadObject();

    // 读入元素个数，没什么用，只是因为写出的时候写了size属性，读的时候也要按顺序来读
    s.readInt();

    if (size > 0) {
        // 计算容量
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        // 检查是否需要扩容
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // 依次读取元素到数组中
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

查看writeObject()方法可知，先调用s.defaultWriteObject()方法，再把size写入到流中，再把元素一个一个的写入到流中。

一般地，只要实现了Serializable接口即可自动序列化，writeObject()和readObject()是为了自己控制序列化的方式，这两个方法必须声明为private，在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。

在ArrayList的writeObject()方法中先调用了s.defaultWriteObject()方法，这个方法是写入非static非transient的属性，在ArrayList中也就是size属性。同样地，在readObject()方法中先调用了s.defaultReadObject()方法解析出了size属性。

elementData定义为transient的优势，自己根据size序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。

总结

1. ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
2. ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
3. ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
4. ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
5. ArrayList从尾部删除元素极快，时间复杂度为O(1)；
6. ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；
7. ArrayList支持求并集，调用addAll(Collection<? extends E> c)方法即可；
8. ArrayList支持求交集，调用retainAll(Collection<? extends E> c)方法即可；
9. ArrayList支持求单向差集，调用removeAll(Collection<? extends E> c)方法即可；