《手写 ArrayList》

public interface List<E> {

  
    /**
     * 返回此列表中指定位置的元素。
     *
     * @param index 列表中指定的下标
     * @return 下标中包含的元素
     */

    E get(int index);

    /**
     * 将此列表中指定位置的元素替换为指定元素（可选操作）
     *
     * @param index
     * @param e     原来下标中的旧值
     */
    E set(int index, E e);

    /**
     * 在此列表中的指定位置插入指定元素（可选操作）。
     * 将当前位于该位置的元素（如果有）和任何后续元素向右移动（将其索引加一）。
     *
     * @param index
     * @param e
     */
    void add(int index, E e);

    /**
     * 将指定元素追加到此列表的末尾（可选操作）。
     * 支持此操作的列表可能会对可以添加到此列表的元素进行限制。
     * 特别是，一些列表将拒绝添加空元素，而另一些列表将对可能添加的元素的类型施加限制。
     * 列表类应在其文档中明确指定对可以添加的元素的任何限制
     */
    boolean add(E e);

    /**
     * 列表中是否包含元素e
     *
     * @param e
     * @return
     */
    int indexOf(E e);

    int lastIndexOf(E o);

    /**
     * 如果此列表包含指定元素，则返回 <tt>true<tt>。
     * 更正式地说，当且仅当此列表包含至少一个元素 <tt>e<tt>
     * 且满足 <tt>(o==null ? e==null : o.equals(e ))<tt>。
     */
    boolean contains(E o);

    /**
     * 删除此列表中指定位置的元素（可选操作）。
     * 将所有后续元素向左移动（从索引中减去 1）。返回从列表中删除的元素。
     */

    E remove(int index);

    /**
     * 从此列表中删除第一次出现的指定元素（如果存在）（可选操作）。
     * 如果此列表不包含该元素，则它不会更改。更正式地说，删除具有最低索引i 的元素，
     * 使得(o==null ? get(i)==null : o.equals(get(i))) （如果存在这样的元素）。
     * 如果此列表包含指定的元素（或者等效地，如果此列表由于调用的结果而更改），则返回true 。
     */
    boolean remove(E o);

    /**
     * 返回此列表中的元素数量
     *
     * @return
     */
    int size();

    /**
     * 如果此列表不包含任何元素，则返回true
     */
    boolean empty();
}

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

/**
 * 数组允许分配的最大值
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 可共享的空实例数组 capacity == 0
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 默认数组
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


/**
 * 底层数据结构 数组 真正存放数据的数据结构
 */
transient Object[] elementData;

/**
 * @param initialCapacity 初始化数组大小
 */
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);
    }
}
/**
 * 默认初始化
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

@Override
public boolean add(E e) {
    // 确保申请的底层数组的容量可以存入当前这个元素
    ensureCapacityInternal(size + 1);
    // 将元素插入数组 并将size+1
    elementData[size++] = e;
    return true;
}

/**
 * 确保底层数组的容量是大于当前需要的最小容量
 * 如果容量不够就进行扩容
 *
 * @param minCapacity 所需最小容量
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 计算容量 选择默认容量和所需容量中的较大者
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}


/**
 * 判断是否需要扩容
 */
private void ensureExplicitCapacity(int minCapacity) {

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 扩容
 *
 * @param minCapacity
 */
private void grow(int minCapacity) {

    int oldCapacity = elementData.length;
    // 默认增加原有素组大小的一半
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 选择 newCapacity 和 minCapacity 中的较大者
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 如果新数组大于我们设定的最大数组长度 MAX_ARRAY_SIZE 则重新计算新数组大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 申请一个新的数组 数组大小为 newCapacity  并将原来数组的中数据拷贝到新数组
    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;
}

/**
 * 扩容
 *
 * @param minCapacity
 */
private void grow(int minCapacity) {

    int oldCapacity = elementData.length;
    // 默认增加原有素组大小的一半
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 选择 newCapacity 和 minCapacity 中的较大者
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;

    // 如果新数组大于我们设定的最大数组长度 MAX_ARRAY_SIZE 则重新计算新数组大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 申请一个新的数组 数组大小为 newCapacity  并将原来数组的中数据拷贝到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

@Override
public void add(int index, E element) {
    // 确保index的位置是合法的
    rangeCheckForAdd(index);

    // 判断是否扩容
    ensureCapacityInternal(size + 1);

    // 从待插入元素位置开始到结尾的所有元素 向后移动一个位置，将待插入位置空出
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    // 设置元素
    elementData[index] = element;
    // 数量+1
    size++;
}


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

@Override
public E set(int index, E element) {
    // 检查下标是否越界
    rangeCheck(index);
    // 旧值
    E oldValue = elementData(index);
    // 插入新值
    elementData[index] = element;
    // 返回旧值
    return oldValue;
}

public E remove(int index) {
    // 判断待删除元素下标是否越界
    rangeCheck(index);

    // 待删除的旧值
    E oldValue = elementData(index);

    // 计算需要移动位置元素的数量
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 移动位置
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    // size-1 
    elementData[--size] = null; // clear to let GC do its work

    // 返回删除元素
    return oldValue;
}