ArrayList的删除实现

      ArrayList的删除实现其实就是和数组添加相反的一个过程，只不过删一个元素和删除多个元素的实现方式略有区别，但是思路还是一样，如下图：

 

一、remove方法

如上，移除一个元素时，可以通过元素或者元素的索引移除，有四个步骤：

（1）判断索引index是否越界

（2）将 index + 1 及之后的元素向前移动一位

（3）最后一个值变为null

（4）长度size - 1

将该索引以后的元素下标前移，最后一个元素置为NULL,源码如下:

       public E remove(int index) {
            /*检查索引是否越界*/
            rangeCheck(index);
          /*记录集合得修改次数*/
            modCount++;
            /*获取被删除的元素*/
            E oldValue = elementData(index);
            /*移动的元素个数*/
            int numMoved = size - index - 1;
            if (numMoved > 0)
                /*参数：被复制的数组， 从被复制数组的第几个元素开始复制，粘贴的目标数组，从目标数组第几个元素开始粘贴，复制的元素个数*/
                System.arraycopy(elementData, index+1, elementData, index, numMoved);
             
            /*将最后一个元素置空，然后GC机制会回收该内存，并且ArrayList的长度-1*/
            elementData[--size] = null; 

            return oldValue;
        }

    public boolean remove(Object o) {
        /*如果删除的元素对象为null*/
        if (o == null) {
            /*删除ArrayList中第一个为null的元素*/
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            /*删除ArrayList中匹配到的第一个元素*/
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    /*不进行索引验证，直接删除*/
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

二、removeAll方法

removeAll的实现方式虽然在思路上和前面一致，但是代码实现略有不同，在移除多个元素时，会遍历数组，先去将数组中的每个元素一一和移除元素数组里的元素匹配，

如图：

当移除完成后，会将最后几位（和移除元素数组长度相同）的元素置为null，源码如下：

    public boolean removeAll(Collection<?> c) {
        /*验证删除Collection是否为null，若null则抛出NullPointerException*/
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
    
    private boolean batchRemove(Collection<?> c, boolean complement) {
        /*获取原数组*/
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            /*遍历所有元素，如果匹配到需要移除的元素，则移除该元素，并将后面未匹配到前移到移除元素位置*/
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            /*r != size 说明元素未完全匹配完，则将未匹配的size - r个元素粘贴到w以后的位置*/
            if (r != size) {
                System.arraycopy(elementData, r, elementData, w, size - r);            
                w += size - r;
            }
            if (w != size) {
                /*将移除完成w以后的元素置为null，由GC回收内存*/
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                /*数组长度置为w*/
                size = w;
                modified = true;
            }
        }
        return modified;
    }

三、clear方法

clear方法也是ArrayList的删除方法之一，只不过是清除所有元素，所以只要将所有元素置为null，由GC回收内存即可

    public void clear() {
        /*记录集合得修改次数*/
        modCount++;
        /*将每个元素置空，之后，内存会被GC回收*/
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        /*元素个数置为0*/
        size = 0;
    }

 上面删除操作，我们发现，元素是没了，但是数组的长度并没有变，那么ArrayList有没有自动缩容机制了，答案是没有，但是它提供可以实现缩容的方法，我们可以手动去触发：

/** 将数组容量缩小至元素数量 */
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}