回炉重造-数据结构之数组列表

来尝试手写一个自己的ArrayList

1. 明确ArrayList主要构成：

public class ArrayList<E> {
    //1.存储数据的数组
    Object[] element;
    //2.元素的数量
    int size;
    //3.结构变更记录
    int modCount;
}

2. 确立扩容机制

    /**
     * 把控容量
     *
     * @param minCapacity
     */
    public void ensureCapacity(int minCapacity) {
        modCount++;
        if (element == null) {
            element = new Object[Math.max(minCapacity, DEFAULT_CAPACITY)];
            return;
        }
        if (minCapacity - element.length > 0) {
            grow(minCapacity);
        }
    }

    /**
     * 数组扩容
     *
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = element.length;
        //1.5倍提升
        int newCapacity = oldCapacity + oldCapacity >> 1;
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        if (newCapacity - (Integer.MAX_VALUE - 8) > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        /**
         * 数组拷贝
         */
        Object[] newObject = new Object[newCapacity];
        System.arraycopy(element, 0, newObject, 0, element.length);
        element = newObject;
    }

    /**
     * 大容量判断选择
     *
     * @param minCapacity
     * @return
     */
    private int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        if (minCapacity > Integer.MAX_VALUE - 8) {
            return Integer.MAX_VALUE;
        } else {
            return Integer.MAX_VALUE - 8;
        }
    }

3. ArrayList的行为调用

    public E element(int index) {
        return (E) element[index];
    }

    public E get(int index) {
        return element(index);
    }

    public void add(E e) {
        ++size;
        ensureCapacity(size);
        element[size - 1] = e;
    }

    public void remove(int index) {
        //删除该数据并移动该位置后的数据
        int moveLength = size - index - 1;
        System.arraycopy(element, index + 1, element, index, moveLength);
        element[--size] = null;
        modCount++;
    }

4. 简单的迭代器

    private class Itr implements Iterator<E> {
        private int index;
        private int latestIndex = -1;
        private int expectModCount;

        @Override
        public boolean hasNext() {
            return index != size;
        }

        @Override
        public E next() {
            latestIndex = index;
            index++;
            return ArrayList.this.element(latestIndex);
        }

        @Override
        public void remove() {
            //数据一致性校验
            if(expectModCount != ArrayList.this.modCount){
                throw new ConcurrentModificationException();
            }
            ArrayList.this.remove(latestIndex);
            index = latestIndex;
            latestIndex = -1;
            expectModCount = modCount;
        }
    }

以上就完成简单的ArrayList。