实现 ArrayList

我看了下 JDK 里面 ArrayList 的源码，抄了一些核心代码出来，然后加了一些注释。ArrayList 是一个比较简单的数据结构，它最核心的部分就是自动扩容。

import java.util.Arrays;

class ArrayList<E> {


    private static final int DEFAULT_CAPACITY = 10;

    private int size;

    private Object[] elementData;

    private static final Object[] empty = {};

    protected transient int modCount = 0;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    public ArrayList() {
        // 默认使用空数组初始化
        this.elementData = this.empty;
    }


    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            elementData = new Object[initialCapacity];
        }
        // 如果初始化容量为 0，则使用空数组
        else if (initialCapacity == 0) {
            this.elementData = this.empty;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }

    }


    public boolean add(E element) {
        // 每次增加新元素前，确保数组容量足够
        ensureCapacity(size + 1);
        elementData[size] = element;
        size++;
        return true;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacity(size + 1);

        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

    public void ensureCapacity(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // 如果当前容器数组为空数组，则在默认的容量和指定的容量中选择较大的一个，否则直接返回指定的容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == empty) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

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

        // 如果指定容量大于容器数组实际容量就得扩容
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }

    private void grow(int minCapacity) {
        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);
        }

        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_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;

        return oldValue;
    }

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

        return elementData(index);
    }

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

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

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

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

    public static void main(String[] args) {
        ArrayList a = new ArrayList();

        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);
        a.add(1);


        System.out.println(a.get(0));
    }


}