3、ArrayList源码分析

我们都知道ArrayList查询和修改快，增加和删除慢，why？我们今天尝试从源码角度去解析它。

一、先看个例子

public class Test {
    public static void main(String[] args) {
        List<Integer> integers = new ArrayList<>();
        integers.add(1);
        integers.add(2);
        integers.add(3);
        integers.add(4);
        System.out.println("原始数组：" + integers);

        // 往索引下标为2的位置加入元素14
        integers.add(2, 14);
        System.out.println("往下标2位置插入元素14：" + integers);

        // 删除索引下标为1的元素
        integers.remove(1);
        System.out.println("删除下标1位置的元素：" + integers);

        // 修改索引下表为1的元素
        integers.set(1,13);
        System.out.println("修改下标1位置的元素：" + integers);

        // 查询下标为3的元素
        System.out.println("查询下标3位置元素：" + integers.get(3));
    }
}

运行结果：

原始数组：[1, 2, 3, 4]
往下标2位置插入元素14：[1, 2, 14, 3, 4]
删除下标1位置的元素：[1, 14, 3, 4]
修改下标1位置的元素：[1, 13, 3, 4]
查询下标3位置元素：4

结果分析：
add(e)，添加的元素，默认添加到在集合的末尾。
add(index, e)，在指定位置添加元素，该位置后续的元素往后移动。
remove(index)，删除指定位置的元素，该位置后续的元素往前移动了。
set(index,e), 修改指定位置的元素。
get(index)，获取指定位置的元素。

二、源码解读

// ArrayList实现List接口
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

    /**
     * 当第一个元素添加时，默认的初始化容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 默认空数组，用以初始化一个空的ArrayList
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区。 
     * ArrayList的容量是此数组缓冲区的长度。添加第一个元素时，任何 
     * 具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 
     * 的空ArrayList都将扩展为DEFAULT_CAPACITY。
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 构造一个空的ArrayList列表
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

   /**
     * 构造具有指定初始容量的空列表
     */
    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);
        }
    }

    /**
     * 添加指定元素到集合末尾
     * 空集合首次添加元素，会初始化集合长度为10
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 空集合首次添加元素，会初始化集合长度为10
        elementData[size++] = e;
        return true;
    }

 /**
     * 将指定的元素插入此列表中的指定位置。
     * 将当前在该位置的元素（如果有的话）和任何后续元素向右移动
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // 空集合首次添加元素，会初始化集合长度为10
        System.arraycopy(elementData, index, elementData, index + 1,size - index); // 将当前在该位置的元素（如果有的话）和任何后续元素向右移动
        elementData[index] = element; // 在当前位置添加指定元素
        size++;
    }

    /**
     * 删除此列表中指定位置的元素。
     * 将所有后续元素向左移动
     */
    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;
    }

   /**
     * 返回此列表中指定位置的元素。
     */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

}

源码分析：
1、ArrayList底层是一个Object数组。
2、可以创建一个长度为0的数组，也可以创建指定长度(>0)的数组。
3、首次添加元素，数组长度默认初始化长度为10。
4、当使用add(e)方法添加元素时，默认添加到数组末尾，因为无需移动其他元素，因此时间复杂度为O(1)。
5、当使用add(index,e)方法添加元素到数组指定位置，因为需要把指定位置后面的元素都往后移动一个位置，因此时间复杂度为O(N)。
6、当使用remove(index)删除指定位置元素时，因为需要把指定位置后面的元素都往前移动一个位置，因此时间复杂度为O(N)。
7、当使用set(index,e)方法修改指定位置元素时，因为无需移动其他元素，因此时间复杂度为O(1)。
8、当使用get(index)方法查询指定位置元素时，因为无需移动其他元素，因此时间复杂度为O(1)。
9、非线程安全。容量不足时，扩容是原来的1.5倍。

vector类和ArrayList类的区别：
1、vector是线程安全的，也就是说vector在增删改查的方法上都加上了synchronized关键字。