一. 初始化
- 1.1 底层的数据结构以及容量
- 1.2 初始化的几种方法
二. 添加元素
- 2.1 添加元素以及扩容机制(Java1.8)
- 2.2 在指定位置插入元素
  - 2.2.1 add方法
  - 2.2.2 System.arraycopy方法

一. 初始化

1.1 底层的数据结构以及容量

由源码可知，ArrayList其实是一个Object的数组，初始化的时候如果不指定容量的话，那么初始话的容量就是10

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 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 Object[] elementData; // non-private to simplify nested class access

1.2 初始化的几种方法

1.2.1 不指定长度

不指定长度的话，会使用无参构造函数，并且让存储数据的elementData数组，指向一个已经声明空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    /**
     * 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 = {};
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

1.2.2 指定长度

若指定长度的话，那么会new出一个新的Object的数组，如果指定的长度为0，那么elementData就会指向一个已经声明的空数组EMPTY_ELEMENTDATA。如果指定的长度是无效的话，比如小于0，那么就会抛出IllegalArgumentException

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {}; 
    /**
     * 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);
        }
    }

1.2.3 指定一个Collection的子类

给定一个Collection的子类，来new出一个ArrayList，首先判断给定的子类示例大小，如果等于0，则直接让elementData指向EMPTY_ELEMENTDATA。
如果给定的子类是ArrayList的类型的，那么直接改变elementData引用的指向，让其指向给定的示例的内存地址即可。

如果如果给定的子类不是ArrayList的类型的，那么调用Arrays.copyOf(a, size, Object[].class);方法进行复制操作

 /**
  * Shared empty array instance used for empty instances.
  */
 private static final Object[] EMPTY_ELEMENTDATA = {};   
 /**
  * Constructs a list containing the elements of the specified
  * collection, in the order they are returned by the collection's
  * iterator.
  *
  * @param c the collection whose elements are to be placed into this list
  * @throws NullPointerException if the specified collection is null
  */
 public ArrayList(Collection<? extends E> c) {
     Object[] a = c.toArray();
     if ((size = a.length) != 0) {
         if (c.getClass() == ArrayList.class) {
             elementData = a;
         } else {
             elementData = Arrays.copyOf(a, size, Object[].class);
         }
     } else {
         // replace with empty array.
         elementData = EMPTY_ELEMENTDATA;
     }
 }

二. 添加元素

2.1 添加元素以及扩容机制(Java1.8)

2.1.1 add方法

添加一个元素到arrayList中，会先调用ensureCapacityInternal(size + 1);方法，进行容量确认，是否需要扩容。然后在索引size+1的位置上，把元素插入到数组里面

    /**
     * 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) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2.1.2 ensureCapacityInternal方法

注意，此方法接收的参数是 size + 1。
此方法又调用了 calculateCapacity(elementData, minCapacity) 方法来计算新的容量，并且调用了ensureExplicitCapacity来完成扩容


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

2.1.3 calculateCapacity方法

此方法接受参数当前数组和 minCapacity（其等于 size + 1）。如果当前是空数组的话，那么就把默认的容量10和最小的指定容量minCapacity的较大的一个值返回去，此时因为是空数组，所以一定会返回10.
如果不是空数组的话，那么就会返回minCapacity

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

2.1.4 ensureExplicitCapacity方法

用这个方法来判断，是否需要扩容。

当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入（执行）grow(minCapacity) 方法。
添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。

直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。
PS：element.length指的是数组的长度，就算有的索引没数据，这个索引的位置也是会被算进长度里面的。
size这个变量值得是，这个arrayList示例里面有多少个有效元素。注意不要和上面的length搞混了

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

2.1.5 grow方法

当 add 第 1 个元素时，oldCapacity 为 0，经比较后第一个 if 判断成立，newCapacity = minCapacity(为 10)。但是第二个 if 判断不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 hugeCapacity 方法。数组容量为 10，add 方法中 return true,size 增为 1。
当 add 第 11 个元素进入 grow 方法时，newCapacity 为 15，比 minCapacity（为 11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 方法。数组容量扩为 15，add 方法中 return true,size 增为 11。
以此类推······
elementData = Arrays.copyOf(elementData, newCapacity); 来把元素copy到指定长度的数组中，再返回给elementData

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

“>>”（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源

    /**
     * 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;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

2.1.6 hugeCapacity方法

从上面 grow() 方法源码我们知道：如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

    /**
     * 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;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

2.2 在指定位置插入元素

2.2.1 add方法

方法接收，插入位置的索引和，被插入的元素。在插入之前会进行索引有效性的check。然后判断是否扩容，扩容的方法参照2.1中内容。
需要重点说明一下System.arraycopy这个方法。
最后把元素插入到对应的索引位置就可以了。

    /**
     * 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);
        elementData[index] = element;
        size++;
    }

2.2.2 System.arraycopy方法

没用的注释有一大堆，所以删掉了一些。5个参数的意思分别是

源数组：要被拷贝的数组是哪个
源数组开始位置：要哪个位置开始拷贝
目标数组：要拷贝到哪个数组
目标数组开始位置：要从哪个位置开始被拷贝
拷贝多少个元素

2.2.1中的调用 System.arraycopy(elementData, index, elementData, index + 1,size - index);
例子：有一个数组[1, 2, 3, 4, 5], 要在索引2的位置插入8. 那么调用此方法就是
把[1, 2, 3, 4, 5]从索引2的位置开始拷贝，要拷贝3个元素（size-index即5-2）即拷贝了[3, 4, 5], 到目标数组中（也就是源数组）的索引（index+1）的位置,即索引3。那么现在的数组就变成了[1, 2, 3, 3, 4, 5]
最后调用的elementData[index] = element; 指令把数组里面红色的3覆盖成8就大功告成。

    /**
     * @param      src      the source array.
     * @param      srcPos   starting position in the source array.
     * @param      dest     the destination array.
     * @param      destPos  starting position in the destination data.
     * @param      length   the number of array elements to be copied.
     */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

ArrayList详解