按照从构造方法->常用API（增、删、改、查）的顺序来阅读源码，并做简要分析。

一. 定义

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

介绍

继承了AbstractList，实现了List
它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
实现了RandmoAccess接口
即提供了随机访问功能
实现了Cloneable接口
即覆盖了函数clone()，能被克隆
实现java.io.Serializable接口
支持序列化，能通过序列化去传输

优势

比数组的优势
ArrayList 是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长
比Vector的优势
和Vector不同，ArrayList中的操作不是线程安全的，但是开销小，在单线程环境性能优于Vector

二 .属性

底层用数组来保存数据

1 2	private transient Object[] elementData; private int size;

size ：当前数组长度
elementData：存放数组的对象的数组
modCount：ArrayList集合的修改次数

基于数组实现，保存元素的数组使用 transient 修饰，该关键字声明数组默认不会被序列化。这是 ArrayList 具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。ArrayList 重写了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

三. 构造函数

1）无参构造函数–`ArrayList()`

Constructs an empty list with an initial capacity of ten.

1
2
3

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

1	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.

1	private static final int DEFAULT_CAPACITY = 10;

此时我们创建的ArrayList对象中的elementData中的长度是1，size是0,当进行第一次add的时候，elementData将会变成默认的长度：10.(具体过程看下文的add())

2)带容量大小的构造函数–`ArrayList(int initialCapacity)`

传入参数如果是大于等于0，则使用用户的参数初始化，如果用户传入的参数小于0，则抛出异常

Constructs an empty list with the specified initial capacity.

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

3)带Collection对象的构造函数–`ArrayList(Collection<? extends E> c)`

构造一个包含指定元素的list，这些元素的是按照Collection的迭代器返回的顺序排列的

将collection对象转换成数组，然后将数组的地址的赋给elementData
更新size的值，同时判断size的大小
2.1 如果是size等于0，直接将空对象EMPTY_ELEMENTDATA的地址赋给elementData
2.2 如果size的值大于0，则执行Arrays.copy方法，把collection对象的内容copy到elementData中

Constructs a list containing the elements of the specified collection, in the order they are returned by the collection’s iterator.

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    //因为size代表的是集合元素数量，所以通过别的集合来构造ArrayList时，要给size赋值
    if ((size = elementData.length) != 0) {
        //这里是当c.toArray出错，没有返回Object[]时
        //利用Arrays.copyOf 来复制集合c中的元素到elementData数组中
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

1	private static final Object[] EMPTY_ELEMENTDATA = {};

Arrays.copyOf()方法

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) {
     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));
     return copy;
 }

可以看到，他是在方法内部，新建了一个相同类型的数组，然后调用系统方法

1	System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));

original - 源数组。
0 - 源数组中的起始位置。
copy - 目标数组。
0 - 目标数据中的起始位置。
Math.min(original.length, newLength) - 要复制的数组元素的数量。

四. 增加—add addAll

添加元素时使用 ensureCapacity() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，使得新容量为旧容量的 1.5 倍oldCapacity + (oldCapacity >> 1)
扩容操作需要把原数组整个复制到新数组中，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

添加一个元素(在末尾)–`add(E e)`

add(E e)

Appends the specified element to the end of this list.

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;//在数组末尾追加一个元素，并修改size
    return true;
}

ensureCapacityInternal(int minCapacity)

确保添加的元素有地方存储
当第一次添加元素的时候this.size+1 的值是1，所以第一次添加的时候会将当前elementData数组的长度变为10

1
2
3

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

calculateCapacity(Object[] elementData, int minCapacity)

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //利用 == 可以判断数组是否是用默认构造函数初始化的
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

1	private static final int DEFAULT_CAPACITY = 10;

ensureExplicitCapacity()

经过前面的一顿操作，minCapacity 是

DEFAULT_CAPACITY（10）
当第一次添加时
size + 1
当不是第一次添加时

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //如果确定要扩容，会修改modCount 
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow()

Increases the capacity to ensure that it can hold at least the number of elements specified by the minimum capacity argument

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 旧容量的1.5倍
  //如果还不够 ，那么就用 能容纳的最小的数量。（add后的容量）
    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);
}

在指定位置添加一个元素–`add(int index, E element)`

Inserts the specified element at the specified position in this list.

确保有足够的容量之后
使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位
将新的数据内容存放到数组的指定位置（index）上

public void add(int index, E element) {
    rangeCheckForAdd(index);
    // 进行扩容检查
    ensureCapacityInternal(size + 1);  // Increments modCount!!
   // 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
   // 将指定的index位置赋值为element
    elementData[index] = element;
    size++;
}

关于arraycopy()

1
2
3

public static void (Object src,int srcPos,
                    Object dest,int destPos,
                    int length)

参数	意义
src	源数组
srcPos	源数组要复制的起始位置
dest	目的数组
destPos	目的数组放置的起始位置
length	复制的长度

src和dest都必须是同类型或者可以进行转换类型的数组
可以实现自己到自己复制

其中rangeCheckForAdd是为了防止越界：

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

增加一个集合–`addAll(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.

 public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();//将集合转换为数组
    int numNew = a.length;
    //扩容检查
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将c添加至list的数据尾部
    System.arraycopy(a, 0, elementData, size, numNew);
    //更新当前容器大小
    size += numNew;
    return numNew != 0;
}

在指定位置，增加一个集合元素–`addAll(int index, Collection<? extends E> c)`

Inserts all of the elements in the specified collection into this list, starting at the specified position.

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //计算需要移动的长度（index之后的元素个数）
    int numMoved = size - index;
    //将数组index后的元素向右移动numNum个位置，即空出第index到index+numNum的位置
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //将要插入的集合元素复制到数组空出的位置中
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

关于增的总结：
add、addAll。
先判断是否越界，是否需要扩容。
如果扩容，就复制数组。
然后设置对应下标元素值。

值得注意的是：
1 如果需要扩容的话，默认扩容一半。如果扩容一半不够，就用目标的size作为扩容后的容量。
2 在扩容成功后，会修改modCount

五. 删除—remove

根据索引位置删除元素–`remove(int index)`

Removes the element at the specified position in this list.

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);// 供返回
    int numMoved = size - index - 1;// 计算数组要复制的数量
   // 数组复制，就是将index之后的元素往前移动一个位置
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 因为删除了一个元素，然后index后面的元素都向前移动了，所以最后一个就没用了
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

根据元素内容删除，只删除匹配的第一个–`remove(Object o)`

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.

循环遍历所有对象，得到对象所在索引位置，然后调用fastRemove方法，执行remove操作

null值要用==比较

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

fastRemove()

Private remove method that skips bounds checking and does not return the value removed.

定位到需要remove的元素索引，先将index后面的元素往前面移动一位（调用System.arraycooy实现），然后将最后一个元素置空。

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
}

数组越界检查

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

1
2
3

private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

六. 查找—get

查找指定位置上的元素

Returns the element at the specified position in this list.

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

七. 更新—set

将指定位置的元素更新为新元素

Replaces the element at the specified position in this list with the specified element.

注意返回值是oldValue

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);// 记录要更新位置的元素，供返回使用
    elementData[index] = element;
    return oldValue;
}

八. 判断

包含–`contains(Object o)`

调用indexOf方法，遍历数组中的每一个元素作对比，如果找到对于的元素，则返回true，没有找到则返回false

1
2
3

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

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

空–`isEmpty()`

1
2
3

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

九. ArrayList遍历方式

ArrayList支持3种遍历方式

通过迭代器遍历。即通过Iterator去遍历。

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

随机访问，通过索引值去遍历。
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
    value = (Integer)list.get(i);        
}

for循环遍历。如下：

Integer value = null;
for (Integer integ:list) {
    value = integ;
}

十. ArrayList和 Vector 的区别

同步
Vector 和 ArrayList 几乎是完全相同的，唯一的区别在于 Vector 是同步的，因此开销就比 ArrayList 要大，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作完全可以由程序员自己来控制；
扩容
Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。
Vector 的grow()扩容部分

1 2	int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

十一. 小回顾

添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间
add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）
remove(Object o)需要遍历数组
remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高
contains(E)需要遍历数组

参考文章
Java集合干货系列-（一）ArrayList源码解析
 Java官方文档
 ArrayList源码解析（JDK8）