JDK ArrayList 删除源码

ArrayList是JDK提供的一个数组list，其实现基于java的数组， elementData是声明在该类里面的实际保存数组的变量：

 

private transient Object[] elementData;

 

删除：

remove的时候，需要遍历整个数组，找到匹配的元素， 然后调用内部私有方法，进行快速删除（fastRemove），这个删除方法不检查数组下标长度等。

    public boolean remove(Object o) {
	if (o == null) {
            for (int index = 0; index < size; index++)
		if (elementData[index] == null) {
		    fastRemove(index);
		    return true;
		}
	} else {
	    for (int index = 0; index < size; index++)
		if (o.equals(elementData[index])) {
		    fastRemove(index);
		    return true;
		}
        }
	return false;
    }

 删除的方式是调用系统类的arraycopy方法对数组本身进行自复制，也可以说是自覆盖，从找到元素的后一个index开始复制（index+1），

    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; // Let gc do its work
    }

 其实就是把该index后从index+1开始的数组全部覆盖到从index开始的位置，等于将整个数组左移了一位，所有移动的数量是numMoved。 然后再将数组最后一位清空。

 

填加：

    public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

 可以看到在填加元素时，首先检查是否需要对数组扩容，如果没问题，则将元素加入到目前数组的size++的位置，既加入到ArrayList的末尾。size是类级变量，java中int初始化给了默认值0。

检查容量的源码为：

    public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 比较时检查数组目前长度与传入的所需size，如果长度不够，则做扩容，扩容用目前长度的1.5倍来计算。 这里源码中还额外计算了最小容量与新容量的大小，使增加后的数组长度能到一个合理的大小。

新的数组数据用Arrays.copyOf方法进行克隆。 该方法还可以在程序员可以预估List大小时设定List的容量，减少其内部数组elementData的扩容次数。

 

List的特性与数组类似，内部实现也依赖于数组，并提供了更方便的方法，如增删时越界检查及自动扩容等，是JDK加强数组使用便利性的一种封装。