JDK剖析-集合篇-ArrayList

Arraylist 和 LinkedList 是在工作中常用的集合工具。

构造方法

public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

初始化长度为 0 的 Object[]，当第一次 add()方法时，扩充为 DEFAULT_CAPACITY 个长度(默认为 10)；

public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
}

初始化 initialCapacity 长度的 Object[]，

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

初始化长度为 c.size()的 Object[]。

全局变量

private static final int DEFAULT_CAPACITY = 10;
当第一次 add 的时候，默认扩容的长度

private static final Object[] EMPTY_ELEMENTDATA = {};
空构造初始化的对象

private transient Object[] elementData;
保存元素的数组

private int size;
当前 list 的长度

protected transient int modCount = 0;
list 长度修改的次数，即 elementData 修改的次数

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
list 的最大长度，减 8 是因为有些虚拟机会将头信息放进数组中，为了防止 OutOfMemoryError 发生，

add()方法

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

首先确定确定 list 的容量，如果容量满了，就扩容。 然后存入 size++位置 返回 true

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

首先判断 elementData 是不是刚初始化的空数组，如果是就将 minCapacity 赋值为 DEFAULT_CAPACITY(默认为 10)，

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

将 elementData 的修改次数 modCount 加一

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

oldCapacity » 1 就是 oldCapacity 的二分之一，也就是 newCapacity= oldCapacity*1.5，也就是数组需要扩容是则扩容原来的 1.5 倍的长度。

remove()方法

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

根据索引值查出元素位置，首先检查索引位置的合法性，记录修改次数，拿出被删元素，将被删除索引位置后面的元素依次往前移，将尾部元素位置至 Null，记录数组 size，并返回被删元素。

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

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
}

根据元素对象删除，根据元素是否为 Null，遍历出元素位置，然后删除。

set()方法

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

get()方法

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

总结

ArrayList 类的内部实现比较简单，内部维护一个 Object 数组，当需要扩充容量的时候，会新建一个 Object 数组，将原来的数据拷贝进来。操作 list 的方法实现也较简单。