1. 简介

• ArrayList是List接口的实现类，是开发中使用比较多的集合工具类，存放于java.util包下
• ArrayList常用于存放一系列数据类型相同的数据集

2. 底层数据结构

• ArrayList底层数据结构是一个数组（Object[] elementData）,默认初始大小为10（是在第一次add时初始化数组容量的）

3. 关键方法

3.1 构造

• 默认无参构造，在默认无参构造器中并未将容量赋值为默认初始容量10，而是将数组指向一个空数组，将数组容量的申请延后到第一次add中（下面add方法会分析）

/** 默认构造 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个常量空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

• 传入初始容量值initialCapacity的构造器，传入initialCapacity < 0会抛异常

// 传入初始容量值initialCapacity的构造器，小于0会抛异常
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);
    }
}

• 传入另一个Collection接口的实现集合类（List、Set等）的构造器

// 传入另一个Collection接口的实现集合类（List、Set等）的构造器
// 本质上是数组的Arrays.copy操作
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

3.2 add

• add添加元素涉及到数组elementData的扩容判断，modCount++（主要用于迭代时判断是否有被修改而抛异常）
• 数组的赋值，存储元素的大小size++

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

• 接着看确认容量的函数ensureCapacityInternal

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

• 本质上调用的是ensureExplicitCapacity方法，参数为calculateCapacity方法的返回值

// 用于计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 当elementData还是空数组即第一次add时，将容量置为默认初始容量10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否则容量为size+1
    return minCapacity;
}

// 用于扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 主要用于迭代时判断是否有被修改而抛异常

    // overflow-conscious code
    // 这里只会第一次和后面size超过数组本身容量才会扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

• 接着看本质上调用的扩容方法grow，每次扩容都是之前容量的1.5倍

// 扩容，首次为10、后面为之前的1.5倍
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 初始时elementData为空数组，这里为0
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为1.5倍
    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);
}

3.3 remove(int index)

• 删除指定位置index，本质上是System.arraycopy复制，相当于移位

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    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

    return oldValue;
}

3.4 remove(E element)

• 删除指定元素（当有多个，只会移除最前面的一个）

// 遍历，找出相等的第一个元素使用fastRemove移除
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;
}

// 跟remove(index)大致相同，只是少了rangeCheck和返回值（毕竟不需要）
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
}

4. 总结

• ArrayList存放于java.util包下是List接口（Coolection的子接口）的实现类
• 用于存放一系列相同类型的集合数据
• 底层数据结构是一个数组，会在第一次add时将10作为默认初始容量，每次扩容是之前的1.5倍并使用System.arraycopy将元素复制到扩容后的数组
• 使用数组作为底层数据结构，故很容易保证元素存储的有序性
• 由于方法都是非同步方法，故无法保证线程安全