ArrayList源码学习

ArrayList是一种常见的顺序存储的线形表。基本特性就是查询快，增删慢，线程不安全。平常我们使用最多的就是add(),remove(),size()等。通过查看源码得知其中一个非常重要的变量是Object[] elementData。这个数组就是用来存放添加进去的数据的。所有的添加和删除都是在操作这个数组完成的。
1：add

public boolean add(E e) {
        //   确保内部有足够的空间添加元素
        ensureCapacityInternal(size + 1);  
        //  把元素添加到数组的末尾
        elementData[size++] = e;
        return true;
    }

可以看到add方法内部很简单，一共就两行代码。看到注释我们知道第一个方法是来计算是否有剩余的空间的，那么ArrayList是怎么保证数组有足够的空间来存放数据的呢？

private void ensureCapacityInternal(int minCapacity) {
       // 如果是空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 取DEFAULT_CAPACITY和minCapacity当中最大的一个
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }  
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //  元素的个数大于此刻数组的长度
        if (minCapacity - elementData.length > 0)
          // 扩容
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // 数组长度
        int oldCapacity = elementData.length;
        // 新的长度为1.5倍的原数组的长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 把数组扩容并赋值给原来的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

接下来看ArrayList是怎么删除一个元素的。

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        modCount++;
      //   从数组中取出要删除的元素
        E oldValue = (E) elementData[index];
       //   计算出要复制的长度
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; 
        return oldValue;
    }

比如删除前数组的元素为[0,1,2,3,4,5]。假如要移除的元素index为2，那么move()方法中所做的事情就是先取出来元素，也就是代码中的oldValue = 2；然后计算需要复制的长度，也就是numMoved=6-2-1=3；而System.arraycopy()所做的事情就是在上面的数组中计算从索引3开始（包含索引3）往后数numMoved个数，也就是3,4,5。然后放入目标数组中，目标数组也是elementData，所以目标数组中的元素也是[0,1,2,3,4,5]。从索引2开始（包含索引2）的位置开始依次放入，那么最后拿到的数组中的元素就是[0,1,3,4,5,5]。最后把--size，也就是索引为5的元素置空，最后返回oldValue。
可以看到ArrayList添加或者删除元素的时候都需要进行计算，并且需要进行数组的拷贝，这也就是为什么ArrayList增删操作的时候效率低了。
在实际的使用中，经常会用到for循环去添加或者删除某个元素。如果用的是for-each循环的话，就会抛出一个ConcurrentModificationException异常。这是因为for-each循环是使用的迭代器原理，而ArrayList迭代器中有一个expectedModCount变量，是由Arraylist当中modCount直接赋值的。而modCount是无论在添加和删除的时候都会进行modCount++操作的。当你在for-each进行增删的modCount就会进行修改导致变量不相等而抛出异常。所以需要使用iterator来进行。

  List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer integer = iterator.next();
            if (integer == 2)
                iterator.remove();
        }

这是因为在Iterator的remove()方法中会重新对expectedModCount进行赋值，所以才避免了此问题。