Java 有序集合 List 深度解析
在現代軟件開發中，Java 是一種廣泛使用的編程語言，其豐富的標準庫提供了多種數據結構來幫助開發者高效地管理和操作數據。其中，List 集合是一種非常常用的數據結構，它允許我們以有序的方式存儲和訪問元素。
本文將深入探討 Java 中的 List 集合，包括它的基本概念、主要實現類（如 ArrayList 和 LinkedList）、常見的操作方法以及優秀實踐。無論您是初學者還是有一定經驗的開發者，都能從本文中獲得有價值的知識和實用技巧。
Java集合的體系概覽
從Java頂層設計角度分類而言，集合整體可分為兩大類型：
第1大類是存放單元素的Collection，從源碼的注釋即可看出，該接口用于表示一組對象的抽象，該接口下的實現的集合空間或允許或不允許元素重復，JDK不提供此幾口的任何直接實現，也就是說，該接口底層有包括List、Set等接口的抽象實現：
The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered. The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set and List. This interface is typically used to pass collections around and manipulate them where maximum generality is desired.
第2大類則是存放鍵值對的Map，該類型要求鍵不可重復，且每個鍵最多可以到映射到一個值(注意這是從宏觀角度說的值，該值可以是一個對象、可以是一個集合)：
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
我們針對Collection接口進行展開說明，按照元素存儲規則的不同我們又可以分為:
- 有序不重復的Set集合體系。
- 有序可重復的LIst集合體系。
- 支持FIFO順序的隊列類型Queue。
對應的我們給出類圖：
同理我們將Map接口進行展開，他的特點就是每一個元素都是由鍵值對組成，我們可以通過key找到對應的value，類圖如下，集合具體詳情筆者會在后文闡述這里我們只要有一個粗略的印象即可：
詳解List集合體系知識點
1.List集合概覽
List即有序集合，該接口體系下所實現的集合可以精確控制每一個元素插入的位置，用戶可以通過整數索引定位和訪問元素：
An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
從底層結構角度，有序集合還可以有兩種實現，第一種也就是我們常說的ArrayList ，從ArrayList源碼找到的ArrayList底層存儲元素的變量elementData，可以看出ArrayList本質上就是對原生數組的封裝：
transient Object[] elementData;第2中則是LinkedList即雙向鏈表所實現的有序集合，它由一個個節點構成，節點有雙指針，分別指向前驅節點和后繼節點。
private static class Node<E> {
E item;
// 指向后繼節點
Node<E> next;
//指向前驅節點
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}Vector底層實現ArrayList一樣都是通過空間連續的數組構成，與ArrayList的區別是它在操作時是有上鎖的，這意味著多線程場景下它是可以保證線程安全的，但vector現在基本不用了，這里僅僅做個了解：
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//......
protected Object[] elementData;
//......
}2.ArrayList容量是10，給它添加一個元素會發生什么？
我們不妨看看這樣一段代碼，可以看到我們將集合容量設置為10，第11次添加元素時，由于ArrayList底層使用的數組已滿，為了能夠容納新的元素，它會進行一次動態擴容，即創建一個更大的容器將原有空間的元素拷貝過去：
//創建1個容量為10的數組
ArrayList<Integer> arrayList = new ArrayList<>(10);
//連續添加10次至空間滿
for (int i = 0; i < 10; i++) {
arrayList.add(i);
}
//再次添加引發動態擴容
arrayList.add(10);我們查看add源碼實現細節，可以每次插入前都會調用ensureCapacityInternal來確定當前數組空間是否可以容納新元素：
public boolean add(E e) {
//判斷本次插入位置是否大于容量
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}查看ensureCapacityInternal的細節可知，一旦感知數組空間不足以容納新元素時，ArrayList會創建一個新容器大小為原來的1.5倍，然后再將原數組元素拷貝到新容器中：
private void ensureCapacityInternal(int minCapacity) {
//傳入當前元素空間和所需的最小數組空間大小
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//當需求空間大于數組
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 創建一個原有容器1.5倍的數組空間
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//......
//將原有元素elementData拷貝到新空間去
elementData = Arrays.copyOf(elementData, newCapacity);
}3.針對動態擴容導致的性能問題,你有什么解決辦法嘛?
我們可以提前調用ensureCapacity頂下最終容量一次性完成動態擴容提高程序執行性能。
public static void main(String[] args) {
int size = 1000_0000;
ArrayList<Integer> list = new ArrayList<>(1);
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
long end = System.currentTimeMillis();
System.out.println("無顯示擴容，完成時間:" + (end - start));
//顯示擴容顯示擴容，避免多次動態擴容的拷貝
ArrayList<Integer> list2 = new ArrayList<>(size);
start = System.currentTimeMillis();
list2.ensureCapacity(size);
for (int i = 0; i < size; i++) {
list2.add(i);
}
end = System.currentTimeMillis();
System.out.println("顯示擴容，完成時間:" + (end - start));
}輸出結果如下，可以看到在顯示指明大小空間的情況下，性能要優于常規插入：
無顯示擴容，完成時間:6122
顯示擴容，完成時間:7614.ArrayList和LinkedList性能差異體現在哪
我們給出頭插法的示例代碼：
public static void main(String[] args) {
int size = 10_0000;
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
arrayList.add(0, i);
}
long end = System.currentTimeMillis();
System.out.println("arrayList頭插時長:" + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
linkedList.add(0, i);
}
end = System.currentTimeMillis();
System.out.println("linkedList 頭插時長:" + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
((LinkedList<Integer>) linkedList).addFirst(i);
}
end = System.currentTimeMillis();
System.out.println("linkedList addFirst 耗時:" + (end - start));
}從性能表現上來看arrayList表現最差，而linkedList 的addFirst 表現最出色。
arrayList頭插時長:562
linkedList 頭插時長:8
linkedList addFirst 耗時:4這里我們不妨說一下原因，arrayList性能差原因很明顯，每次頭部插入都需要挪動整個數組，linkedList的add方法在進行插入時，若是頭插法，它會通過node方法定位頭節點，然后在使用linkBefore完成頭插法。
public void add(int index, E element) {
//......
if (index == size)
linkLast(element);
else
//通過node定位到頭節點，再進行插入操作
linkBefore(element, node(index));
}而鏈表的addFirst 就不一樣，它直接定位到頭節點，進行頭插法，正是這一點點性能上的差距造成兩者性能表現上微小的差異。
private void linkFirst(E e) {
//直接定位到頭節點，進行頭插法
final Node<E> f = first;
//創建新節點
final Node<E> newNode = new Node<>(null, e, f);
//直接讓first 直接引用該節點
first = newNode;
//讓原有頭節點指向當前節點
if (f == null)
last = newNode;
else
f.prev = newNode;
//調整元素空間數量
size++;
modCount++;
}再來看看尾插法：
public static void main(String[] args) {
int size = 10_0000;
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
arrayList.add(i, i);
}
long end = System.currentTimeMillis();
System.out.println("arrayList 尾插時長:" + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
linkedList.add(i, i);
}
end = System.currentTimeMillis();
System.out.println("linkedList 尾插時長:" + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
((LinkedList<Integer>) linkedList).addLast(i);
}
end = System.currentTimeMillis();
System.out.println("linkedList 尾插時長:" + (end - start));
}輸出結果，可以看到還是鏈表稍快一些，為什么arraylist這里性能也還不錯呢？原因也很簡單，無需為了插入一個節點維護其他位置。
arrayList 尾插時長:5
linkedList 尾插時長:2
linkedList 尾插時長:3最后再來看看隨機插入，為了公平實驗，筆者將list初始化工作都放在計時之外，避免arrayList動態擴容的時間影響最終實驗結果:
public static void main(String[] args) {
int size = 10_0000;
//填充足夠量的數據
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < size; i++) {
arrayList.add(i);
}
//隨機插入
long begin = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
arrayList.add(RandomUtil.randomInt(0, size), RandomUtil.randomInt());
}
long end = System.currentTimeMillis();
System.out.println("arrayList隨機插入耗時:" + (end - begin));
//填充數據
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < size; i++) {
linkedList.add(i);
}
//隨機插入
begin = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
linkedList.add(RandomUtil.randomInt(0, size), RandomUtil.randomInt());
}
end = System.currentTimeMillis();
System.out.println("linkedList隨機插入耗時:" + (end - begin));
}從輸出結果來看，隨機插入也是arrayList性能較好，原因也很簡單，arraylist隨機訪問速度遠遠快與linklist：
arrayList隨機插入耗時:748
linkedList隨機插入耗時:27741針對兩者的性能差異，筆者也在這里進行一下簡單的小結：
- 頭插法：由于LinkedList節點維護只需管理原有頭節點和新節點的關系，無需大費周章的調整整個地址空間，相較于ArrayList，它的表現會相對出色一些。
- 尾插法：和頭插法類似，除非動態擴容，ArrayList無需進行大量的元素轉移，所以大體上兩者性能差異不是很大，總的來說linkedList 會稍勝一籌。
- 隨機插入：ArrayList在進行元素定位時只需O(1)的時間復雜度，相較于LinkedList 需要全集合掃描來說，這些時間開銷使得前者性能表現更加出色。
5.ArrayList 和 Vector 的異同
這個問題我們可以從以下兩個維度分析:
先來說說底層數據結構，兩者底層存儲都是采用數組，ArrayList存儲用的是new Object[initialCapacity];
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);
}
}Vector底層存儲元素用的也是是 new Object[initialCapacity];，即一個對象數組：
public Vector(int initialCapacity, int capacityIncrement) {
//......
//基于定長容量初始化數組
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}從并發安全角度來說，Vector 為線程安全類，ArrayList 線程不安全，如下所示我們使用ArrayList進行多線程插入出現的索引越界問題。
public static void main(String[] args) throws InterruptedException {
List<Integer> list = new ArrayList<>();
Thread t1 = new Thread(() -> {
for (int i = 0; i < 1000; i++) {
list.add(i);
}
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < 1000; i++) {
list.add(i);
}
});
t1.start();
t2.start();
t1.join();
t2.join();
Thread.sleep(5000);
System.out.println(list.size());
}因為多線程訪問的原因，底層索引不安全操作的自增，導致插入時得到一個錯誤的索引位置從而導致插入失?。?/p>
Exception in thread "Thread-0" java.lang.ArrayIndexOutOfBoundsException: 823
at java.util.ArrayList.add(ArrayList.java:463)
at com.sharkChili.Main.lambda$main$0(Main.java:15)
at java.lang.Thread.run(Thread.java:748)Vector 線程安全代碼示例：
public static void main(String[] args) throws InterruptedException {
List<Integer> list = new Vector<>();
Thread t1 = new Thread(() -> {
for (int i = 0; i < 1000; i++) {
list.add(i);
}
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < 1000; i++) {
list.add(i);
}
});
t1.start();
t2.start();
t1.join();
t2.join();
Thread.sleep(5000);
System.out.println(list.size());//2000
}原因很簡單，vector的add方法有加synchronized 關鍵字，保證單位時間內只有一個線程可以操作底層的數組:
//任何操作都是上鎖的，保證一次插入操作互斥和原子性
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}6.ArrayList 與 LinkedList 的區別
從上文中我們基本可以了解兩者區別，這里我們就做一個簡單的小結：
- 底層存儲結構:ArrayList 底層使用的是數組，LinkedList 底層使用的是鏈表
- 線程安全性:兩者都是線程不安全，因為add方法都沒有任何關于線程安全的處理。
- 隨機訪問性:雖然兩者都支持隨機訪問，但是鏈表隨機訪問不太高效。
- 內存空間占用: ArrayList 的空間浪費主要體現在在 List列表的結尾會預留一定的容量空間，而 LinkedList 的空間花費則體現在它的每一個元素都需要消耗比 ArrayList 更多的空間（因為要存放直接后繼和直接前驅以及數據）。
7.ArrayList 的擴容機制
Java的ArrayList 底層默認數組大小為10，的動態擴容機制即ArrayList 確保元素正確存放的關鍵，了解核心邏輯以及如何基于該機制提高元素存儲效率也是很重要的。
盡管從上面來看兩者各有千秋，但比較有趣的是，LinkedList的作者Josh Bloch基本沒有用過這個集合：
