用 ArrayList 還是 LinkedList？看完你就懂了！

本文旨在為 Java 開發這擇合适的順序資料結構提供指導。

ArrayList 和 LinkedList 是 Java 集合架構中用來存儲對象引用清單的兩個類。ArrayList 和 LinkedList 都實作 List 接口。首先，讓我們了解一下它們最重要的父接口——List。

1. List 接口

清單（list）是元素的有序集合，也稱為序列。它提供了基于元素位置的操作，有助于快速通路、添加和删除清單中特定索引位置的元素。List 接口實作了 Collection 和 Iterable 作為父接口。它允許存儲重複值和空值，支援通過索引通路元素。

2. 用法

下面是使用 List 接口聲明 ArrayList 和 LinkedList 的代碼片段。

import java.util.*;
public class MyClass {
  // 非同步或非線程安全
  List<Object> arrayList = new ArrayList<>(); // 聲明一個 array list
  List<Object> linkedList = new LinkedList(); // 聲明 linked list
  // 確定線程安全
  List<Object> tsArrayList = Collections.synchronizedList(new LinkedList<>());
  List<Object> tsLinkedList = Collections.synchronizedList(new LinkedList<>());
}      

Vector 與 ArrayList 類似，隻是它們支援自動同步，這也使得 Vector 線程安全，但同時會帶來一些性能損耗。

3. 内部實作

3.1 LinkedList 内部實作

Linkedlist 資料結構包含一組有序的資料元素，稱為節點。每個元素都包含對其後續元素，即下一個元素的連結或引用。 序列的最後一個元素（尾部）指向空元素。連結清單本身包含對連結清單第一個元素的引用，該元素稱為 head 元素。Java 中的 LinkedList 是 List 接口的雙向連結清單。在雙向連結清單中，每個節點都指向它的上一個節點和下一個節點。此外，它還實作了其他接口，比如 Serializable、 Cloneable 和 Deque（實作 Queue 作為父接口）。

3.2 ArrayList 内部實作

ArrayList 是可調整大小的數組，實作了 List 接口。 它的内部是一個對象數組，可以根據需要擴容支援在集合中加入更多元素。可以通過構造函數 ArrayList(int initialCapacity)指定 ArrayList 的初始容量，然後在必要時使用 void ensureCapacity(int minCapacity) 增加容量，確定至少可以容納初始化時最小容量參數指定數量的元素。

它還提供一個方法 void trimToSize()，可以減少現有元素的大小。

// 調用構造函數 ArrayList<type>(initialCapacity)
List arr = new ArrayList<Integer>(10);      

預設情況下，ArrayList 建立初始容量為10的清單，而 LinkedList 隻構造一個沒有設定任何初始容量的空清單。 Linkedlist 不實作 RandomAccess 接口，而 ArrayList 實作了 RandomAccess 接口（而非 Deque 接口）。

4. 各種操作的時空複雜性

5. 小貼士

考慮下面周遊 LinkedList 的示例代碼。在這段代碼中周遊會非常慢，因為 LinkedList 不支援随機通路，是以每次周遊都會帶來巨大的開銷。

LinkedList ll = new LinkedList();
…
…
Object o = null;
for (int i = 0; i < list.size(); i++)
{
  o = list.get(i);
  …
}      

一個更好的方法可提高性能，像下面這段代碼。

LinkedList ll = new LinkedList();
…
…
Object o = null;
ListIterator li = list.listIterator(0);
while (li.hasNext()){
  o = ll.next();
  …
}      

6. 總結

相比較而言 ArrayList 更快而且更好，因為它支援對其元素的随機通路。 周遊連結清單或在中間插入新元素開銷很大，因為必須周遊每個元素而且很可能遇到緩存失敗。 如果需要在一次疊代中對清單中的多個項目執行處理，那麼 LinkedList 的開銷比 ArrayList 使用時多次複制數組元素的開銷要小。

歡迎分享你對這個話題的經驗與見解，請在文章的評論區中提出你的想法。

原文：

https://dzone.com/articles/arraylist-or-linkedlist

翻譯：唐尤華