ArrayList底层数据结构

ArrayList底层使用的数组这个基本的数据结构，我们看下它的初始化及添加数据时的扩容策略。

ArrayList list = new ArrayList()
list.add("ss");
list.add("mm");
list.remove(1)
list.remove("ss"); 

1. 创建一个list对象

/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

我们可以看的默认的构造函数，直接将存储数据的数组进行初始化，DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个初始化为空的数组

/**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

2. 调用add方法，将值添加进数组
   因为我们初始化一个空的list，所以在add的时候会进行数组扩容

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

DEFAULT_CAPACITY为默认容量是10，因为首次调用add此时minCapacity为10而数组长度为0，因此会调用grow进行扩容设置当前数组长度为10，如果当前capacity达到初始容量，则之后扩容会按之前的1.5倍进行扩容。
扩容方式是调用Arrays.copyof（elementdata,newCapacity）方法这个方法底层调用了native方法System.arraycopy

3. 调用remove方法，remove(int index)和remove(Object o)的区别是remove(int index)会有边界判断并且会将要移除的对象返回，而remove(Object o)是返回移除成功失败的boolean返回值，最终会调用System.arraycopy将删除index+1开始的数据复制到当前的index开始的位置，这样就可以将数组最后一位置为null，最后一个对象可以通过gc来释放。

System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);

4. 代码中出现的modCount作用是防止在迭代遍历的过程中进行删除，添加操作
   关于Arrays.copyOf与System.arraycopy参考以下文章
   参考https://blog.csdn.net/zhouxukun123/article/details/79314175?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase