2.2 List集合的一种典型实现——ArrayList类
ArrayList就是动态数组，用MSDN中的说法，就是Array的复杂版本，它提供了如下一些好处：动态地增加和减少元素，实现了ICollection和IList接口以及灵活地设置数组的大小。在面试时候通常会被问到：数组和ArrayList的区别是什么？ArrayList的底层是什么？ArrayList线程是否安全，为什么？
关于这些问题，熟悉源码后就迎刃而解了。本节将重点介绍ArrayList类是如何实现的。
2.2.1 ArrayList定义
ArrayList是一个用数组实现的集合，支持随机访问，元素有序且可以重复。ArrayList类结构如图2-2所示。
●图2-2 ArrayList类结构图
1. 实现RandomAccess接口
这是一个标记接口，一般此标记接口用于List实现，以表明它们支持快速（通常是恒定时间）的随机访问。该接口的主要目的是允许通用算法改变其行为，以便在应用于随机或顺序访问列表时提供良好的性能。
比如在工具类Collections（这个工具类后面会详细讲解）中，应用二分查找方法可以判断是否实现了RandomAccess接口：
2. 实现Cloneable接口
这个类是Java. lang. Cloneable，学习Java深拷贝和浅拷贝原理时，知道浅拷贝可以通过调用Object. clone()方法来实现，但是调用该方法的对象必须要实现Cloneable接口，否则会抛出CloneNoSupportException异常。
Cloneable和RandomAccess接口也是一个标记接口，接口内无任何方法体和常量的声明，如果想克隆对象，必须要实现Cloneable接口，表明该类是可以被克隆的。
3. 实现Serializable接口
该接口也是标记接口，表示能被序列化。
4. 实现List接口
这个接口是List类集合的上层接口，定义了实现该接口的类都必须要实现的一组方法，如下所示，下面对这一系列方法的实现做详细介绍。
2.2.2 字段属性
字段属性代码如下：
2.2.3 构造函数
构造函数代码如下：
此无参构造函数将创建一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA声明的数组，注意此时初始容量是0，而不是很多人认为的10。
注意：
根据默认构造函数创建的集合，ArrayList list = new ArrayList()；此时集合长度是0。
初始化集合大小创建ArrayList集合。当大于0时，给定多少就创建多大的数组；当等于0时，创建一个空数组；当小于0时，抛出异常。
以上代码即将已有的集合复制到ArrayList。
2.2.4 添加元素
通过前面的字段属性和构造函数，可以看出ArrayList集合是由数组构成的，那么向ArrayList中添加元素，也就是向数组赋值。众所周知一个数组的声明是能确定大小的，而使用ArrayList时，需要能添加任意多个元素，这就涉及数组的扩容。
扩容的核心方法就是调用Arrays. copyOf方法，来创建一个更大的数组，然后将原数组元素拷贝过去即可。下面看具体实现：
如上所示，在通过调用add方法添加元素之前，要首先调用ensureCapacityInternal方法来确定集合的大小，如果集合满了，则要进行扩容操作。
在ensureExplicitCapacity方法中，首先对修改次数modCount加一，这里的modCount给ArrayList的迭代器使用，在并发操作被修改时，提供快速失败行为（保证modCount在迭代期间不变，否则抛出ConcurrentModificationException异常），可以查看源码865行，接着判断minCapacity是否大于当前ArrayList内部数组长度，大于则调用grow方法对内部数组elementData扩容，grow方法代码如下：
对于ArrayList集合添加元素，总结如下：
1）当通过ArrayList()构造一个空集合，初始长度是为0的，第1次添加元素，会创建一个长度为10的数组，并将该元素赋值到数组的第一个位置。
2）第2次添加元素，集合不为空，而且由于集合的长度size+1是小于数组的长度10，所以直接添加元素到数组的第二个位置，不用扩容。
3）第11次添加元素，此时size+1 = 11，而数组长度是10，这时候创建一个长度为10+10∗0. 5 = 15的数组（扩容1. 5倍），然后将原数组元素引用拷贝到新数组。并将第 11次添加的元素赋值到新数组下标为10的位置。
4）第Integer. MAX_VALUE - 8 = 2147483639，然后 2147483639%1. 5=1431655759（这个数是要进行扩容）次添加元素，为了防止溢出，此时会直接创建一个 1431655759+1大小的数组，这样一直，每次添加一个元素，都只扩大一个范围。
5）第Integer. MAX_VALUE - 7次添加元素时，创建一个大小为Integer. MAX_VALUE的数组，在进行元素添加。
6）第Integer. MAX_VALUE + 1次添加元素时，抛出OutOfMemoryError异常。
注意：
可以向集合中添加null，因为数组可以有null值存在。
2.2.5 删除元素
1. 根据索引删除元素
remove（int index）方法表示删除索引index处的元素，首先通过rangeCheck（index）方法判断给定索引的范围，超过集合大小则抛出异常；接着通过System. arraycopy方法对数组进行自身拷贝。
2. 直接删除指定元素
remove（Object o）方法是删除第一次出现的该元素。然后通过System. arraycopy进行数组自身拷贝。
2.2.6 修改元素
通过调用set（int index，E element）方法将指定索引index处的元素替换为element，并返回原数组的元素。
2.2.7 查找元素
1. 根据索引查找元素
同理，该方法首先还是判断给定索引的合理性，然后直接返回处于该下标位置的数组元素。
2. 根据元素查找索引
注意：
indexOf（Object o）方法是返回第一次出现该元素的下标，如果没有则返回 -1。
还有lastIndexOf（Object o）方法是返回最后一次出现该元素的下标。
2.2.8 遍历集合
1. 普通for循环遍历
前面介绍查找元素时，可以通过get（int index）方法，根据索引查找元素，普通for循环遍历同理。
2. 迭代器iterator
先看看ArrayList的具体用法，代码如下所示。
在介绍ArrayList时，该类实现了List接口，而List接口又继承了Collection接口，Collection接口又继承了Iterable接口，该接口有个Iterator＜T＞iterator()方法，能获取Iterator对象，并能用该对象进行集合遍历，为什么能用该对象进行集合遍历？先看看ArrayList类中的返回方法，代码如下所示。
该方法是返回一个Itr对象，这个类是ArrayList的内部类。
注意：
在进行next()方法调用的时候，会进行checkForComodification()调用，该方法表示迭代器进行元素迭代时，如果同时进行增加和删除操作，会抛出ConcurrentModification Exception异常。比如：
解决办法是不调用ArrayList. remove()方法，转而调用迭代器的remove()方法。
这种语法可以看成是JDK的一种语法糖，通过反编译class文件，可以看到生成的Java文件，其具体实现还是通过调用Iterator迭代器进行遍历。示例代码如下所示。
3. 迭代器ListIterator
还是先看看ArrayList具体用法，示例代码如下所示。
ArrayList还能实现一边遍历，一边进行新增或者删除操作：
也就是说相比于Iterator迭代器，这里的ListIterator多出了能向前迭代以及能够新增元素。示例代码如下所示。
对于Iterator迭代器，查看JDK源码，发现还有ListIterator接口继承了Iterator。
该接口有如下方法：
在ArrayList类中，有如下方法可以获得ListIterator接口。
这里的ListItr也是一个内部类。
2.2.9 SubList方法
在ArrayList中有这样一个方法：
该方法作用是返回从fromIndex（包括）开始的下标，到toIndex（不包括）结束的下标之间的元素视图。示例代码如下所示。
这里出现了SubList类，这也是ArrayList中的一个内部类。
注意：
返回的是原集合的视图，也就是说，如果对SubList类中出来的集合进行修改或新增操作，那么原始集合也会发生同样的操作。
如想要独立出来一个集合，解决办法如下：
2.2.10 size()方法
通过size()方法返回集合的长度，一般是指元素的数量，代码如下所示。
注意：
返回集合的长度，而不是数组的长度，这里的size就是定义的全局变量。
2.2.11 isEmpty()方法
这个方法是判断集合是否为空，代码如下所示。
返回size == 0的结果。
2.2.12 trimToSize()方法
该方法用于回收多余的内存。即一旦确定集合不在添加多余的元素之后，调用trimToSize()方法会将实现集合的数组大小刚好调整为集合元素的大小。
注意：
该方法会花时间来复制数组元素，所以应该在确定不会添加元素之后再调用。