1.1　List集合概要和重要接口介紹

JCF中的List集合涉及的部分重要接口、抽象類和具體實現類（包括java.util.ArrayList、java.util.LinkedList、java.util.Vector和java.util.Stack），如圖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所示。

根據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可知，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所示（在實際使用時，綜合客觀情況后的時間復雜度可能更高）。

這樣我們就可以在java.util.Collections類的fill()方法中復盤，如果需要被填充/替換數據對象的LinkedList集合中的數據對象數量并不多（少于25個），則如何進行LinkedList集合中的數據對象填充/替換操作，如圖1-5所示。

根據圖1-5可知，每次調用set(int, E)方法，LinkedList集合都需要重新定位指定的索引位，當LinkedList集合中的數據對象數量不多時，這種缺陷不會對性能造成過多浪費。

ArrayList集合是一種支持隨機訪問的集合。下面以ArrayList集合為例，看一下支持隨機訪問的集合對set()方法的實現方式，源碼如下。后續章節會詳細介紹ArrayList集合。

ArrayList集合本質上是一個數組，要尋找數組中某個索引位上的數據對象，無須從頭依次查詢。JVM會根據數據對象在內存空間中的起始位置和數組位置的偏移量直接找到這個索引位上的數據對象引用。因此，在java.util.Collections類的fill()方法中，ArrayList集合的數據對象填充過程如圖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所示。

在本節中，我們對支持隨機訪問和不支持隨機訪問的List集合在訪問性能上的工作差異進行了介紹。實際上，典型的ArrayList集合和LinkedList集合的性能差異不止于此，后面會進行詳細說明。