手写ArrayList

　写一个自定义ArrayList有利于提升自己对java数据结构的理解。 ArrayList底层使用数组。数组的难点在于在数组中间插入，删除麻烦。优点查询速度快。

　直接上代码　　

  一个简单的集合有以下方法，我们使用接口MyList定义方法。

public interface MyList<E> {

	public boolean add(E e);

	public boolean add(int index, E e);

	public E remove(int index);

	public boolean remove(E e);

	public int size();

	public E get(int index);

}

　　

有了方法，我们只需要关注业务逻辑，具体代码实现。

import java.util.Arrays;

public class MyArrayList<E> implements MyList<E> {

    private Object[] elementData;

    private int size;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    public MyArrayList() {
        this(10);
    }

    public MyArrayList(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 int size() {
        return size;
    }

    /**
     * 数组扩容
     * 
     * @param minCapacity
     */
    private void ensureCapacityInterval(int minCapacity) {
        int oldCapacity = elementData.length;
        // 扩容原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 防止出现原数组 长度为0的情况
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        // 扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 插入 第一步 检查是否需要扩容 第二步 赋值
     */
    public boolean add(E e) {
        ensureCapacityInterval(size + 1);
        elementData[size++] = e;
        return true;
    }

    /**
     * 指定位置 add
     * 
     * @param index
     * @param obj
     */
    public boolean add(int index, Object obj) {
        rangeCheck(index);
        ensureCapacityInterval(size + 1);
        // 插入操作
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = obj;
        size++;
        return true;
    }

    public E remove(int index) {
        rangeCheck(index);
        E oldValue = elementData(index);
        // 移除操作
        System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
        elementData[--size] = null;
        return oldValue;
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    public boolean remove(Object object) {
        // 数组移除分二种情况 一种为空
        if (object == null) {
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null) {
                    remove(i);
                    return true;
                }
            }

        } else {
            // 另外一种判断对象是否相等
            for (int i = 0; i < size; i++) {
                if (get(i).equals(object)) {
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }

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

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

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

}