简单模拟Java中的ArrayList

Java中的ArrayList是用数组实现的。
数组是有界的,因此实现最重要的是数组的扩容机制。
扩容机制:

当要存的数据大于数组大小时,会扩容。
在JDK1.8中,会创建一个新数组,新数组大小为原数组的1.5倍,并将原数组复制到该新数组中。

可以发现,扩容过程会消耗大量的时间、空间,应当尽量避免数组扩容。因此在创建ArrayList时,确定一个合适的初始数组大小是很有必要的。


下面是简单的模拟

public class MyArrayList {
    
    private static final int DEFAULT_CAPACITY = 10;

    private Object[] elementData;

    private int size;

    public MyArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public MyArrayList(int initialCapacity) {
        if (initialCapacity < 0) {
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        elementData = new Object[initialCapacity];
    }
    
    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void add(Object obj) {
        ensureCapacity();

        elementData[size++] = obj;
    }

    
    public void add(int index, Object obj) {
        RangeCheckByAdd(index); //add的check不同,add可以在数组尾部添加,所以可以不加=
        ensureCapacity();

        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = obj;
        size++;
    }
    
    public Object set(int index, Object obj) {
        RangeCheck(index);

        Object oldValue = elementData[index];
        elementData[index] = obj;
        return oldValue;
    }

    public Object get(int index) {
        RangeCheck(index);

        return this.elementData[index];
    }

    public Object remove(int index) {
        RangeCheck(index);

        Object 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 boolean remove(Object obj) {
        if (obj == null) {
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null) {
                    remove(i);
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (elementData[i].equals(obj)) {
                    remove(i);
                }
            }
        }
        return true;
    }
    
    public void clear() {
        for(int i=0;i<size;i++) {
            elementData[i] = null;
        }
        size = 0;
    }

    /**
     * 判断是否达到容量上限==》扩容
     * ArrayList扩容大小:原数组的1.5倍
     * 扩容原理:创建新数组,将原数组复制过来
     * 本方法未考虑超过int表示范围情况
     */
    private void ensureCapacity() {
        if (size == elementData.length) {
            Object[] newArray = new Object[size + (size >> 1)];
            System.arraycopy(elementData, 0, newArray, 0, elementData.length);
            elementData = newArray;
        }
    }

    /**
     * 判断操作位是否越界
     * index表示操作位,从0开始,最大为size-1
     * @param index
     */
    private void RangeCheck(int index) {
        if (index >= size || index < 0) {
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    
    /**
     * 判断操作位是否越界(add)
     * add的越界判断不同。add可以在数组尾部添加,所以index和size相等的情况是可以接受的
     * @param index
     */
    private void RangeCheckByAdd(int index) {
        if (index > size || index < 0) {
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}