2.2 List集合的一种典型实现——ArrayList类_Java修炼指南：高频源码解析-QQ阅读男生都市网

书名：Java修炼指南：高频源码解析
作者名：开课吧组编曹子方杨富杰刘常凯等编著
本章字数：2626字
更新时间：2021-04-22 17:10:54

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类中的返回方法，代码如下所示。