List实现之ArrayList

??????? List的主要实现类为：AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector.

??????? 大多数情况我们实现List这个接口时使用的是ArrayList这个类，ArrayList类是List 接口的大小可变数组的实现，所以ArrayList的字面意思就是“数组列表”的意思。ArrayList实现了List接口所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

??????? 下面就从ArrayList的使用和内部实现几个方面来深入学习一下ArrayList：

?

??????? 1.ArrayList初始化

??????? 使用ArrayList之前需要先实例化，代码如下：

List list=new ArrayList();
或
ArrayList list=new ArrayList();

?

??????? 一般情况下我们都是使用默认构造方法来实例ArrayList，ArrayList的默认构造方法源代码如下：

//ArrayList内部是以一个对象数组形式实现，transient作用是放弃序列化
private transient Object[] elementData;
/**
 * 构造一个空的list时，初始容量为10
 */
public ArrayList() {
	this(10);
}

/**
 * 构造一个空的list时，初始容量为指定值
 */
public ArrayList(int initialCapacity) {
	super();
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
	this.elementData = new Object[initialCapacity];
}

??????? 当我们利用默认构造方法实例化一个 ArrayList时，看到默认构造方法中调用了另一个重构方法，并指定了其默认大小为10，也就是说在不指定 ArrayList大小时，其内部实现数组的默认长度为10。

??????? 当然我们也可以在实例化时指定ArrayList的大小：

int size=20;
List list=new ArrayList(size);
或
ArrayList list=new ArrayList(size);

??????? 实例化时指定ArrayList大小的好处就是减少其内部数组因元素个数超出数组大小时进行扩容所消耗掉的性能。

?

??????? 2.ArrayList的成员变量

??????? ArrayList类只有两个成员变量：elementData与size：

/**
 * 用来存储ArrayList实例所添加的元素
 * ArrayList的 capacity（容量）等于该数组的长度
 */
private transient Object[] elementData;

/**
 * ArrayList的size （也就是ArrayList实例所含有的元素个数）.
 */
private int size;

??????? size很好理解，就是ArrayList的长度大小，也可理解为ArrayList中已添加的元素个数，这里需要注意：ArrayList允许添加为null的元素，所以null也会占用一份空间。

??????? elementData就是ArrayList的内部数组实现，它是一个一维对象数组。当通过add方法向ArrayList中添加元素时，这些元素就会被依次存储于elementData这个数组中。

??????? elementData既然是数组，它必然拥有长度length，那么这个数组的长度是否等于ArrayList的size？?

??????? 这里就需要了解一些ArrayList的相关设计概念：

??????? 首先作为ArrayList的内部实现数组elementData具备一定的长度（初始值为10），此长度又被称为capacity（容量）。

??????? 而每一个ArrayList实例又具有一个size，此size是该实例的列表长度，这其中capacity永远等于数组elementData的长度，并永远大于等于列表size。

??????? 所以capacity可以理解为ArrayList的容纳能力，而size可以理解为已使用的空间大小。

??????? 下面举一个生动的例子可能更好理解这两个概念：

?

??????? 我们可以把ArrayList理解为上图中的容器，这个容器初始的大小是10，容器的大小也就是上面所说的capacity。

??????? 此时我们使用这个容器，往容器中填充元素。其中所占用的空间就可以理解为size。

??????? 无论桶是空的还是正好盛满了水，容器的大小（capacity）都是不变的，而其中size会随着填充元素数量增加而增加，但最终只可能等于容器大小。

?

??????? 3.ArrayList的“可变大小”

??????? 之前已经重复了解了ArrayList的capacity与size两者的不同与所代表的意义。初始化的ArrayList容量为10，但是当我想填充超过10或更多的元素时怎么办？

??????? 原来的容器的大小是无法满足这个需求的，只有更换一个更大的容器来才容纳更多的元素。那么ArrayList又是如何实现这部分的呢？

??????? 首先需要先了解ArrayList添加元素的过程和处理方式，这样才能了解到以上两个问题的解决方法。

??????? 添加元素是通过add方法来完成的，所以我们要先分析下它的源码，以下是add方法的源代码：

/**
 * 添加指定元素至list末尾
 */
public boolean add(E e) {
	ensureCapacity(size + 1); // 增加modCount
	elementData[size++] = e;
	return true;
}

??????? add方法虽简单却比较重要，在添加元素至elementData数组前先要调用ensureCapacity方法来判断现elementData数组是否已经无法再添加新元素，如果还没有满则直接返回，如果已经满了则需要对elementData数组进行扩容，扩容后添加新元素。

??????? 之前已经了解到在初始化 ArrayList时我们可以指定其内部的数组长度，也就是 initialCapacity。只有在使用ArrayList，往里面添加元素时 size的值才会不断增加，直到与 capacity相等为止。

??????? 当 elementData所有索引位置均被填满元素的时候，此时的size=capacity。当再往其中添加新的元素时，此时原数组已经无法添加就需要扩充数组大小以满足新元素的添加。

??????? ensureCapacity方法的作用就是在必要时扩容elementData数组：

/**
 * 增加这个ArrayList实例的capacity，如果必要的话确保它可以容纳minCapacity数量的元素
 */
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);
	}
}

??????? 方法中 oldCapacity就是原数组的大小，minCapacity就是新数组最小的大小，也就是容纳所有元素所需的数组长度，如果 minCapacity已经大于了现使用数组的长度，则证明需要扩容。

?

??????? 将添加过程分成几个流程会更好的理解：

??????? 1）新建一个ArrayList实例，默认capacity为10：

List list=new ArrayList();

??????? 此时该实例内部如图：

??????? list内部数组elementData的length与capacity为10，list的size为0。

?

??????? 2）此时不断往list里添加元素，当元素个数不超过10时，elementData数组的大小并不会变化，当添加到第11个元素时：

List list=new ArrayList();
list.add(1);
...添加
list.add(10);
//添加10个元素后，此时capacity=10，size=10

//添加第11个元素
list.add(11);
//此时capacity=16，size=11

...添加
list.add(21);
//当添加至第21个元素时，此时capacity=31，size=21

??????? 可以看到capacity的增加幅度并不是每次都相同的，它是根据int newCapacity = (oldCapacity * 3) / 2 + 1;这个算法来计算的（原数组大小乘3再除以2，然后结果加1)，这样做最大的优点就是在满足一定容量的基础上，然后根据我们现有的数组长度去计算一个较为合适的增长幅度，这样可以在保证一定效率的情况下尽量满足元素的添加。

??????? 所以说ArrayList的每次add操作的开销上并不一定是相同的，它会有一定的线性增长过程，只有程序员更主动的去规划ArrayList的长度范围才能更好的避免这一问题。

?

??????? 4.获取元素

??????? ArrayList通过get方法获得指定index位置的元素内容，因为我们已经知道ArrayList的内部实现是数组，所以每次get方法调用只是返回该下标下的数组元素而已：

public E get(int index) {
	RangeCheck(index);//检查index值是否越界
	return (E) elementData[index];//直接返回该下标下的数组元素内容
}

??????? 在获取元素之前会先判断指定的index下标是否越界，通过校验之后返回该位置的元素内容。

?

??????? 5.移除元素

??????? 通过对ArrayList内部结构及实现方式的了解，当容器不足以容纳新元素时会进行扩容，当如果我们移除元素之后容器是否会“减容”呢？

??????? 最直接的办法就是查看源代码，下面是remove的源代码：

/**
 * 从列表中移除指定位置的元素，然后所有后续元素左移（下标减1）
 */
public E remove(int index) {
	//检查是否越界
	RangeCheck(index);
	modCount++;
	//原index位置元素
	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
	//返回原index位置元素
	return oldValue;
}

??????? remove方法中核心的部分就是System.arraycopy(elementData, index + 1, elementData, index, numMoved);这段代码，这段代码的作用就是从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。从 src 引用的源数组到 dest 引用的目标数组，数组组件的一个子序列被复制下来。被复制的组件的编号等于 length 参数。源数组中位置在 srcPos 到 srcPos+length-1 之间的组件被分别复制到目标数组中的 destPos 到 destPos+length-1 位置。

??????? 如果参数 src 和 dest 引用相同的数组对象，则复制的执行过程就好像首先将 srcPos 到 srcPos+length-1 位置的组件复制到一个带有 length 组件的临时数组，然后再将此临时数组的内容复制到目标数组的 destPos 到 destPos+length-1 位置一样。

arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

?