說一下 ArrayList 和 LinkedList 的區別？

本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。

前言

大家好，我是小彭。

在上一篇文章裡，我們聊到了基於動態陣列 ArrayList 線性表，今天我們來討論一個基於連結串列的線性表 —— LinkedList。

小彭的 Android 交流群 02 群已經建立啦，掃描文末二維條碼進入~

思維導圖：

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 的屬性很好理解的，不出意外的話又有小朋友出來舉手提問了：