Java 面試題：說一下 ArrayList 和 LinkedList 的區別？
theme: jzman
本文已收錄到 GitHub · AndroidFamily，有 Android 進階知識體系，歡迎 Star。技術和職場問題，請關注公眾號 [彭旭銳] 私信我提問。
前言
大家好，我是小彭。
在上一篇文章裡，我們聊到了基於動態陣列 ArrayList 線性表，今天我們來討論一個基於連結串列的線性表 —— LinkedList。
學習路線圖：
1. LinkedList 的特點
1.1 說一下 ArrayList 和 LinkedList 的區別？
- 1、資料結構： 在資料結構上，ArrayList 和 LinkedList 都是 “線性表”，都繼承於 Java 的
List介面。另外 LinkedList 還實現了 Java 的Deque介面，是基於連結串列的棧或佇列，與之對應的是ArrayDeque基於陣列的棧或佇列； - 2、執行緒安全： ArrayList 和 LinkedList 都不考慮執行緒同步，不保證執行緒安全；
- 3、底層實現： 在底層實現上，ArrayList 是基於動態陣列的，而 LinkedList 是基於雙向連結串列的。事實上，它們很多特性的區別都是因為底層實現不同引起的。比如說：
- 在遍歷速度上： 陣列是一塊連續記憶體空間，基於區域性性原理能夠更好地命中 CPU 快取行，而連結串列是離散的記憶體空間對快取行不友好；
- 在訪問速度上： 陣列是一塊連續記憶體空間，支援 O(1) 時間複雜度隨機訪問，而連結串列需要 O(n) 時間複雜度查詢元素；
- 在新增和刪除操作上： 如果是在陣列的末尾操作只需要 O(1) 時間複雜度，但在陣列中間操作需要搬運元素，所以需要 O(n)時間複雜度，而連結串列的刪除操作本身只是修改引用指向，只需要 O(1) 時間複雜度（如果考慮查詢被刪除節點的時間，複雜度分析上依然是 O(n)，在工程分析上還是比陣列快）；
- 額外記憶體消耗上： ArrayList 在陣列的尾部增加了閒置位置，而 LinkedList 在節點上增加了前驅和後繼指標。
1.2 LinkedList 的多面人生
在資料結構上，LinkedList 不僅實現了與 ArrayList 相同的 List 介面，還實現了 Deque 介面（繼承於 Queue 介面）。
Deque 介面表示一個雙端佇列（Double Ended Queue），允許在佇列的首尾兩端操作，所以既能實現佇列行為，也能實現棧行為。
Queue 介面：
| 拒絕策略 | 拋異常 | 返回特殊值 | | ------ | --------- | -------- | | 入隊（隊尾） | add(e) | offer(e) | | 出隊（隊頭） | remove() | poll() | | 觀察（隊頭） | element() | peek() |
Queue 的 API 可以分為 2 類，區別在於方法的拒絕策略上：
-
拋異常：
- 向空佇列取資料，會丟擲 NoSuchElementException 異常；
- 向容量滿的佇列加資料，會丟擲 IllegalStateException 異常。
-
返回特殊值：
- 向空佇列取資料，會返回 null；
- 向容量滿的佇列加資料，會返回 false。
Deque 介面：
Java 沒有提供標準的棧介面（很好奇為什麼不提供），而是放在 Deque 介面中：
| 拒絕策略 | 拋異常 | 等價於 | | ------ | ------- | ------------- | | 入棧 | push(e) | addFirst(e) | | 出棧 | pop() | removeFirst() | | 觀察（棧頂） | peek() | peekFirst() |
除了標準的佇列和棧行為，Deque 介面還提供了 12 個在兩端操作的方法：
| 拒絕策略 | 拋異常 | 返回值 | | ---- | --------------------------- | --------------------------- | | 增加 | addFirst(e)/ addLast(e) | offerFirst(e)/ offerLast(e) | | 刪除 | removeFirst()/ removeLast() | pollFirst()/ pollLast() | | 觀察 | getFirst()/ getLast() | peekFirst()/ peekLast()
2. LinkedList 原始碼分析
這一節，我們來分析 LinkedList 中主要流程的原始碼。
2.1 LinkedList 的屬性
- LinkedList 底層是一個 Node 雙向連結串列，Node 節點中會持有資料 E 以及 prev 與next 兩個指標；
- LinkedList 用
first和last指標指向連結串列的頭尾指標。
LinkedList 的屬性很好理解的，不出意外的話又有小朋友出來舉手提問了：
- 🙋🏻♀️ 疑問 1：為什麼欄位都不宣告
private關鍵字？
這個問題直接回答吧。我的理解是：因為內部類在編譯後會生成獨立的 Class 檔案，如果外部類的欄位是 private 型別，那麼編譯器就需要通過方法呼叫，而 non-private 欄位就可以直接訪問欄位。
- 🙋🏻♀️ 疑問 2：為什麼欄位都宣告
transient關鍵字？
這個問題我們在分析原始碼的過程中回答。
疑問比 ArrayList 少很多，LinkedList 真香（還是別高興得太早吧）。
```java
public class LinkedList
// 疑問 1：為什麼欄位都不宣告 private 關鍵字？
// 疑問 2：為什麼欄位都宣告 transient 關鍵字？
// 元素個數
transient int size = 0;
// 頭指標
transient Node<E> first;
// 尾指標
transient Node<E> last;
// 連結串列節點
private static class Node<E> {
// 節點資料
// （型別擦除後：Object item;）
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;
}
}
} ```
2.2 LinkedList 的構造方法
LinkedList 有 2 個構造方法：
- 1、無參構造方法： no-op；
- 2、帶集合的構造： 在連結串列末尾新增整個集合，內部呼叫了 addAll 方法將整個集合新增到陣列的末尾。
```java // 無參構造方法 public LinkedList() { }
// 帶集合的構造方法 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
// 在連結串列尾部新增集合 public boolean addAll(Collection<? extends E> c) { // 索引為 size，等於在連結串列尾部新增 return addAll(size, c); } ```
2.3 LinkedList 的新增方法
LinkedList 提供了非常多的 addXXX 方法，內部都是呼叫一系列 linkFirst、linkLast 或 linkBefore 完成的。如果在連結串列中間新增節點時，會用到 node(index) 方法查詢指定位置的節點。
其實，我們會發現所有新增的邏輯都可以用 6 個步驟概括：
- 步驟 1： 找到插入位置的後繼節點（在頭部插入就是 first，在尾部插入就是 null）；
- 步驟 2： 構造新節點；
- 步驟 3： 將新節點的 prev 指標指向前驅節點（在頭部插入就是 null，在尾部插入就是 last）；
- 步驟 4： 將新節點的 next 指標指向後繼節點（在頭部插入就是 first，在尾部插入就是 null）；
- 步驟 5： 將前驅節點的 next 指標指向新節點（在頭部插入沒有這個步驟）；
- 步驟 6： 將後繼節點的 prev 指標指向新節點（在尾部插入沒有這個步驟）。
分析一下新增方法的時間複雜度，區分在連結串列兩端或中間新增元素的情況共：
- 如果是在連結串列首尾兩端新增： 只需要 O(1) 時間複雜度；
- 如果在連結串列中間新增： 由於需要定位到新增位置的前驅和後繼節點，所以需要 O(n) 時間複雜度。如果事先已經獲得了新增位置的節點，就只需要 O(1) 時間複雜度。
新增方法
```java public void addFirst(E e) { linkFirst(e); }
public void addLast(E e) { linkLast(e); }
public boolean add(E e) { linkLast(e); return true; }
public void add(int index, E element) { checkPositionIndex(index); if (index == size) // 在尾部新增 linkLast(element); else // 在指定位置新增 linkBefore(element, node(index)); }
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }
// 在連結串列頭部新增
private void linkFirst(E e) {
// 1. 找到插入位置的後繼節點（first）
final Node
// 在連結串列尾部新增
void linkLast(E e) {
final Node
// 在指定節點前新增
// 1. 找到插入位置的後繼節點
void linkBefore(E e, Node
// 在指定位置新增整個集合元素 // index 為 0：在連結串列頭部新增 // index 為 size：在連結串列尾部新增 public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); // 事實上，c.toArray() 的實際型別不一定是 Object[]，有可能是 String[] 等 // 不過，我們是通過 Node中的item 承接的，所以不用擔心 ArrayList 中的 ArrayStoreException 問題 Object[] a = c.toArray(); // 新增的陣列為空，跳過 int numNew = a.length; if (numNew == 0) return false;
// 1. 找到插入位置的後繼節點
// pred：插入位置的前驅節點
// succ：插入位置的後繼節點
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
// 找到 index 位置原本的節點，插入後變成後繼節點
succ = node(index);
pred = succ.prev;
}
// 插入集合元素
for (Object o : a) {
E e = (E) o;
// 2. 構造新節點
// 3. 將新節點的 prev 指標指向前驅節點
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
// pred 為 null 說明是在頭部插入，需要修改 first 指標
first = newNode;
else
// 5. 將前驅節點的 next 指標指向新節點
pred.next = newNode;
// 修改前驅指標
pred = newNode;
}
if (succ == null) {
// succ 為 null 說明是在尾部插入，需要修改 last 指標
last = pred;
} else {
// 4. 將新節點的 next 指標指向後繼節點
pred.next = succ;
// 6. 將後繼節點的 prev 指標指向新節點
succ.prev = pred;
}
// 數量增加 numNew
size += numNew;
modCount++;
return true;
}
// 將 LinkedList 轉化為 Object 陣列
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node
在連結串列中間新增節點時，會用到 node(index) 方法查詢指定位置的節點。可以看到維持 first 和 last 頭尾節點的作用又發揮出來了：
- 如果索引位置小於 size/2，則從頭節點開始找；
- 如果索引位置大於 size/2，則從尾節點開始找。
雖然，我們從複雜度分析的角度看，從哪個方向查詢是沒有區別的，時間複雜度都是 O(n)。但從工程分析的角度看還是有區別的，從更靠近目標節點的位置開始查詢，實際執行的時間會更短。
查詢指定位置節點
java
// 尋找指定位置的節點，時間複雜度：O(n)
Node<E> node(int index) {
if (index < (size >> 1)) {
// 如果索引位置小於 size/2，則從頭節點開始找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果索引位置大於 size/2，則從尾節點開始找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
LinkedList 的刪除方法其實就是新增方法的逆運算，我們就不重複分析了。
```java
// 刪除頭部元素
public E removeFirst() {
final Node
// 刪除尾部元素
public E removeLast() {
final Node
// 刪除指定元素 public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } ```
2.4 LinkedList 的迭代器
Java 的 foreach 是語法糖，本質上也是採用 iterator 的方式。由於 LinkedList 本身就是雙向的，所以 LinkedList 只提供了 1 個迭代器：
- ListIterator
listIterator()： 雙向迭代器
與其他容器類一樣，LinkedList 的迭代器中都有 fail-fast 機制。如果在迭代的過程中發現 expectedModCount 變化，說明資料被修改，此時就會提前丟擲 ConcurrentModificationException 異常（當然也不一定是被其他執行緒修改）。
```java
public ListIterator
// 非靜態內部類
private class ListItr implements ListIterator
ListItr(int index) {
next = (index == size) ? null : node(index);
nextIndex = index;
}
public E next() {
// 更新 expectedModCount
checkForComodification();
...
}
...
} ```
2.5 LinkedList 的序列化過程
- 🙋🏻♀️ 疑問 2：為什麼欄位都宣告
transient關鍵字？
LinkedList 重寫了 JDK 序列化的邏輯，不序列化連結串列節點，而只是序列化連結串列節點中的有效資料，這樣序列化產物的大小就有所降低。在反序列時，只需要按照物件順序依次新增到連結串列的末尾，就能恢復連結串列的順序。
```java // 序列化和反序列化只考慮有效資料
// 序列化過程 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject();
// 寫入連結串列長度
s.writeInt(size);
// 寫入節點上的有效資料
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
// 反序列化過程 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject();
// 讀取連結串列長度
int size = s.readInt();
// 讀取有效元素並用 linkLast 新增到連結串列尾部
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
} ```
2.6 LinkedList 如何實現執行緒安全？
有 5 種方式：
- 方法 1 - 使用 Collections.synchronizedList 包裝類： 原理也是在所有方法上增加 synchronized 關鍵字；
- 方法 2 - 使用 ConcurrentLinkedQueue 容器類： 基於 CAS 無鎖實現的執行緒安全佇列；
- 方法 3 - 使用 LinkedBlockingQueue 容器： 基於加鎖的阻塞佇列，適合於帶阻塞操作的生產者消費者模型；
- 方法 4 - 使用 LinkedBlockingDeque 容器： 基於加鎖的阻塞雙端佇列，適合於帶阻塞操作的生產者消費者模型；
- 方法 5 - 使用 ConcurrentLinkedDeque 容器類： 基於 CAS 無鎖實現的執行緒安全雙端佇列。
3. 總結
-
1、LinkedList 是基於連結串列的線性表，同時具備 List、Queue 和 Stack 的行為；
-
2、在查詢指定位置的節點時，如果索引位置小於 size/2，則從頭節點開始找，否則從尾節點開始找；
-
3、LinkedList 重寫了序列化過程，只處理連結串列節點中有效的元素；
-
4、LinkedList 和 ArrayList 都不考慮執行緒同步，不保證執行緒安全。
在上一篇文章裡，我們提到了 List 的陣列實現 ArrayList，而 LinkedList 不僅是 List 的連結串列實現，同時還是 Queue 和 Stack 的連結串列實現。那麼，在 Java 中的 Queue 和 Stack 的陣列實現是什麼呢，這個我們在下篇文章討論，請關注。
本文為稀土掘金技術社群首發簽約文章，14天內禁止轉載，14天后未獲授權禁止轉載，侵權必究！
- LeetCode 周賽 336，多少人直接 CV？
- LeetCode 周賽 335，純純手速場！
- LeetCode 雙週賽 98，腦筋急轉彎轉不過來！
- Android IO 框架 Okio 的實現原理，到底哪裡 OK？
- 12 張圖看懂 CPU 快取一致性與 MESI 協議，真的一致嗎？
- Android 序列化框架 Gson 原理分析，可以優化嗎？
- 為什麼計算機中的負數要用補碼錶示？
- 什麼是二叉樹？
- 我把 CPU 三級快取的祕密，藏在這 8 張圖裡
- 全網最全的 ThreadLocal 原理詳細解析 —— 原理篇
- 程式設計師學習 CPU 有什麼用？
- WeakHashMap 和 HashMap 的區別是什麼，何時使用？
- 萬字 HashMap 詳解，基礎（優雅）永不過時 —— 原理篇
- Java 面試題：說一下 ArrayDeque 和 LinkedList 的區別?
- Java 面試題：說一下 ArrayList 和 LinkedList 的區別？
- Java 面試題：ArrayList 可以完全替代陣列嗎？
- 已經有 MESI 協議，為什麼還需要 volatile 關鍵字？
- JVM 系列（6）吊打面試官：為什麼 finalize() 方法只會執行一次？
- 使用字首和陣列解決"區間和查詢"問題
- NDK 系列（5）：JNI 從入門到實踐，萬字爆肝詳解！