1.1 List集合概要和重要接口介绍
JCF中的List集合涉及的部分重要接口、抽象类和具体实现类（包括java.util.ArrayList、java.util.LinkedList、java.util.Vector和java.util.Stack），如图1-1所示。
图1-1
其中java.util.Vector集合和java.util.Stack集合之间是继承关系，它们从JDK 1.0开始就供开发人员使用，后来又被性能和设计更好的集合代替。例如，从名字就可以看出是后进先出（LIFO）性质的java.util.Stack集合，在其自身的文档中（JDK 1.7+）已建议开发者优先使用性能更好的java.util.ArrayDeque集合作为代替方案（后续会进行详细介绍）。但是本节仍然会介绍java.util.Vector集合和java.util.Stack集合，因为本书主要分析Java源码的设计思想，以便读者将这些设计思想应用到实际工作中。
要理解java.util包中关于java.util.List接口的重要实现类，首先要搞清楚其上层和下层涉及的主要接口（如java.lang.Iterable接口、java.util.Collection接口）、抽象类（如java.util.AbstractList抽象类、java.util.AbstractSequentialList抽象类）及其功能特性。
1.1.1 java.lang.Iterable接口
List、Set、Queue集合的上层都需要继承java.lang.Iterable接口，如图1-2所示。
图1-2
根据java.lang.Iterable接口自带的注释描述，实现该接口的类可以使用for each循环语句进行操作处理。但实际上该接口还提供了两个操作方法（JDK 1.8+），分别为forEach(Consumer<? super T>action)方法和spliterator()方法。forEach(Consumer<? super T> action)方法的一般使用方法示例如下。
forEach(Consumer<? super T> action)方法中的Consumer接口定义在java.util.function包（由JDK 1.8+提供）中，其中包括大量函数式编程功能，java.util.function.Consumer接口就是其中之一，该接口表示消费某个对象。
1.1.2 java.util.Collection接口
java.util.Collection接口是一个非常关键的接口，如果读者仔细观察java.util包中的源码结构，就会发现该接口并没有直接的实现类。实现了该接口的下级类或接口，以及聚合该接口工作的下级类或接口，都属于JCF的一部分（可以大概理解为JCF中的集合不一定实现了该接口，但实现了该接口的集合一定是JCF中的集合）。
间接实现java.util.Collection接口的类都是可以按照某种逻辑结构存储一组数据的集合，这种逻辑结构可以是链表（如LinkedList集合），也可以是固定长度的数组（如Vector集合），还可以是树结构（如TreeMap集合）；向外界的输出结果可以是有序的（如ArrayList集合），也可以是无序的（如HashSet集合）；可以是保证多线程下的操作安全性的（如CopyOnWriteArrayList集合），也可以是不保证多线程下的操作安全性的（如ArrayDeque集合）。
1.1.3 java.util.AbstractList抽象类
在JCF中，可以根据List集合在各维度上表现出来的工作特点对其进行分类，分类标准有三种：根据是否支持随机访问的特点进行分类，根据是否具有数据的可修改权限进行分类，根据集合容量是否可变进行分类。
根据是否支持随机访问的特点进行分类，可以将List集合分为支持随机访问（读）的List集合和不支持随机访问（读）的List集合。支持随机访问的List集合可以查询集合中任意位置的数据，并且所花费的时间不会改变（时间复杂度为O(1)）。
JCF中为List集合定义的“随机访问”和磁盘I/O中的“随机读”是有区别的（也有相似点），虽然二者表示的都是“可以在某个指定的独立位置读取数据”，但磁盘I/O描述的“随机读”属于硬件层面的知识点，注意区分；List集合定义的“随机访问”需要从算法的时间复杂度层面考虑。例如，如果使用数组结构作为List集合的基本结构，那么其找到指定索引位的时间复杂度为常量O(1)，这是因为可以直接定位到指定的内存起始位置，并且通过偏移量进行最终定位。因此，支持随机访问的List集合在数据读取性能方面远远优于不支持随机访问的List集合。
根据是否具有数据的可修改权限进行分类，可以将List集合分为可修改的List集合和不可修改的List集合。对于可修改的List集合，操作者可以在集合中的指定索引位上指定一个存储值。对于不可修改的List集合，操作者可以获取集合中指定索引位上的存储值，但不能对这个索引位上的值进行修改；操作者也可以获取当前集合的大小，但不能对当前集合的大小进行修改。
根据集合容量是否可变进行分类，可以将List集合分为大小可变的List集合和大小不可变的List集合。大小不可变的List集合是指在实例化后，大小就固定下来不再变化的List集合。大小可变的List集合的定义与之相反。
针对这三个维度的不同类型，开发人员可以定义不同操作特性的List集合。为了保证具有不同分类特点的List集合提供的操作方法符合规范，也为了减少开发人员针对不同分类特点的List集合的开发工作量，还为了向操作者屏蔽分类定义的细节差异，Java提供了java.util.AbstractList抽象类，继承该抽象类的各种具体的List集合只需根据自身情况重写java.util.AbstractList抽象类中的不同方法。例如，set(int)方法的功能是替换指定索引位上的数据对象，如果当前List集合不支持修改，则一定会抛出UnsupportedOperationException异常；对于不可修改的List集合，开发人员只需重写java.util.AbstractList抽象类中的get(int)方法和size()方法；如果开发人员自行定义一个大小可变的List集合，则只需重写add(int, E)方法和remove(int)方法；如果开发人员不需要实现支持随机访问的List集合，则可以使其继承java.util.AbstractSequentialList抽象类。
1.1.4 java.util.RandomAccess接口
java.util.RandomAccess接口是一种标识接口。标识接口是指Java中用于标识某个类具有某种操作特性、功能类型的接口。Java中有很多标识接口，如java.lang.Cloneable接口、java.io.Serializable接口。
标识接口通常不需要下层类实现任何方法。例如，java.lang.Cloneable接口的源码中没有任何需要实现的方法描述，其源码如下。
前面已经提到，List集合中有一组具体集合，支持集合中数据对象的随机访问，包括java.util.ArrayList集合、java.util.Vector集合和java.util.concurrent.CopyOnWriteArrayList集合。java.util. RandomAccess标识接口主要用于向调用者表示这些List集合支持集合中数据对象的随机访问，如图1-3所示。
图1-3
根据图1-3可知，java.util.ArrayList集合、java.util.Vector集合和java.util.concurrent.CopyOnWriteArrayList集合都实现了java.util.RandomAccess接口，表示它们支持集合中数据对象的随机访问。实现java.util.RandomAccess接口的还有很多第三方类库，如一些厂商封装的JSON工具中的JSONArray类。这些实现了java.util.RandomAccess标识接口的List集合在工作时也会被区别对待，如下所示。
以上源码片段中有一个隐藏的知识点，即instanceof修饰符在JDK 14、JDK 15中的用法：从JDK 14开始，Java为instanceof修饰符提供了一个新的使用方法——模式匹配。模式匹配可以有效减少程序员在使用instanceof修饰符时的机械化源码，示例如下。
上述示例代码来自java.util.Collections类（注意不是java.util.Collection接口，Collections类是JCF中提供的一种工具类，二者命名相似，但意义完全不同）中的fill()方法，该方法主要用于向List集合填充默认的Object对象数据。在这个方法中，如果当前指定的List集合支持随机访问，则优先使用for()循环定位并填充/替换集合中的每个索引位上的数据对象。如果当前指定的List集合不支持随机访问，但集合中的数据对象数量少于FILL_THRESHOLD（常量，默认值为25），则仍然使用for循环依次填充/替换每个索引位上的数据对象；如果不支持随机访问的集合拥有较多数据对象数量，则使用ListIterator迭代器顺序定位并填充/替换集合中的每个索引位上的数据对象。
为什么会出现这种处理逻辑呢？这主要是因为支持随机访问的集合对set()方法的实现方式与不支持随机访问的集合对set()方法的实现方式不一样，前者可以基于随机访问特性快速定位到指定的索引位，而后者不能。
LinkedList集合是一种不支持随机访问的集合。下面以LinkedList集合为例，看一下不支持随机访问的集合对set()方法的实现方式，源码如下。需要注意的是，LinkedList集合的内部结构是一个双向链表，后续章节还会专门介绍LinkedList集合。
LinkedList集合的内部结构是一个双向链表，要寻找链表中某个索引位上的数据对象，只能从头部或尾部依次查询，如图1-4所示（在实际使用时，综合客观情况后的时间复杂度可能更高）。
图1-4
这样我们就可以在java.util.Collections类的fill()方法中复盘，如果需要被填充/替换数据对象的LinkedList集合中的数据对象数量并不多（少于25个），则如何进行LinkedList集合中的数据对象填充/替换操作，如图1-5所示。
图1-5
根据图1-5可知，每次调用set(int, E)方法，LinkedList集合都需要重新定位指定的索引位，当LinkedList集合中的数据对象数量不多时，这种缺陷不会对性能造成过多浪费。
ArrayList集合是一种支持随机访问的集合。下面以ArrayList集合为例，看一下支持随机访问的集合对set()方法的实现方式，源码如下。后续章节会详细介绍ArrayList集合。
ArrayList集合本质上是一个数组，要寻找数组中某个索引位上的数据对象，无须从头依次查询。JVM会根据数据对象在内存空间中的起始位置和数组位置的偏移量直接找到这个索引位上的数据对象引用。因此，在java.util.Collections类的fill()方法中，ArrayList集合的数据对象填充过程如图1-6所示。
图1-6
在图1-6中，调用ArrayList集合中的set(int,E)方法，进行一次遍历即可完成所有数据对象的填充/替换操作。
很显然，ArrayList集合在数据对象填充/替换场景的设计效果要优于LinkedList集合，这主要得益于ArrayList集合对随机访问的支持，本质上得益于ArrayList集合内部数组结构的设计方式。一个显而易见的效果是，无论使用java.util.Collections.fill()方法填充/替换的ArrayList集合中有多少数据对象，其操作性能都非常高。
前面讨论的都是集合中数据对象数量不多的情况。如果不支持随机访问的集合拥有较多的数据对象数量，那么是否有比较合理的数据对象填充/替换方法呢？显然是有的，这就是fill()方法中的另一半源码逻辑——使用集合的迭代器功能依次对每个索引位上的数据对象进行填充/替换操作。
使用迭代器的好处在于，可以帮助不支持随机访问的集合避免不必要的索引位查询操作。在每次调用next()方法时，迭代器都可以基于上一次操作的索引位继续寻找下一个索引位，而不需要重新从第一个索引位进行查询。
下面看一下在List集合默认的上层抽象类java.util.AbstractList中，list.listIterator()方法返回的ListIterator迭代器是如何实现next()方法的，源码如下。
根据以上源码可知，在next()方法中使用全局变量cursor记录了当前处理的索引位，当再次调用next()方法时，只需将cursor代表的索引值加1，如图1-7所示。
图1-7
在本节中，我们对支持随机访问和不支持随机访问的List集合在访问性能上的工作差异进行了介绍。实际上，典型的ArrayList集合和LinkedList集合的性能差异不止于此，后面会进行详细说明。