Java 有序集合 List 深度解析
在現(xiàn)代軟件開(kāi)發(fā)中，Java 是一種廣泛使用的編程語(yǔ)言，其豐富的標(biāo)準(zhǔn)庫(kù)提供了多種數(shù)據(jù)結(jié)構(gòu)來(lái)幫助開(kāi)發(fā)者高效地管理和操作數(shù)據(jù)。其中，List 集合是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，它允許我們以有序的方式存儲(chǔ)和訪問(wèn)元素。
本文將深入探討 Java 中的 List 集合，包括它的基本概念、主要實(shí)現(xiàn)類（如 ArrayList 和 LinkedList）、常見(jiàn)的操作方法以及優(yōu)秀實(shí)踐。無(wú)論您是初學(xué)者還是有一定經(jīng)驗(yàn)的開(kāi)發(fā)者，都能從本文中獲得有價(jià)值的知識(shí)和實(shí)用技巧。
Java集合的體系概覽
從Java頂層設(shè)計(jì)角度分類而言，集合整體可分為兩大類型：
第1大類是存放單元素的Collection，從源碼的注釋即可看出，該接口用于表示一組對(duì)象的抽象，該接口下的實(shí)現(xiàn)的集合空間或允許或不允許元素重復(fù)，JDK不提供此幾口的任何直接實(shí)現(xiàn)，也就是說(shuō)，該接口底層有包括List、Set等接口的抽象實(shí)現(xiàn)：
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大類則是存放鍵值對(duì)的Map，該類型要求鍵不可重復(fù)，且每個(gè)鍵最多可以到映射到一個(gè)值(注意這是從宏觀角度說(shuō)的值，該值可以是一個(gè)對(duì)象、可以是一個(gè)集合)：
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
我們針對(duì)Collection接口進(jìn)行展開(kāi)說(shuō)明，按照元素存儲(chǔ)規(guī)則的不同我們又可以分為:
- 有序不重復(fù)的Set集合體系。
- 有序可重復(fù)的LIst集合體系。
- 支持FIFO順序的隊(duì)列類型Queue。
對(duì)應(yīng)的我們給出類圖：
同理我們將Map接口進(jìn)行展開(kāi)，他的特點(diǎn)就是每一個(gè)元素都是由鍵值對(duì)組成，我們可以通過(guò)key找到對(duì)應(yīng)的value，類圖如下，集合具體詳情筆者會(huì)在后文闡述這里我們只要有一個(gè)粗略的印象即可：
詳解List集合體系知識(shí)點(diǎn)
1.List集合概覽
List即有序集合，該接口體系下所實(shí)現(xiàn)的集合可以精確控制每一個(gè)元素插入的位置，用戶可以通過(guò)整數(shù)索引定位和訪問(wèn)元素：
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.
從底層結(jié)構(gòu)角度，有序集合還可以有兩種實(shí)現(xiàn)，第一種也就是我們常說(shuō)的ArrayList ，從ArrayList源碼找到的ArrayList底層存儲(chǔ)元素的變量elementData，可以看出ArrayList本質(zhì)上就是對(duì)原生數(shù)組的封裝：
transient Object[] elementData;第2中則是LinkedList即雙向鏈表所實(shí)現(xiàn)的有序集合，它由一個(gè)個(gè)節(jié)點(diǎn)構(gòu)成，節(jié)點(diǎn)有雙指針，分別指向前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。
private static class Node<E> {
E item;
// 指向后繼節(jié)點(diǎn)
Node<E> next;
//指向前驅(qū)節(jié)點(diǎn)
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}Vector底層實(shí)現(xiàn)ArrayList一樣都是通過(guò)空間連續(xù)的數(shù)組構(gòu)成，與ArrayList的區(qū)別是它在操作時(shí)是有上鎖的，這意味著多線程場(chǎng)景下它是可以保證線程安全的，但vector現(xiàn)在基本不用了，這里僅僅做個(gè)了解：
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//......
protected Object[] elementData;
//......
}2.ArrayList容量是10，給它添加一個(gè)元素會(huì)發(fā)生什么？
我們不妨看看這樣一段代碼，可以看到我們將集合容量設(shè)置為10，第11次添加元素時(shí)，由于ArrayList底層使用的數(shù)組已滿，為了能夠容納新的元素，它會(huì)進(jìn)行一次動(dòng)態(tài)擴(kuò)容，即創(chuàng)建一個(gè)更大的容器將原有空間的元素拷貝過(guò)去：
//創(chuàng)建1個(gè)容量為10的數(shù)組
ArrayList<Integer> arrayList = new ArrayList<>(10);
//連續(xù)添加10次至空間滿
for (int i = 0; i < 10; i++) {
arrayList.add(i);
}
//再次添加引發(fā)動(dòng)態(tài)擴(kuò)容
arrayList.add(10);我們查看add源碼實(shí)現(xiàn)細(xì)節(jié)，可以每次插入前都會(huì)調(diào)用ensureCapacityInternal來(lái)確定當(dāng)前數(shù)組空間是否可以容納新元素：
public boolean add(E e) {
//判斷本次插入位置是否大于容量
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}查看ensureCapacityInternal的細(xì)節(jié)可知，一旦感知數(shù)組空間不足以容納新元素時(shí)，ArrayList會(huì)創(chuàng)建一個(gè)新容器大小為原來(lái)的1.5倍，然后再將原數(shù)組元素拷貝到新容器中：
private void ensureCapacityInternal(int minCapacity) {
//傳入當(dāng)前元素空間和所需的最小數(shù)組空間大小
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//當(dāng)需求空間大于數(shù)組
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 創(chuàng)建一個(gè)原有容器1.5倍的數(shù)組空間
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//......
//將原有元素elementData拷貝到新空間去
elementData = Arrays.copyOf(elementData, newCapacity);
}3.針對(duì)動(dòng)態(tài)擴(kuò)容導(dǎo)致的性能問(wèn)題,你有什么解決辦法嘛?
我們可以提前調(diào)用ensureCapacity頂下最終容量一次性完成動(dòng)態(tài)擴(kuò)容提高程序執(zhí)行性能。
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("無(wú)顯示擴(kuò)容，完成時(shí)間:" + (end - start));
//顯示擴(kuò)容顯示擴(kuò)容，避免多次動(dòng)態(tài)擴(kuò)容的拷貝
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("顯示擴(kuò)容，完成時(shí)間:" + (end - start));
}輸出結(jié)果如下，可以看到在顯示指明大小空間的情況下，性能要優(yōu)于常規(guī)插入：
無(wú)顯示擴(kuò)容，完成時(shí)間:6122
顯示擴(kuò)容，完成時(shí)間:7614.ArrayList和LinkedList性能差異體現(xiàn)在哪
我們給出頭插法的示例代碼：
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頭插時(shí)長(zhǎng):" + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
linkedList.add(0, i);
}
end = System.currentTimeMillis();
System.out.println("linkedList 頭插時(shí)長(zhǎng):" + (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 耗時(shí):" + (end - start));
}從性能表現(xiàn)上來(lái)看arrayList表現(xiàn)最差，而linkedList 的addFirst 表現(xiàn)最出色。
arrayList頭插時(shí)長(zhǎng):562
linkedList 頭插時(shí)長(zhǎng):8
linkedList addFirst 耗時(shí):4這里我們不妨說(shuō)一下原因，arrayList性能差原因很明顯，每次頭部插入都需要挪動(dòng)整個(gè)數(shù)組，linkedList的add方法在進(jìn)行插入時(shí)，若是頭插法，它會(huì)通過(guò)node方法定位頭節(jié)點(diǎn)，然后在使用linkBefore完成頭插法。
public void add(int index, E element) {
//......
if (index == size)
linkLast(element);
else
//通過(guò)node定位到頭節(jié)點(diǎn)，再進(jìn)行插入操作
linkBefore(element, node(index));
}而鏈表的addFirst 就不一樣，它直接定位到頭節(jié)點(diǎn)，進(jìn)行頭插法，正是這一點(diǎn)點(diǎn)性能上的差距造成兩者性能表現(xiàn)上微小的差異。
private void linkFirst(E e) {
//直接定位到頭節(jié)點(diǎn)，進(jìn)行頭插法
final Node<E> f = first;
//創(chuàng)建新節(jié)點(diǎn)
final Node<E> newNode = new Node<>(null, e, f);
//直接讓first 直接引用該節(jié)點(diǎn)
first = newNode;
//讓原有頭節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)
if (f == null)
last = newNode;
else
f.prev = newNode;
//調(diào)整元素空間數(shù)量
size++;
modCount++;
}再來(lái)看看尾插法：
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 尾插時(shí)長(zhǎng):" + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
linkedList.add(i, i);
}
end = System.currentTimeMillis();
System.out.println("linkedList 尾插時(shí)長(zhǎng):" + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
((LinkedList<Integer>) linkedList).addLast(i);
}
end = System.currentTimeMillis();
System.out.println("linkedList 尾插時(shí)長(zhǎng):" + (end - start));
}輸出結(jié)果，可以看到還是鏈表稍快一些，為什么arraylist這里性能也還不錯(cuò)呢？原因也很簡(jiǎn)單，無(wú)需為了插入一個(gè)節(jié)點(diǎn)維護(hù)其他位置。
arrayList 尾插時(shí)長(zhǎng):5
linkedList 尾插時(shí)長(zhǎng):2
linkedList 尾插時(shí)長(zhǎng):3最后再來(lái)看看隨機(jī)插入，為了公平實(shí)驗(yàn)，筆者將list初始化工作都放在計(jì)時(shí)之外，避免arrayList動(dòng)態(tài)擴(kuò)容的時(shí)間影響最終實(shí)驗(yàn)結(jié)果:
public static void main(String[] args) {
int size = 10_0000;
//填充足夠量的數(shù)據(jù)
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < size; i++) {
arrayList.add(i);
}
//隨機(jī)插入
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隨機(jī)插入耗時(shí):" + (end - begin));
//填充數(shù)據(jù)
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < size; i++) {
linkedList.add(i);
}
//隨機(jī)插入
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隨機(jī)插入耗時(shí):" + (end - begin));
}從輸出結(jié)果來(lái)看，隨機(jī)插入也是arrayList性能較好，原因也很簡(jiǎn)單，arraylist隨機(jī)訪問(wèn)速度遠(yuǎn)遠(yuǎn)快與linklist：
arrayList隨機(jī)插入耗時(shí):748
linkedList隨機(jī)插入耗時(shí):27741針對(duì)兩者的性能差異，筆者也在這里進(jìn)行一下簡(jiǎn)單的小結(jié)：
- 頭插法：由于LinkedList節(jié)點(diǎn)維護(hù)只需管理原有頭節(jié)點(diǎn)和新節(jié)點(diǎn)的關(guān)系，無(wú)需大費(fèi)周章的調(diào)整整個(gè)地址空間，相較于ArrayList，它的表現(xiàn)會(huì)相對(duì)出色一些。
- 尾插法：和頭插法類似，除非動(dòng)態(tài)擴(kuò)容，ArrayList無(wú)需進(jìn)行大量的元素轉(zhuǎn)移，所以大體上兩者性能差異不是很大，總的來(lái)說(shuō)linkedList 會(huì)稍勝一籌。
- 隨機(jī)插入：ArrayList在進(jìn)行元素定位時(shí)只需O(1)的時(shí)間復(fù)雜度，相較于LinkedList 需要全集合掃描來(lái)說(shuō)，這些時(shí)間開(kāi)銷使得前者性能表現(xiàn)更加出色。
5.ArrayList 和 Vector 的異同
這個(gè)問(wèn)題我們可以從以下兩個(gè)維度分析:
先來(lái)說(shuō)說(shuō)底層數(shù)據(jù)結(jié)構(gòu)，兩者底層存儲(chǔ)都是采用數(shù)組，ArrayList存儲(chǔ)用的是new Object[initialCapacity];
public ArrayList(int initialCapacity) {
//給定容量后初始化定長(zhǎng)數(shù)組存儲(chǔ)元素
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}Vector底層存儲(chǔ)元素用的也是是 new Object[initialCapacity];，即一個(gè)對(duì)象數(shù)組：
public Vector(int initialCapacity, int capacityIncrement) {
//......
//基于定長(zhǎng)容量初始化數(shù)組
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}從并發(fā)安全角度來(lái)說(shuō)，Vector 為線程安全類，ArrayList 線程不安全，如下所示我們使用ArrayList進(jìn)行多線程插入出現(xiàn)的索引越界問(wèn)題。
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());
}因?yàn)槎嗑€程訪問(wèn)的原因，底層索引不安全操作的自增，導(dǎo)致插入時(shí)得到一個(gè)錯(cuò)誤的索引位置從而導(dǎo)致插入失?。?/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
}原因很簡(jiǎn)單，vector的add方法有加synchronized 關(guān)鍵字，保證單位時(shí)間內(nèi)只有一個(gè)線程可以操作底層的數(shù)組:
//任何操作都是上鎖的，保證一次插入操作互斥和原子性
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}6.ArrayList 與 LinkedList 的區(qū)別
從上文中我們基本可以了解兩者區(qū)別，這里我們就做一個(gè)簡(jiǎn)單的小結(jié)：
- 底層存儲(chǔ)結(jié)構(gòu):ArrayList 底層使用的是數(shù)組，LinkedList 底層使用的是鏈表
- 線程安全性:兩者都是線程不安全，因?yàn)閍dd方法都沒(méi)有任何關(guān)于線程安全的處理。
- 隨機(jī)訪問(wèn)性:雖然兩者都支持隨機(jī)訪問(wèn)，但是鏈表隨機(jī)訪問(wèn)不太高效。
- 內(nèi)存空間占用: ArrayList 的空間浪費(fèi)主要體現(xiàn)在在 List列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而 LinkedList 的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比 ArrayList 更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。
7.ArrayList 的擴(kuò)容機(jī)制
Java的ArrayList 底層默認(rèn)數(shù)組大小為10，的動(dòng)態(tài)擴(kuò)容機(jī)制即ArrayList 確保元素正確存放的關(guān)鍵，了解核心邏輯以及如何基于該機(jī)制提高元素存儲(chǔ)效率也是很重要的。
盡管從上面來(lái)看兩者各有千秋，但比較有趣的是，LinkedList的作者Josh Bloch基本沒(méi)有用過(guò)這個(gè)集合：
