1. 简介

List是一种支持插入、删除、查找，元素可重复，可为null的数据结构，在JDK中有不同的实现类，其中ArrayList基于数组实现，支持随机访问，非线程安全，插入与删除时间复杂度为O(n)。

2. 实现

ArrayList内部是使用数组来实现的，所以可以做到随机访问时间为O(1)，如果不一开始设置好最终的大小，可能在不断添加元素的过程中多次扩容而导致效率问题。

属性

//默认容量
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};
//数组最大大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//元素存放的数组，设置为transient的目的是序列化对象时忽略该数组，因为数组可能不是存满的，我们只序列化必要的对象以节省空间时间。
transient Object[] elementData; // non-private to simplify nested class access
//已经添加的元素数量
private int size;

构造函数

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，只不过这个大小为10的数组是延迟到添加元素创建的，所以这里
// 一开始数组大小是0。
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

扩容函数

private void ensureCapacityInternal(int minCapacity) {
    // 这里就是默认大小数组延迟创建的开始部分了
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}


private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 判断是否需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新数组的大小为旧数组的1.5倍
    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);
}

增删改查方法

// 获取指定位置上的元素
public E get(int index) {
        //范围检查，index超出范围抛出异常
        rangeCheck(index);
        return elementData(index);
}

// 修改指定位置上的元素并返回旧元素
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

// 添加元素到列表尾部
public boolean add(E e) {
    // 判断是否需要扩容，如需要则扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 添加元素到指定索引位置
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++;
}

// 移除指定位置上的元素并返回其值
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;
}

// 若存在对象o则移除
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;
    }

// 清空所有对象
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

toArray方法

// 复制出一个具有原数组所有元素的新数组
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

subList方法

创建出一个子List，对该List的操作将作用于到原List上

public List<E> subList(int fromIndex, int toIndex) {
    // 检查索引范围是否合法
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

sort方法

List接口中存在默认的sort方法，只不过该方法是为LinkedList非基于数组实现的List准备的，所以ArrayList重写了sort方法，通过调用Arrays.sort()方法直接对数组进行排序效率比默认的高。

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

3. 适用场景

ArrayList内部基于数组实现，查找效率非常高，但是当出现大量的插入或删除操作，每次都要移动大量元素，明显效率很低。所以ArrayList应该适合于那种查找操作多于插入删除操作的场景。
ArrayList比LinkedList节省空间，因为ArrayList核心就是一个存储该类元素的数组。在64位虚拟机下，不开启指针压缩情况下：
- ArrayList存储元素消耗的空间为 24字节（数组对象头）+ 数组长度 * 8字节
- LinkedList存储元素消耗的空间为元素数量 * 40字节（结点对象头 + 前后结点指针 + 元素指针）
- 总的来说，每存储一个元素，ArrayList平均消耗8个字节的引用空间，而LinkedList除了消耗8个字节的引用空间还要32字节的空间（结点对象头 + 前后结点指针）

ArrayList源码解析

2018-04-15
JDK源码解析