自定义实现ArrayList

ArrayList底层使用Object数组来存储元素数据。 特点：查询效率高，增删效率低。

我们知道，数组长度是有限的，而ArrayList是可以存放任意数量的对象，长度不受限制，那么它是怎么实现的呢？

本质上就是通过定义新的更大的数组，将旧数组中的内容拷贝到新数组，来实现扩容。ArrayList的Object数组初始化长度为10，如果我们存储满了这个数组，需要存储第11个对象，就会定义新的长度更大的数组，并将原数组内容和新的元素一起加入到新数组中。

下面自定义实现ArrayList的基本功能：

public class MyArrayList<E> {
    // ArrayList的底层实现是一个可以放入任何对象并且扩容的数组
    private Object[] elementData;
    private int size = 0;
    // 默认对象数组容量
    private static final int DEFALT_CAPACITY = 10;

    public MyArrayList() {
        // 调用重载构造方法
        this(DEFALT_CAPACITY);
    }

    public MyArrayList(int capacity) {
        elementData = new Object[capacity];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    // 按索引获取元素
    public E get(int index) {
        checkRange(index);
        return (E) elementData[index];
    }

    // 按索引修改元素
    public void set(int index, E element) {
        checkRange(index);
        elementData[index] = element;
    }

    // 判断索引合法性
    public void checkRange(int index) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("索引不合法:" + index);
        }
    }

    // 新增方法包含自动扩容
    public void add(E element) {
        // 数组扩容
        if (size == elementData.length) {
            // 创建一个容量更大的新数组
            Object[] newArray = new Object[elementData.length + (elementData.length >> 1)];
            /*
             * System类的复制数组方法 arraycopy(Object src, int srcPos, Object dest, int destPos,
             * int length) Copies an array from the specified source array, beginning at the
             * specified position, to the specified position of the destination array.
             */
            System.arraycopy(elementData, 0, newArray, 0, elementData.length);
            elementData = newArray;
        }
        elementData[size++] = element;
    }

    public void remove(int index) {
        checkRange(index);
        int theLength = elementData.length - index - 1;
        System.arraycopy(elementData, index + 1, elementData, index, theLength);
        elementData[--size] = null;
    }

    // 删除List内所有指定对象
    public void remove(E element) {
        for (int i = 0; i < size; i++) {
            if (element.equals(get(i))) {
                remove(i);
            }
        }
    }

    public void clear() {
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i] + ",");
        }
        if (sb.length() == 1) {
            sb.append("]");
        } else {
            // 将最后一个“,”替换为“]”
            sb.setCharAt(sb.length() - 1, ']');
        }
        return sb.toString();
    }
}