ArrayList 源码精读笔记

ArrayList 类属性

ArrayList 实现了 RandomAccess 接口，RandomAccess 接口没有内容只是一个标记，对于实现了 RandomAccess 接口的类支持通过索引/下标访问。

对于实现了 RandomAccess 接口的类使用 for 循环遍历效率高，没有实现的类尽量使用迭代器遍历

package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import sun.misc.SharedSecrets;

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)
 *
 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.
 *
 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.
 *
 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 *
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 *
 * <p><a name="fail-fast">
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
 * if the list is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2
 */

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{ // 实现了 RandomAccess 接口支持随机访问，实现了 Cloneable 接口，是浅克隆的，实现了序列化接口 Serializable
    // 每次用于网络传输的类都需要生成了随机序列化，是书写规范，如果不写其实也会自动加上
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10; // 默认容量

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {}; // 初始化空数组

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 和 EMPTY_ELEMENTDATA 做区分

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    // 真正存放数据的数组，transient 防止进行序列化，既然元素不支持序列化，那么类上为什么又实现了 Serilizable 接口呢
    // 这里是自己重写了序列化方法，节省了 50% 序列化的空间
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    // ArrayList 中包含的元素个数
    private int size;

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    // 带初始容量的构造器
    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    // 空参构造期
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // ...
    
    
}

add(E e) 以及扩容机制

当我们初始化一个容量为 0 的 ArrayList 的容量 ArrayList<Object> list = new ArrayList<>(0);

如果往集合中添加 10 个元素，则会扩容 7 次。这样做的效率非常低

所以如果我们知道需要多大的容量，则尽量在初始化的时候指定具体的容量，否则可以使用默认构造器，避免使用 0 参数。

List<Object> list = new ArrayList<>(0);
list.add("a"); // 第 1 次 add
list.add("b"); list.add("c"); list.add("d"); list.add("e"); 
list.add("f"); list.add("g"); list.add("h");list.add("i");
list.add("j"); // 第 10 次 add

下面时执行流程：

执行带参数构造器，创建 ArrayList 对象

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) { // 如果初始容量大于 0，则直接创建一个 initialCapacity 的 Object 数组赋值给 elementData
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { // 如果初始容量为 0 走这里，将 EMPTY_ELEMENTDATA 赋值给 elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

首先执行第一步 add(E e)

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    // 1. 确保内部容量
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 添加元素到 elementData 中，同时 size + 1
    elementData[size++] = e;
    return true;
}

确保内部容量

private void ensureCapacityInternal(int minCapacity) {
    // 1. 先计算容量大小 calculateCapacity(elementData, minCapacity)
    // 2. 确保具体容量
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判断 elementData 是不是 默认容量空数组（和空数组 EMPTY_ELEMENTDATA 做区分）
        return Math.max(DEFAULT_CAPACITY, minCapacity); // 是的话，返回当前容量为 默认容量 和 用户自己传入的最小容量 的最大值
    }
    return minCapacity; // 走这里，否则返回 用户自己传入的最小容量
}

确保具体容量

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 首先并发修改数 + 1，定义在 AbstractList 中，protected transient int modCount = 0; 用于是否出现了判断修改

    // overflow-conscious code
    // 如果我们传入的最小容量 - elementData 数组长度 > 0，则进行扩容
    if (minCapacity - elementData.length > 0)
        // 扩容方法
        grow(minCapacity);
}

扩容

	/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    // 旧容量
    int oldCapacity = elementData.length;
    // 新容量，扩容为旧容量的 近似 1.5 倍【注意】
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 扩容之后的新容量还是 小于 我们传入的最小容量，那把 minCapacity 作为我们的新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果 新容量 大于 最小数组大小（int 最大值 - 8），那么执行 hugeCapacity(minCapacity); 扩容为 int 最大值
    if (newCapacity - MAX_ARRAY_SIZE > 0) // Integer.MAX_VALUE - 8;
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 开辟新数组，并将原数组的内容拷贝到新数组中，最后再赋值给 elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}

最大化扩容

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果我们传入的最小容量 大于 最大数组大小，就扩容为 int 最大值
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

当我们使用空参构造器时，ArrayList<Object> list = new ArrayList<>();

List<Object> list = new ArrayList<>();
list.add("a"); // 第 1 次 add
list.add("b"); list.add("c"); list.add("d"); list.add("e"); 
list.add("f"); list.add("g"); list.add("h");list.add("i");
list.add("j"); // 第 10 次 add

执行空参构造器，创建 ArrayList 对象

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData
}

执行第一步 add(E e)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

确保内部容量

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 走这里
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判断 elementData 是不是 默认容量空数组（和空数组 EMPTY_ELEMENTDATA 做区分）
        return Math.max(DEFAULT_CAPACITY, minCapacity); // 是的话，返回当前容量为 默认容量 和 用户自己传入的最小容量 0 + 1 的最大值，那么就是 10
    }
    return minCapacity; // 否则返回 用户自己传入的最小容量
}

确保具体容量
然后执行一次扩容，扩容为 10，可以容量 10 个数，所以只会进行一次扩容

关于创建 ArrayList 的几种方式常见问题

第一种：new 对象，调用 ArrayList 的构造器，这个没啥说法

第二种：调用 Arrays 工具类的 asList() 方法，可以初始化一个 List

1 2	List<String> list2 = Arrays.asList("a", "b", "c"); // 创建方式没有问题 list2.add("d"); // 但是不能调用 add() 方法，为什么？

为什么通过 Arrays 创建的 List 不能调用 add 方法呢？同时 remove() 方法也不能调用。

下面看源码：

asList() 方法

1
2
3

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

ArrayList 的构造器

/**
 * @serial include
 */
private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable
{
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }
    
    // ...
    
}

发现调用的是 Arrays 类自己创建的内部类 ArrayList 的构造器，而这个 ArrayList 中并没有重写 add() 方法，虽然它继承了 AbstractList 抽象类，但是 AbstractList 中的抽象类的 add() 方法的默认实现是直接抛异常，同理 remove() 方法也没有重写，继承抽奖类的也是直接抛异常，而 get()、set() 获取和修改可以使用，原因就是重写了对应方法。

public boolean add(E e) {
    add(size(), e);
    return true;
}

public void add(int index, E element) {
    // 添加直接抛异常
    throw new UnsupportedOperationException();
}

public E remove(int index) {
    // 删除直接抛异常
    throw new UnsupportedOperationException();
}

那什么时候会用这种方式创建 List 呢？

当我们使用固定大小的 List 且不做增加和删除，只做修改的时候可以使用这种方式。

第三种：调用 Collections 工具类的 emptyList() 方法，初始化一个空的 List【基本不用】

1 2	ArrayList<String> list = Collections.emptyList(); // 创建一个 EmptyList，空的 List list.add("a"); // 不能调用 add() 方法

不能调用 add() 的原因和第二种方式的原因时类似的

看源码：

emptyList() 方法，直接返回一个 EMPTY_LIST

public static final <T> List<T> emptyList() {
    return (List<T>) EMPTY_LIST;
}

public static final List EMPTY_LIST = new EmptyList<>();

再看 EmptyList 类

/**
  * @serial include
  */
private static class EmptyList<E>
    extends AbstractList<E>
    implements RandomAccess, Serializable {
    private static final long serialVersionUID = 8842843931221139166L;

    public Iterator<E> iterator() {
        return emptyIterator();
    }
    public ListIterator<E> listIterator() {
        return emptyListIterator();
    }

    public int size() {return 0;}
    public boolean isEmpty() {return true;}

    // ...

}

它也是一个内部类，同样的继承了 AbstractList，但是没有重写 add()、set()、remove()，所以无法添加元素，什么都不能干，还真就是一个空的 List，没什么用。

使用场景？

当我们代码中要返回空 List 的时候才会用到，public static final List EMPTY_LIST = new EmptyList<>(); 在 javac 编译成 class 文件的时候就已经初始化了，比 new ArrayList() 每次返回空 List 要好，因为不需要重新创建对象。

trimToSize()

剪切 ArrayList 让它的容量变成 size，将没有元素的位置删掉，底层还是 Arrays.copy()

/**
     * Trims the capacity of this <tt>ArrayList</tt> instance to be the
     * list's current size.  An application can use this operation to minimize
     * the storage of an <tt>ArrayList</tt> instance.
     */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

contains(Object o)、indexOf(int index)、lastIndexOf(int index)

contains(Object o) 源码

/**
     * Returns <tt>true</tt> if this list contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this list contains
     * at least one element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return <tt>true</tt> if this list contains the specified element
     */
public boolean contains(Object o) {
    return indexOf(o) >= 0; // 这里调用 indexOf(o)，判断返回索引是否 大于等于 0，如果是则包含，否则不包含
}

indexOf(int index) 源码

/**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
public int indexOf(Object o) {
    if (o == null) { // 如果是空，遍历等于空的位置，找到第一个返回
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else { // 如果不是空，同样是 for 循环遍历，找到第一个返回
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1; // 找不到返回 -1
}

lastIndexOf(int index) 源码

/**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
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;
}

clone()

ArrayList 的克隆方法，用的是父类 Object 的 clone() 方法，所以是浅拷贝，只拷贝值，不创建对象。

/**
     * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this <tt>ArrayList</tt> instance
     */
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone(); // 调用父类 clone()
        v.elementData = Arrays.copyOf(elementData, size); // Arrays.copy 拷贝
        v.modCount = 0; // 克隆之后认为是一个新的 ArrayList，没有被修改过
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

toArray()

/**
     * Returns an array containing all of the elements in this list
     * in proper sequence (from first to last element).
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this list in
     *         proper sequence
     */
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

// 泛型实现 T 是类型，E 是元素，U 是
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
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

Arrays.copy()

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

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    // 真正执行 copy 的是这句话，System.arraycopy
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

// native 实现，底层可能是 C++ 写的
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

get(index)

对通过下标取数组元素做的一个封装 elementData(index)

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index]; // 底层还是数组访问
}

get(index)

/**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
public E get(int index) {
    rangeCheck(index); // 索引范围检查，不合法抛出下标越界异常

    return elementData(index); // 返回索引对应的值
}

/**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
private void rangeCheck(int index) {
    if (index >= size) // 索引不合法抛出 IndexOutOfBoundsException 异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

set(index)

/**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
public E set(int index, E element) {
    rangeCheck(index); // 索引范围检查

    E oldValue = elementData(index); // 先获取旧值
    elementData[index] = element; // 再赋新值
    return oldValue; // 返回旧值
}

add(index, E) 插入

每插入一次都会触发一次 arraycopy 数组移动，O(n) 的复杂度，比较耗费性能。

/**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
public void add(int index, E element) {
    rangeCheckForAdd(index); // 插入索引范围检查

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index); // [index, size) 往后移动一位
    elementData[index] = element; // 插入到 index 位置上
    size++; // 容量 + 1
}

/**
     * A version of rangeCheck used by add and addAll.
     */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) // 插入索引范围检查，这里有一个优化的地方：把常用的判断条件放前边，提高性能
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
     * Constructs an IndexOutOfBoundsException detail message.
     * Of the many possible refactorings of the error handling code,
     * this "outlining" performs best with both server and client VMs.
     */
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size; // 对于短字符串用 + 号最快，对于大量字符串拼接用 StringBuilder
}

remove(int index)、remove(Object o)

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
// 根据索引删除
public E remove(int index) {
    rangeCheck(index); // 索引范围检查

    modCount++; // 修改次数 + 1
    E oldValue = elementData(index); // 先获取旧值用于返回

    int numMoved = size - index - 1; // numMoved 是删除 index 上的数后需要移动的元素的个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved); // 又是一个 arraycopy
    elementData[--size] = null; // clear to let GC do its work，容量 - 1 并且最后一个元素指向空，表示不可达，等待下次垃圾回收

    return oldValue;
}

/**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If the list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns <tt>true</tt> if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
// 删除指定对象，如果有多个，删除第一个
public boolean remove(Object o) { // 这里和 contains(Object o) 实现类似
    // for 循环遍历，找到第一个相等的元素删除
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index); // 这里调用 fastRemove() 方法进行删除当前元素
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
// 发现和 remove(index) 思路一样啊，也是 arraycopy 移动元素，
// 然名字是 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
}

clear()

/**
     * Removes all of the elements from this list.  The list will
     * be empty after this call returns.
     */
// 清空 List
public void clear() {
    modCount++; // 清空也是一次修改
	
    // 将每个元素置空，等待 GC 回收
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0; // size 置为 0
}

延伸：下面这段代码扩容几次？

List<Object> list = new ArrayList<>();
list.add("a"); 
list.clear();
list.add("a");

答案：扩容 1 次，创建空的 ArrayList()，第一次添加元素会进行 1 次扩容，扩容为 10，然后 clear() 清空 List 之后，只是把数组中的元素个数 size 置为 0，再次添加此时 elementData 数组的长度还是 10，所以不会执行扩容。

所以当我们还要复用这个 List 的时候，就可以使用 clear()，而不建议使用 new ArrayList() 的方式，因为它每次会进行一次扩容。

addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)

/**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
// 向 List 中添加一个 List
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); // 数组拷贝，把 a 数组放到 elementData 数组后面
    size += numNew; // 元素个数 + numNew
    return numNew != 0; // 如果不是 0 就可以添加成功
}

/**
     * Inserts all of the elements in the specified collection into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order that they are returned by the
     * specified collection's iterator.
     *
     * @param index index at which to insert the first element from the
     *              specified collection
     * @param c collection containing elements to be added to this list
     * @return <tt>true</tt> if this list changed as a result of the call
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified collection is null
     */
// 向 List 的某个位置上插入一个 List
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index); // 插入索引范围检查

    Object[] a = c.toArray();
    int numNew = a.length;
    // 确保内部容量
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index; // 要往后移动的元素个数
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved); // arraycopy 移动数组

    System.arraycopy(a, 0, elementData, index, numNew); // 将 a 数组插入到 index 位置上
    size += numNew; // 更新 size
    return numNew != 0; // true or false
}

延伸：向一个空的 List 中添加一个空的 List，以下代码输出是什么？

1
2
3

List<Object> list = new ArrayList<>();
List<Object> list2 = new ArrayList<>();
System.out.println(list.addAll(list2));

答案：false，添加的时候执行第一句话 c.toArray()，返回的 a 就是一个空数组（toArray() 方法转换的时候看的是 size 而不是数组的 length，size = 0, length = 10），所以 a.length = 0，那么最后返回的就是 false。

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

public static <T> T[] copyOf(T[] original, int newLength) { // newLength = 0
    return (T[]) copyOf(original, newLength, original.getClass());
}

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength)); // newLength = 0 
    return copy;
}

removeRange(fromIndex, toIndex)

/**
     * Removes from this list all of the elements whose index is between
     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
     * Shifts any succeeding elements to the left (reduces their index).
     * This call shortens the list by {@code (toIndex - fromIndex)} elements.
     * (If {@code toIndex==fromIndex}, this operation has no effect.)
     *
     * @throws IndexOutOfBoundsException if {@code fromIndex} or
     *         {@code toIndex} is out of range
     *         ({@code fromIndex < 0 ||
     *          fromIndex >= size() ||
     *          toIndex > size() ||
     *          toIndex < fromIndex})
     */
// 范围删除
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex; // 要移动的元素个数
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved); // 将 [toIndex, size) 拷贝到从 fromIndex 开始

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) { // 删除后面的元素
        elementData[i] = null;
    }
    size = newSize; // 更新 size
}

removeAll(Collection<?> c)

/**
     * Removes from this list all of its elements that are contained in the
     * specified collection.
     *
     * @param c collection containing elements to be removed from this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException if the class of an element of this list
     *         is incompatible with the specified collection
     * (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if this list contains a null element and the
     *         specified collection does not permit null elements
     * (<a href="Collection.html#optional-restrictions">optional</a>),
     *         or if the specified collection is null
     * @see Collection#contains(Object)
     */
// 从 List 中删除集合 c 中的所有元素
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c); // 判断是否为空，调用的是 Object 的方法
    return batchRemove(c, false); // 批量删除
}

// Object.class
public static <T> T requireNonNull(T obj) {
    if (obj == null) // 只判断了是否为 null，没有判断空 List
        throw new NullPointerException();
    return obj;
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData; // 复制一份 elementData
    int r = 0, w = 0; // 定义两个指针
    boolean modified = false;
    try {
        // complement = false，所以 for 循环的含义就是将不在 c 集合中的元素放到数组的前面，并且记录个数 w
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) { // 正常情况下上面循环执行结束 r = size
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) { // w == size 表示 elementData 全删
            // clear to let GC do its work
            for (int i = w; i < size; i++) // 将 [w, size) 后面的元素全部删掉
                elementData[i] = null;
            modCount += size - w; // 更新 modCount
            size = w; // 更新 size
            modified = true; // 修改成功
        }
    }
    return modified;
}

writeObject(java.io.ObjectOutputStream s)、readObject(java.io.ObjectInputStream s) 序列化和反序列化

序列化：

我们的 elementData transient Object[] elementData; // non-private to simplify nested class access 是被 transient 修饰的，所以不能被序列化，那具体是怎么序列化的呢，同时这样做的好处是什么？
看源码之后发现，是通过 for 循环 elementData 数组中的元素，对每个元素进行序列化，我不对整个数组序列化，因为 elementData 的容量通常情况下是比 size 大的，扩容的时候每次大约 1.5 倍，那么就有 1 / 3 的空间是空的，空的数据没必要序列化。
好处：1. 不浪费序列化的内容 2. 无需考虑 null 序列化的问题，因为有的序列化方式序列化 null 会报错

/**
 * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 * is, serialize it).
 *
 * @serialData The length of the array backing the <tt>ArrayList</tt>
 *             instance is emitted (int), followed by all of its elements
 *             (each an <tt>Object</tt>) in the proper order.
 */
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount; // 将 modCount 存一份，用于判断在 List 序列化的过程中是否有其他线程进行了修改
    s.defaultWriteObject(); // 对 ObjectOutputStream 做一个初始化

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size); // 先把 size 序列化

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) { // for 循环序列每个元素，这里太妙了！！！
        s.writeObject(elementData[i]);
    }

    // 最后判断是否有并发修改异常，如果出现异常则序列化失败
    // 那么如果有修改，序列化就白做了，但其实这也符合实际场景：一切对于我们的 list 的业务上的修改级别高于序列化。
    if (modCount != expectedModCount) { 
        throw new ConcurrentModificationException();
    }
}

/**
 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 * deserialize it).
 */
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored // 先读取 List 的大小

    if (size > 0) { // 如果有数据再反序列化
        // be like clone(), allocate array based upon size not capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size); // 先保证容量

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) { // 每次读一个对象存到 elementData 中
            a[i] = s.readObject();
        }
    }
}

迭代器相关

TODO