ArrayList源码解析

       ArrayList和HashMap、LinkedList一样，是常用的数据结构。ArrayList提供了一个动态数组，弥补了数组的长度固定，增加元素操作消耗大的不足。但因为ArrayList存储了对象数组，构造对象也造成了性能开销，所以相对布言，如果数组的长度可知，使用数组的效率最高，反之则可使用ArrayList。

 ArrayList内部使用Object[]存储数据

    private transient Object[] elementData;

 ArrayList使用Obect数组elementData来存储数据，这样可以存储任意类型的数据。

 构造函数

    public ArrayList() {
	this(10);
    }

 默认构造函数的数组的容量为10。

 ArrayList添加元素

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

 添加元素时，元素添加到ArrayList容器的尾部。

 在添加元素之前，先判断数组的容量是否需要扩容ensureCapacity（size+1），传的参数是当前数组的size+1。

确保ArrayList容器容量

    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);
	}
    }

 在ensureCapacity方法中，先把参数（新索引值）minCapacity与数组容器的原长度oldCapacity做比较，如果参数minCapacity大于原长度，就说明数组已经饱和，需要进行扩容。

扩容的具体实现是把原来的长度增加50%再增加1，然后，把旧数组的数据拷贝到新数组里（使用System.arrayCopy（）实现）。

在指定位置(index)添加元素

    public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);  // Increments modCount!!
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
    }

 实现流程也是先判断数组需不需要扩容，然后把从index往后面的数组元素，向后移动一位。再把index位置的数组元素的引用赋予要插入的元素。

查找指定位置(index)的元素

    public E get(int index) {
	RangeCheck(index);

	return (E) elementData[index];
    }

 查找元素的方法比较简单，先是查看索引index值是否越界，如果在范围之内，直接返回数组的该索引元素。

从数组的指定位置index删除元素

    public E remove(int index) {
	RangeCheck(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; // Let gc do its work

	return oldValue;
    }

 在ArrayList中删除指定位置的元素时，如果这个index不是数组的最大下标位置，就把index之后的所有元素向前移动一位，来填充index位置的元素移除后的空白。

总结：

        ArrayList是一个动态数组数据结构，可以灵活地添加元素，查找性能好，而在指定位置添加和删除元素时性能下降，因为要移动数组的数据。所以ArrayList适用于查找多，而在数组内指定位置操作少的场景。