【注】本文譯自： Java ArrayList vs LinkedList | Baeldung

Java ArrayList 與 LinkedList

1. 概述

對(duì)于 collections?（集合），Java 標(biāo)準(zhǔn)庫(kù)提供了大量可供選擇的選項(xiàng)。在這些選項(xiàng)中，有兩個(gè)著名的 List 實(shí)現(xiàn)，稱為 ArrayList 和 LinkedList，每個(gè)實(shí)現(xiàn)都有自己的屬性和用例。

在本教程中，我們將看到這兩者是如何實(shí)現(xiàn)的。然后，我們將為評(píng)估每個(gè)應(yīng)用的不同。

2. ArrayList

在內(nèi)部，ArrayList 使用數(shù)組來實(shí)現(xiàn) List 接口。由于數(shù)組在 Java 中是固定大小的，因此 ArrayList 創(chuàng)建一個(gè)具有一些初始容量的數(shù)組。在此過程中，如果我們需要存儲(chǔ)比默認(rèn)容量更多的項(xiàng)，它將用一個(gè)新的、更大的數(shù)組替換該數(shù)組。

為了更好地理解它的屬性，讓我們根據(jù)它的三個(gè)主要操作來評(píng)估這個(gè)數(shù)據(jù)結(jié)構(gòu)：添加項(xiàng)、通過索引獲取項(xiàng)和通過索引刪除項(xiàng)。

2.1. 添加

當(dāng)我們創(chuàng)建一個(gè)空的 ArrayList 時(shí)，它會(huì)使用默認(rèn)容量（當(dāng)前為 10）初始化其后備數(shù)組：

在該數(shù)組尚未滿時(shí)添加新項(xiàng)目就像將該項(xiàng)分配給特定數(shù)組索引一樣簡(jiǎn)單。這個(gè)數(shù)組索引由當(dāng)前數(shù)組大小決定，因?yàn)槲覀儗?shí)際上是附加到列表中：

backingArray[size] = newItem;
size++;復(fù)制代碼

因此，在最佳和一般情況下，加法操作的時(shí)間復(fù)雜度為 O(1)，這非?？?。但是，隨著后備數(shù)組變滿，添加實(shí)現(xiàn)的效率會(huì)降低：

要添加新項(xiàng)目，我們應(yīng)該首先初始化一個(gè)容量更大的全新數(shù)組，并將所有現(xiàn)有項(xiàng)目復(fù)制到新數(shù)組中。只有在復(fù)制當(dāng)前元素后，我們才能添加新項(xiàng)目。因此，在最壞的情況下時(shí)間復(fù)雜度為 O(n)，因?yàn)槲覀儽仨毾葟?fù)制 n 個(gè)元素。

從理論上講，添加新元素的運(yùn)行時(shí)間為攤銷常數(shù)。也就是說，添加 n 個(gè)元素需要 O(n) 時(shí)間。但是，由于復(fù)制開銷，某些單次添加可能表現(xiàn)不佳。

2.2. 按索引訪問

通過索引訪問項(xiàng)是 ArrayList?的真正亮點(diǎn)。要檢索下標(biāo)為?i?的項(xiàng)，我們只需要返回位于后備數(shù)組中第 i 個(gè)下標(biāo)的項(xiàng)。因此，通過索引操作訪問的時(shí)間復(fù)雜度始終為 O(1)。

2.3. 通過索引刪除

假設(shè)我們要從 ArrayList 中刪除索引 6，它對(duì)應(yīng)于我們的后備數(shù)組中的元素 15：

將所需元素標(biāo)記為已刪除后，我們應(yīng)該將其后的所有元素向后移動(dòng)一個(gè)索引。顯然，元素越靠近數(shù)組的開頭，我們應(yīng)該移動(dòng)的元素就越多。因此，時(shí)間復(fù)雜度在最佳情況下為 O(1)，在平均和最壞情況下為 O(n)。

2.4. 應(yīng)用和限制

.通常，當(dāng)需要 List 實(shí)現(xiàn)時(shí)，ArrayList 是許多開發(fā)人員的默認(rèn)選擇。事實(shí)上，當(dāng)讀取次數(shù)遠(yuǎn)遠(yuǎn)超過寫入次數(shù)時(shí)，這實(shí)際上是一個(gè)明智的選擇。

有時(shí)我們需要同樣頻繁的讀取和寫入。如果我們確實(shí)估計(jì)了可能項(xiàng)目的最大數(shù)量，那么使用 ArrayList 仍然有意義。如果是這種情況，我們可以使用初始容量初始化 ArrayList：

int possibleUpperBound = 10_000;
List<String> items = new ArrayList<>(possibleUpperBound);復(fù)制代碼

這種估計(jì)可以防止大量不必要的復(fù)制和數(shù)組分配。

此外，數(shù)組由 Java 中的?int 值索引。因此，在 Java 數(shù)組中存儲(chǔ)超過 2 的 32 次方個(gè)元素是不可能的，因此，在 ArrayList 中也是如此。

3. LinkedList

LinkedList，顧名思義，使用鏈接節(jié)點(diǎn)的集合來存儲(chǔ)和檢索元素。例如，以下是添加四個(gè)元素后的 Java 實(shí)現(xiàn)：

每個(gè)節(jié)點(diǎn)維護(hù)兩個(gè)指針：一個(gè)指向下一個(gè)元素，另一個(gè)指向前一個(gè)元素。對(duì)此進(jìn)行擴(kuò)展，雙向鏈表有兩個(gè)指向第一項(xiàng)和最后一項(xiàng)的指針。

同樣，讓我們根據(jù)相同的基本操作來評(píng)估這個(gè)實(shí)現(xiàn)。

3.1. 添加

為了添加新節(jié)點(diǎn)，首先，我們應(yīng)該將當(dāng)前最后一個(gè)節(jié)點(diǎn)鏈接到新節(jié)點(diǎn)：

然后更新最后一個(gè)指針：

由于這兩個(gè)操作都很簡(jiǎn)單，因此加法操作的時(shí)間復(fù)雜度始終為 O(1)。

3.2. 通過索引訪問

LinkedList 與 ArrayList 不同，不支持快速隨機(jī)訪問。因此，為了按索引查找元素，我們應(yīng)該手動(dòng)遍歷列表的某些部分。

在最好的情況下，當(dāng)請(qǐng)求的項(xiàng)目接近列表的開頭或結(jié)尾時(shí)，時(shí)間復(fù)雜度將與 O(1) 一樣快。然而，在平均和最壞情況下，我們可能會(huì)以 O(n) 的訪問時(shí)間結(jié)束，因?yàn)槲覀儽仨氁粋€(gè)接一個(gè)地檢查許多節(jié)點(diǎn)。

3.3. 通過索引刪除

為了刪除一項(xiàng)，我們應(yīng)該首先找到請(qǐng)求的項(xiàng)，然后從列表中取消它的鏈接。因此，訪問時(shí)間決定了時(shí)間復(fù)雜度——即在最佳情況下為 O(1)，在平均和最壞情況下為 O(n)。

3.4. 應(yīng)用

當(dāng)添加率遠(yuǎn)高于讀取率時(shí)，LinkedLists 更適合。

此外，當(dāng)大多數(shù)時(shí)候我們想要第一個(gè)或最后一個(gè)元素時(shí)，它可以用于讀取密集的場(chǎng)景。值得一提的是，LinkedList 還實(shí)現(xiàn)了?Deque 接口——支持對(duì)集合兩端的高效訪問。

通常，如果我們知道它們的實(shí)現(xiàn)差異，那么我們可以輕松地為特定用例選擇一個(gè)。

例如，假設(shè)我們將在類似列表的數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)大量時(shí)間序列事件。我們知道我們每秒都會(huì)收到突發(fā)事件。

此外，我們需要定期檢查所有事件并提供一些統(tǒng)計(jì)數(shù)據(jù)。對(duì)于此用例，LinkedList 是更好的選擇，因?yàn)樘砑铀俾蔬h(yuǎn)高于讀取速率。

此外，我們會(huì)讀取所有項(xiàng)目，因此我們無法超過 O(n) 上限。

4. 結(jié)論

在本教程中，我們首先深入研究了 ArrayList 和 LinkLists 如何在 Java 中實(shí)現(xiàn)。

我們還評(píng)估了其中每一個(gè)的不同用例。