深入java集合类系列：ArrayList

   ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小，下面将从ArrayList的属性及相关方法进行概述

属性

private transient Object[] elementData;

 为实际数据的存储对象，可以看出ArrayList实际存储数据对象为对象数组，所以ArrayList实际为对对象数组操作的封装,从这里我们也可以看出ArrayList没有容量限制。 

 private int size;

 当前对象数组中已经存在元素个数size小于等对象数组的大小，

创建

ArrayList API提供了三种构造方法，常用的两种如下

    public ArrayList() {
	//调用ArrayList(int initialCapacity)
	this(10);
    }
    public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	//创建存储数据对象
	this.elementData = new Object[initialCapacity];
    }

 对于默认的new ArrayList()来说，可以分析得到创建默认大小的object数组，数组的初始化大小为10，默认创建时size未赋值，因是类变量size将初始为0；

增加元素

   public boolean add(E e) {
	//校验数组容量
	ensureCapacity(size + 1);  // Increments modCount!!
	//将数据对象插入到数组的size末端
	elementData[size++] = e;
	return true;
    }
	//插入指定位置的元素
	public void add(int index, E element) {
	//索引>size或索引小于0直接抛出异常
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
	ensureCapacity(size+1);  // Increments modCount!!
	//将index后面的数据后移一位
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	//将数据插入到指定index位置
	elementData[index] = element;
	//size加一
	size++;
    }
	public void ensureCapacity(int minCapacity) {
	modCount++;
	//原有数组容量大小
	int oldCapacity = elementData.length;
	//插入的索引位置大于数组容量，增大数组容量
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
		//数组容量增大，按照原数组容量大小0.5增加
	    int newCapacity = (oldCapacity * 3)/2 + 1;
		//增大的容量如果还是小于插入的索引位置，将索引直接赋值给新的数组容量
		if (newCapacity < minCapacity)
			newCapacity = minCapacity;
		//将数组按照新的数组容量进行扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 增加是先校验底层的对象数组是否能再添加元素，如果没法添加，先将对象数组进行扩容【要进行一次数组拷贝】，扩容因子为0.5。再进行插入。如果能添加元素，直接将数据插入到size对应的索引位置。如果插入到指定位置将会涉及到数组元素的后移【进行一次数组拷贝】，相关请看add(int index, E element)注解。同时我们也可以发现对于NULL值和重复值也未进行处理。

读取元素

    public E get(int index) {
	RangeCheck(index);//校验index大小
	return (E) elementData[index];//获取index位置的数据
    }
    private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }

 读取最简单就是从对象数组中将对应索引位置的数据读取出来。读取的索引小于size。

删除

    public E remove(int index) {
	RangeCheck(index);//检查index大小
	modCount++;
	E oldValue = (E) elementData[index];//标记删除位置的值
	int numMoved = size - index - 1;//计算删除索引到size剩入数据
	if (numMoved > 0)//如果剩入数据大于0，则将index后的数据进行前移。
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; //将size大小-1，并将elementData的原来索引位置为size-1的数据清空。
	return oldValue;
    }

 删除涉及到数组的前移，前移的数据范围为删除索引的值+1到size-1的元素。注意我们发现删除并未和写入时一样进行对象数组的大小的自动收缩【即存储容量未发生变化】。

按照元素值进行删除

   public boolean remove(Object o) {
		if (o == null) {
			//遍历数组，发现第一个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;
    }

	 private void fastRemove(int index) {
        modCount++;
		//计算要前移动的数据个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
			//进行数组拷贝将index后数据前移一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
		//size-1并将size-1索引位置的元素清空，
        elementData[--size] = null; // Let gc do its work
    }

 按照元素值进行删除，会遍历数组对象，遍历元素个数为删除元素的索引index+1，且只会删除该元素值出现第一个。并且在删除是，对象数组会进行拷贝，拷贝元素个数为size-index-1。

压缩对象数组存储容量

    public void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	//当前数组的大小小于当前数组存储大小进行压缩
	if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
	}
    }

  压缩的时候是以size为标准，将对象数组的大小压缩为size一样大小。

清空

    public void clear() {
	modCount++;
	// 将数组中数据清空
	for (int i = 0; i < size; i++)
	    elementData[i] = null;
	//将size大小设置为0
	size = 0;
    }

清空主要进行两件事情：（1）：将相关的数据元素设置为NULL值。（2）：将size设置为0

其他的不做介绍了，ArrayList主要是针对对象数组的操作，主要围绕size展开。

总结：

（1）：ArrayList的实际存储对象为一个数组对象。没有容量大小，可以无限增加【扩展因子为0.5】，只受JVM内存大小限制。

（2）：ArrayList中可以包含重复的元素，并可以存储NULL值。

（3）：ArrayList的所有方法都是非线程安全的。

（4）：ArrayList的索引访问和元素更新方面有着非常优秀的性能，因为不需要花费精力做范围检查,所以从ArrayList的末端添加元素，删除元素也有着非常优秀的性能，除非ArrayList的存储容量不足而需要扩展内部数组的长度【扩展的时候需要数组拷贝】。插入和删除数据需要一个数组的拷贝，需要拷贝的元素数量是ArrayList的元素长度（size-1）减去索引号，对插入来讲，插入元素到ArrayList的第一个元素位置的性能最差，插入到最后一个位子的性能最好，数组拷贝所需的时间会根据元素的数量增加而显著增加。

（5）：ArrayList查找指定位置的数据时间为O(1),插入到指定位置的数据时间为O(size-index-1)。

（6）：ArrayList插入大量的元素，提前指定ArrayList的大小，防止在插入过程ArrayList进行扩容。

（7）：ArrayList按照元素值进行删除时，会遍历数组对象，并且会进行数组拷贝，时间为O(index+1)+O(size-index-1），可以计算总共花费O(size),遍历的对象+拷贝的对对象就等于元素个数。

 

（8）：ArrayList删除时，不会调整原有的数组存储容量的大小即在数组存储容量扩容的后删除所用扩容数据后也不会调整整个数组容量大小，手工调用trimToSize进行调整。