大家天天在用List，ArrayList一般来讲应该是程序员用的最多的集合类了。

我们今天研究一下ArrayList。

总体来讲，从底层数据结构或者源码的角度看，List比Map或者Set要简单。

底层数据结构

ArryList其实就是可变长数组。

初始化的时候，可以指定容量，不指定容量的话，ArrayList被初始化为空数组，首次存入数据的时候才进行容量初始化，初始化最小容量为10。

ArrayList的容量控制

每次存入数据到ArrayList的时候，首先检查容量：

private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}

如果ArrayList容量不能满足本次数据存储的要求的话，调用grow方法扩容：

private void grow(int minCapacity) {// overflow-conscious codeint 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);}

grow方法首先检查原容量扩容1.5倍是否能满足要求，能满足则扩容到原来的1.5倍，否则扩容到能满足数据存入要求的容量。

扩容后调用Arrays.copyOf(elementData, newCapacity)把旧的数据copy到扩容后的新数组。Arrays.copyof方法其实也是调用System.arraycopy方法完成copy。

数据存入

调用add（E e）方法在ArrayList尾部追加数据。
调用addAll(Collection<? extends E> c)在ArrayList尾部追加集合c中的所有数据。

ArrayList支持追加数据到其指定位置（通过调用方法add(int index, E element)），底层通过调用System.arraycopy方法实现。

研究ArrayList源码会发现其中大量使用System.arraycopy方法，所以，虽然ArrayList其实就是数组操作，但是性能也不至于太差。

获取数据

使用ArrayList的时候我们一般会有两种获取数据的需求，一种就是获取指定位置的数据，通过get(int index)方法获取，因为ArrayList其实就是数组，所以，获取指定位置的数据效率非常高，时间复杂度为O(1)。

另外一种就是判断是否包含某一数据，调用contains(Object o)方法：

public boolean contains(Object o) {return indexOf(o) >= 0;}public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}

其实猜都能猜到他必须要遍历数组了，所以效率不会太高。

其他

读源码的目的除了从底层彻底了解其工作原理之外，还有一个重要的目的就是学习最最NB的JAVA程序员的编码思想和习惯。

比如释放内存：

   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}

比如代码重用：

    public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, false);}

retainAll是只保留参数集合中的数据，removeAll则正好相反，移除参数集合中的数据，两个方法目的正好相反，则通过调用batchRemove、传递complement为true或false达到目的。

值得每个尤其是新手程序员认真学习。

晚安！