[TOC]
ArrayList
1 简介
继承自 AbstractList，实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速访问、复制、序列化的。
- RandomAccess:
标志接口，实现这个这个接口的 List 集合是支持快速随机访问的。也就是说，实现了这个接口的集合是支持 快速随机访问 策略的。
如果是实现了这个接口的 List，那么使用for循环的方式获取数据会优于用迭代器获取数据 - Cloneable:
克隆接口，同时也是标记接口，只有实现这个接口后，然后在类中重写Object中的clone方法，然后通过类调用clone方法才能克隆成功，如果不实现这个接口，则会抛出CloneNotSupportedException(克隆不被支持)异常。 - Serializable:
一个对象序列化的接口，一个类只有实现了Serializable接口，它的对象才能被序列化
2 源码开篇说明
List接口的可调整数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现List接口之外，该类还提供了操作内部用于存储列表的数组大小的方法。(这个类大致相当于Vector，只是它是非线程安全的。)
size、isEmpty、get、set、iterator和listIterator操作在常量时间内运行。加法运算在平摊常数时间内运行，也就是说，添加n个元素需要O(n)时间。所有其他操作都以线性时间运行(粗略地说)。与LinkedList实现相比，常量因子较低。
每个ArrayList实例都有一个容量。capacity是用于存储列表中元素的数组的大小。它总是至少和列表大小一样大。当元素被添加到ArrayList中时，它的容量会自动增长。除了添加元素的平摊时间成本是常数这一事实之外，没有指定增长策略的细节。
应用程序可以在使用ensureCapacity操作添加大量元素之前增加ArrayList实例的容量。这可能会减少增量重新分配的数量。
注意，这个实现不是同步的。如果多个线程同时访问一个ArrayList实例，并且至少有一个线程在结构上修改了这个列表，那么它必须在外部同步。(结构修改是任何添加或删除一个或多个元素的操作，或显式地调整后台数组的大小;仅仅设置元素的值并不是结构上的修改。)这通常是通过对自然封装列表的某些对象进行同步来完成的。如果不存在这样的对象，则应该使用Collections对列表进行“包装”。synchronizedList方法。这最好在创建时完成，以防止对列表的意外非同步访问:
列表列表=集合。synchronizedList(新ArrayList(…));
这个类的迭代器和listIterator方法返回的迭代器是快速失败的:如果在创建迭代器之后的任何时间，列表的结构被修改，除了通过迭代器自己的remove或add方法，迭代器将抛出ConcurrentModificationException。因此，在面临并发修改时，迭代器会快速而干净地失败，而不是在未来不确定的时间冒着任意、不确定行为的风险。
请注意，迭代器的快速失败行为不能得到保证，因为通常来说，在存在非同步并发修改的情况下，不可能做出任何硬保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此，编写一个依赖于此异常的程序来保证其正确性是错误的:迭代器的快速失败行为只能用于检测bug。
This class is a member of the Java Collections Framework.
自从: 1.2
请参阅: Collection, List, LinkedList, Vector
作者: Josh Bloch, Neal Gafter
类型参数: – the type of elements in this list
3 成员变量
ArrayList 底层是基于数组来实现容量大小动态变化的
// 数组列表的大小(包含元素的数量)
private int size; // 实际元素个数
transient Object[] elementData; size 是指 elementData 中实际有多少个元素
elementData.length 为集合容量，表示最多可以容纳多少个元素
默认初始容量大小为 10
private static final int DEFAULT_CAPACITY = 10;这个变量是定义在 AbstractList 中的。记录对 List 操作的次数。主要使用是在 Iterator，是防止在迭代的过程中集合被修改
protected transient int modCount = 0;下面这两个变量是用在构造函数中
第一次添加元素时知道该 集合容量 从空的构造函数还是有参构造函数被初始化的，以此确认如何扩容
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};4 三种构造的方式
无参构造函数
/**
* Constructs an empty list with an initial capacity of ten.
* 构造一个初始容量为10的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}虽然注释说，构造一个初始容量是10的空列表，但是这里的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空值
其实容量是在第一次添加元素的时候进行扩大到10
有参构造函数，传整数，确认集合的容量大小
假如通过这种方式构造，会初始化数组大小，但是List的大小没有变，因为list的大小是返回size的。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object 数组并赋值给 elementData
当 initialCapacity 为零时则是把 EMPTY_ELEMENTDATA 赋值给 elementData
使用指定 Collection 构造 ArrayList 的构造函数
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}5 总结性的一些话
ArrayList就是个数组列表，特点是查询访问元素的速度比较快，插入删除的速度比较慢
且线程不安全
扩容方式
如果在构造时采取默认构造，底层会默认赋一个空数组，所以数组容量为0
只有真正对数据进行添加add时，才分配默认DEFAULT_CAPACITY = 10的初始容量。
扩容的时候，他是通过数组扩容的方式实现的，当进行新增操作的时候，发现集合满了
就会重新定义一个长度是原来1.5倍的数组，把原数组的数据进行赋值到新数组中，再把地址指向修改到新数组
1.7版本开始的变化
初始化时，1.7以前会调用this(10)进行真正的初始化容量10，但是1.7后无参构造默认走了空数组的方式
在扩容时，新版本的效率更高，采用了位移运算
1.7的时候3/2+1
1.8直接就是3/2 （位运算）
新增元素
可以指定下标位置新增，也可以直接新增
新增元素前，进行校验长度判断，长度不够时需要进行扩容，size自增+1
假如指定下标新增，效率会变低，为什么呢？
通过指定下标新增时，会复制多一个长度+1的数组，将下标+1后的元素赋值上去
腾出位置后，再放入指定新增的元素到指定位置
删除
ArraysList插入删除的速度取决于进行变更的元素距离末端数组有多远
因为他插入和删除一样，都是在copy多一个数组
ArrayList适合做队列吗
队列一般是FIFO（先入先出）的，如果用ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数组，反过来也可以。
但是无论如何总会有一个操作会涉及到数组的数据搬迁，这个是比较耗费性能的。
结论：ArrayList不适合做队列。
数组适合做队列吗
数组是非常合适的。
比如ArrayBlockingQueue内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的。
另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列，具体原理不做解释，比较复杂。
简单点说就是使用两个偏移量来标记数组的读位置和写位置，如果超过长度就折回到数组开头，前提是它们是定长数组。
ArrayList的遍历和LinkedList遍历性能比较如何？
论遍历ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。