Java 面試題:說一下 ArrayDeque 和 LinkedList 的區別?

語言: CN / TW / HK

theme: jzman

本文已收錄到  GitHub · AndroidFamily,有 Android 進階知識體系,歡迎 Star。技術和職場問題,請關注公眾號 [彭旭銳] 私信我提問。

前言

大家好,我是小彭。

在上一篇文章裡,我們聊到了基於連結串列的 Queue 和 Stack 實現 —— LinkedList。那麼 Java 中有沒有基於陣列的 Queue 和 Stack 實現呢?今天我們就來聊聊這個話題。


學習路線圖:


1. 回顧 LinkedList

在資料結構上,LinkedList 不僅實現了與 ArrayList 相同的 List 介面,還實現了 Deque 介面,而我們今天要講的 ArrayDeque 就是實現於 Deque 介面的動態陣列。

Deque 介面表示一個雙端佇列(Double Ended Queue),允許在佇列的首尾兩端操作,所以既能實現佇列行為,也能實現棧行為。

1.1 Queue 介面

Queue 的 API 可以分為 2 類,區別在於方法的拒絕策略上:

  • 拋異常:
    • 向空佇列取資料,會丟擲 NoSuchElementException 異常;
    • 向容量滿的佇列加資料,會丟擲 IllegalStateException 異常。
  • 返回特殊值:
    • 向空佇列取資料,會返回 null;
    • 向容量滿的佇列加資料,會返回 false。

| 拒絕策略 | 拋異常 | 返回特殊值 | | --- | --- | --- | | 入隊(隊尾) | add(e) | offer(e) | | 出隊(隊頭) | remove() | poll() | | 觀察(隊頭) | element() | peek() |

1.2 Deque 介面(繼承於 Queue 介面)

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. ArrayDeque 的特點

2.1 說一下 ArrayDeque 的特點

  • 1、ArrayDeque 是基於動態陣列實現的 Deque 雙端佇列,內部封裝了擴容和資料搬運的邏輯;

  • 2、ArrayDeque 的陣列容量保證是 2 的整數冪;

  • 3、ArrayDeque 不是執行緒安全的;

  • 4、ArrayDeque 不支援 null 元素;

  • 5、ArrayDeque 雖然入棧和入隊有可能會觸發擴容,但從均攤分析上看依然是 O(1) 時間複雜度;

2.2 說一下 ArrayDeque 和 LinkedList 的區別?

  • 1、資料結構: 在資料結構上,ArrayDeque 和 LinkedList 都實現了 Java Deque 雙端佇列介面。但 ArrayDeque 沒有實現了 Java List 列表介面,所以不具備根據索引位置操作的行為;

  • 2、執行緒安全: ArrayDeque 和 LinkedList 都不考慮執行緒同步,不保證執行緒安全;

  • 3、底層實現: 在底層實現上,ArrayDeque 是基於動態陣列的,而 LinkedList 是基於雙向連結串列的。

    • 在遍歷速度上: ArrayDeque 是一塊連續記憶體空間,基於區域性性原理能夠更好地命中 CPU 快取行,而 LinkedList 是離散的記憶體空間對快取行不友好;

    • 在操作速度上: ArrayDeque 和 LinkedList 的棧和佇列行為都是 O(1) 時間複雜度,ArrayDeque 的入棧和入隊有可能會觸發擴容,但從均攤分析上看依然是 O(1) 時間複雜度;

    • 額外記憶體消耗上: ArrayDeque 在陣列的頭指標和尾指標外部有閒置空間,而 LinkedList 在節點上增加了前驅和後繼指標。


3. 如何使用陣列實現棧和佇列?

我們知道棧和佇列都是 “操作受限” 的線性表:棧是 LIFO,限制在表的一端入棧和出棧。而佇列是 FIFO,限制在表的一端入隊,在另一端出隊。棧和佇列既可以用陣列實現,也可以用連結串列實現:

  • 陣列:用陣列實現時叫作順序棧和順序佇列;
  • 連結串列:用連結串列實現時叫作鏈式棧和鏈式佇列。

3.1 為什麼 ArrayList 不適合實現佇列?

在上一篇文章裡,我們提到了 LinkedList 的多面人生,它即作為 List 的鏈式表,又作為 Queue 的鏈式佇列,又作為 “Stack” 的鏈式棧,功能很全面。相較之下,ArrayList 卻只作為實現了 List 的順序表,為什麼呢?

這是因為在陣列上同時實現 List 和 Queue 時,無法平衡這兩個行為的效能矛盾。具體來說:ArrayList 不允許底層資料有空洞,所有的有效資料都會 “壓縮” 到底層陣列的首部。所以,使用 ArrayList 開發棧的結構或許合適,可以在陣列的尾部操作資料。但使用 ArrayList 開發佇列就不合適,因為在陣列的首部入隊或出隊需要搬運資料。

3.2 使用陣列實現棧結構

使用陣列實現棧相對容易,因為棧結構的操作被限制在陣列的一端,所以我們可以選擇陣列的尾部作為棧頂,並且使用一個 top 指標記錄棧頂位置:

  • 棧空: top == 0;
  • 棧滿: top == n;
  • 入棧: 將資料新增到棧頂位置,均攤時間複雜度是 O(1);
  • 出棧: 將棧頂位置移除,時間複雜度是 O(1);

對於出棧而言,時間複雜度總是 O(1),但是對於入棧而言,卻不一定。因為當陣列的空間不足(top == n)時,就需要擴容和搬運資料來容納新的資料。此時,時間複雜度就從 O(1) 退化到 O(n)。

對於這種大部分操作時間複雜度很低,只有個別情況下時間複雜度會退化,而且這些操作之間存在很強烈的順序關係的情況,就很適合用 “均攤時間複雜度分析” 了:

假設我們的擴容策略是將陣列擴大到舊陣列的 2 倍,用均攤分析法:

  • 1、對於一個大小為 K 的空陣列,在前 K - 1 次入棧操作中,時間複雜度都是 O(1);
  • 2、在第 K 次入棧中,由於陣列容量不足,所以我們將陣列擴大為 2K,並且搬運 K 個數據,時間複雜度退化為 O(K);
  • 3、對於一個大小為 2K 的陣列,在接下來的 K - 1 次入棧操作中,時間複雜度都是 O(1);
  • 4、在第 2K 次入棧中,由於陣列容量不足,所以我們將陣列擴大為 4K,並且搬運 2K 個數據,時間複雜度再次退化為 O(K);
  • 5、依此類推。

可以看到,在每次搬運 K 個次數後,隨後的 K - 1 次入棧操作就只是簡單的 O(1) 操作,K 次入棧操作涉及到 K 個數據搬運和 K 次賦值操作。那我們從整體看,如果把複雜度較高的 1 次入棧操作的耗時,均攤到其他複雜度較低的操作上,就等於說 1 次入棧操作只需要搬運 1 個數據和 1 次賦值操作,所以入棧的均攤時間複雜度就是 O(1)。

入棧的均攤時間複雜度分析

3.3 使用陣列實現佇列結構

使用陣列實現佇列相對複雜,我們需要一個隊頭指標和一個隊尾指標:

  • 隊空: head == tail;
  • 隊滿: tail == n(並不是真的滿,只是無法填充新資料);
  • 入隊: 將資料新增到隊尾位置,均攤時間複雜度是 O(1);
  • 出隊: 將隊頭位置移除,時間複雜度是 O(1)。

對於出隊而言,時間複雜度總是 O(1)。對於入隊而言,當 tail == n 時,就需要擴容和搬運資料來容納新的資料,我們用均攤分析法得出均攤時間複雜度依然是 O(1),就不重複了。

但是我們發現,棧的 top == n 表示棧空間不足,擴容沒有問題,而佇列的 tail == n 卻不一定表示佇列空間不足。因為入隊和出隊發生在不同方向,有可能出現 tail == n 但隊頭依然有非常多剩餘空間的情況。此時,擴容顯得沒有必要。

擴容顯得沒有必要

那麼,怎麼避免沒有必要的擴容和資料搬移呢?—— 迴圈陣列。

我們在邏輯上將陣列的首尾相連,當 tail == n 時,如果陣列頭部還有空閒位置,我們就把 tail 指標調整到陣列頭部,在陣列頭部新增資料。我們下面要分析的 ArrayDeque 資料結構,就是採用了迴圈陣列的實現。

使用迴圈陣列後,佇列空和佇列滿的判斷條件會發生變化:

  • 佇列空: head == tail;
  • 佇列滿: (tail + 1)%size == head,如果 size 是 2 的整數冪,還可以用位運算判斷:(tail + 1) & (size - 1) == head。

理解了使用陣列實現棧和佇列的思路後,下面再來分析 ArrayDeque 的實現原理,就顯得遊刃有餘了。


4. ArrayDeque 原始碼分析

這一節,我們來分析 ArrayDeque 中主要流程的原始碼。

4.1 ArrayDeque 的屬性

  • ArrayDeque 底層是一個 Object 陣列;
  • ArrayDeque 用 headtail 指標指向陣列的 “隊頭位置” 和 “隊尾位置”,需要注意 tail 隊尾指標實際上是指向隊尾最後一個有效元素的下一位。

ArrayDeque 的屬性很好理解的,不出意外的話又有小朋友出來舉手提問了:

  • 🙋🏻‍♀️疑問 1: 為什麼欄位都宣告 private 關鍵字?(回答過多少次了,把手給我放下)
  • 🙋🏻‍♀️疑問 2: 為什麼欄位都宣告 transient 關鍵字?(回答過多少次了,把手給我放下)
  • 🙋🏻‍♀️疑問 3: 為什麼 elements 欄位不宣告為泛型型別 E?(回答過多少次了,把手給我放下)
  • 🙋🏻‍♀️疑問 4:為什麼沒有看到 ArrayList 類似的 MAX_ARRAY_SIZE 最大容量限制?

這個問題我們在分析原始碼的過程中回答。

有了 ArrayList 的分析基礎,問題少了很多,ArrayDeque 真香。

```java public class ArrayDeque extends AbstractCollection implements Deque, Cloneable, Serializable { // 疑問 1:為什麼欄位都宣告 private 關鍵字? // 疑問 2:為什麼欄位都宣告 transient 關鍵字? // 疑問 3:為什麼 elements 欄位不宣告為泛型型別 E? // 疑問 4:為什麼沒有看到 ArrayList 類似的 MAX_ARRAY_SIZE 最大容量限制?

// 底層陣列
transient Object[] elements; // non-private to simplify nested class access

// 隊頭指標
transient int head;

// 隊尾指標
transient int tail;

// new ArrayDeque(0) 最小初始容量
private static final int MIN_INITIAL_CAPACITY = 8;

// 尾指標 - 頭指標
public int size() {
    return (tail - head) & (elements.length - 1);
}

} ```

4.2 ArrayDeque 的構造方法

ArrayDeque 有 3 個建構函式:

  • 1、無參構造方法: 初始化容量為 16 的陣列;
  • 2、帶初始容量的構造方法: 如果初始容量小於 8 (MIN_INITIAL_CAPACITY),則初始化陣列大小為 8。如果初始容量大於 8,則計算 “最近的 2 的整數冪” 作為初始大小。例如 numElements 為 8,則初始化容量為 16。numElements 為 19,則初始化容量為 32;
  • 3、帶集合的構造方法: 用相同的方法建立初始容量為 2 的整數冪的陣列,並呼叫 addAll 逐個新增元素。

ArrayDeque.java

```java // 無參構造方法 public ArrayDeque() { elements = new Object[16]; }

// 帶初始容量的構造方法 public ArrayDeque(int numElements) { allocateElements(numElements); }

// 帶集合的構造方法 public ArrayDeque(Collection<? extends E> c) { allocateElements(c.size()); // 疑問 5:為什麼帶集合的構造方法不使用 Arrays 工具整體複製,而是逐個新增? addAll(c); }

private void allocateElements(int numElements) { elements = new Object[calculateSize(numElements)]; }

// 求離 numElements 最近的 2 的整數冪,即 nextPow2 問題 // 疑問 6:為什麼 ArrayDeque 要求容量是 2 的整數冪? // 疑問 7:calculateSize() 的函式體解釋一下? private static int calculateSize(int numElements) { // 如果 numElements 小於 8(MIN_INITIAL_CAPACITY),則返回 8 int initialCapacity = MIN_INITIAL_CAPACITY; if (numElements >= initialCapacity) { initialCapacity = numElements; // 五輪無符號右移和或運算後,變成最高有效位開始後面都是 1 initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); // 加 1 進位,得到最近 2 的整數冪 initialCapacity++;

    // 變成負數(高位是 1000,低位都是 0000)
    if (initialCapacity < 0)
        // 右移 1 位,取 2^30 為初始容量
        initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;

} ```

AbstractCollection.java

java // 逐個新增元素 public boolean addAll(Collection<? extends E> c) { boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; }

小朋友總有太多的問號,舉手提問 🙋🏻‍♀️

  • 🙋🏻‍♀️疑問 5:為什麼帶集合的構造方法不使用 Arrays 工具整體複製,而是逐個新增?

因為 ArrayDeque 禁止儲存 null 元素,所以需要逐個判斷元素是否為 null 值後才新增。

  • 🙋🏻‍♀️疑問 6:為什麼 ArrayDeque 要求陣列容量是 2 的整數冪?

在迴圈陣列中需要使用取餘運算計算遊標指標迴圈後的位置,例如 (tail + 1) % size,而如果陣列的尺寸 size 是 2 的整數冪,那麼就可以將取餘運算替換為位運算,例如 (tail + 1) & (size - 1),從而提高索引計算的效率。

```java size = 0 0 0 1 0 0 0 0 0 0 // 2^n 的補碼 size - 1 = 0 0 0 0 1 1 1 1 1 1 // 2^n - 1 的補碼 -1 = 1 1 1 1 1 1 1 1 1 1 // -1 的補碼 0 = 0 0 0 0 0 0 0 0 0 0 // 0 的補碼

// 尾指標的迴圈: 1、如果 tail + 1 <= size - 1,則 (tail + 1) & (size - 1) 後保持不變 2、如果 tail + 1 == size,則 size & (size - 1) 為 0 // 頭指標的迴圈 1、如果 head - 1 >= 0,則(head - 1) & (size - 1) 後保持不變 2、如果 head - 1 == -1,則 -1 & (size - 1) 後為 size - 1 ```

  • 🙋🏻‍♀️疑問 7:calculateSize() 的函式體解釋一下?

calculateSize() 是求離 numElements 最近的 2 的整數冪,即 nextPow2 問題。

  • 1、首先,如果 numElements 小於 8(MIN_INITIAL_CAPACITY),則直接返回 8;
  • 2、否則執行 nextPow2 運算,經過五輪無符號右移和或運算,將 numElements 轉換為從最高位開始後面都是 1 的數。再執行 +1 運算,就求出了最近的 2 的整數冪;
  • 3、當 numElements 在 2^30 到 2^ 31-1 之間(即最高位是 0100 的數),計算後得到的 nextPow2 就是負數(最高位是 1000,低位都是 0),此時就需要右移一位,取 2^30 為初始容量。

java n = 0 0 0 0 1 x x x x x //n n = 0 0 0 0 1 1 x x x x //n |= n >>> 1; n = 0 0 0 0 1 1 1 1 x x //n |= n >>> 2; n = 0 0 0 0 1 1 1 1 1 1 //n |= n >>> 4; n = 0 0 0 0 1 1 1 1 1 1 //n |= n >>> 8;(這一步對 n 沒有影響了) n = 0 0 0 0 1 1 1 1 1 1 //n |= n >>> 16;(這一步對 n 沒有影響了) n = 0 0 0 1 0 0 0 0 0 0 //n ++(進位,得到最近 2 的整數冪)

4.3 ArrayDeque 的新增和擴容方法

ArrayDeque 可以在陣列的兩端新增元素,不支援在陣列的中間新增元素:

  • 在隊頭新增: 在 head 指標的上一個位置賦值,如果陣列越界則迴圈到陣列尾部;
  • 在隊尾新增: 在 tail 指標的位置賦值,並將 tail 指標指向下一個位置,如果陣列越界則迴圈到陣列頭部。

```java public void addLast(E e) { // 疑問:為什麼 ArrayDeque 不支援新增 null 元素 if (e == null) throw new NullPointerException(); // tail 指標本身就是指向下一個位置,所以直接填充 elements[tail] = e; // 修改 tail 指標到下一個位置,並通過取餘操作迴圈到陣列頭部 if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); }

public void addFirst(E e) { // 疑問 8:為什麼 ArrayDeque 禁止儲存 null 元素? if (e == null) throw new NullPointerException(); // 修改 head 指標到前一個位置,並通過取餘操作迴圈到陣列尾部 elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); } ```

不出意外小朋友又要出來舉手提問了🙋🏻‍♀️

  • 🙋🏻‍♀️疑問 8:為什麼 ArrayDeque 禁止儲存 null 元素?

其實在 Deque 介面上並不嚴格禁止儲存 null 元素,但是會強烈建議 Deque 的實現不提供儲存 null 值的能力。因為 null 通常會作為一個特殊值來判斷佇列是否為空。

Deque javadoc

bash While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicated that the deque is empty.

java public E pollFirst() { int h = head; E result = (E) elements[h]; // 佇列為空 if (result == null) return null; elements[h] = null; // Must null out slot head = (h + 1) & (elements.length - 1); return result; }

在每次新增元素後,如果隊頭指標和隊尾指標相遇,說明陣列空間已滿,此時就需要擴容操作。ArrayDeque 會將新陣列的容量擴大到舊陣列的 2 倍 ,由於舊陣列的容量也是 2 的整數冪,因此乘以 2 之後依然是 2 的整數冪。

搬運資料的過程就是把 head 頭指標到陣列末尾的元素拷貝到陣列頭部,而剩下的從陣列頭部到尾指標的元素則銜接到後面,使得所有元素規整地排列在陣列的頭部:

java // 擴容操作 private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; // 隊頭指標到陣列末尾的元素個數 int r = n - p; // 容量翻倍 int newCapacity = n << 1; // 容量變成負數 if (newCapacity < 0) // ArrayList 擴容整型溢位時會丟擲 OutOfMemoryError // ArrayDeque 擴容整型溢位時會丟擲 IllegalStateException // 看了一下,發現這兩個容器出自不同作者,不能統一下嗎哈哈 throw new IllegalStateException("Sorry, deque too big"); // 建立新陣列 Object[] a = new Object[newCapacity]; // 將隊頭指標到陣列末尾的元素拷貝到陣列頭部 System.arraycopy(elements, p, a, 0, r); // 拷貝剩下的從陣列頭部到尾指標的元素 System.arraycopy(elements, 0, a, r, p); // 指向新陣列 elements = a; // 重置頭尾指標 head = 0; tail = n; }

擴容操作

  • 🙋🏻‍♀️疑問 4:為什麼沒有看到 ArrayList 類似的 MAX_ARRAY_SIZE 最大容量限制?

現在我們可以回答這個疑問了, ~~網上也有資料說 ArrayDeque 沒有容量限制,最坑的是程式碼註釋也這麼說:“Array deques have no capacity restrictions”。~~ 顯然不是這麼一回事。 第一,陣列的容量顯示是被虛擬機器固化的,不可能無限容量。第二,從 doubleCapacity() 函式可以看出, 最大容量值是 2^30 ,如果超過這個數,在 doubleCapacity() 擴容的時候就會丟擲異常了。

4.4 ArrayDeque 的獲取和移除方法

ArrayDeque 可以在陣列的兩端移除元素,不支援在陣列的中間移除元素:

  • 在隊頭移除: 在 head 指標的位置獲取,再將 head 指向上一個位置,如果陣列越界則迴圈到陣列尾部;
  • 在隊尾移除: 在 tail 指標的下一個位置獲取,如果陣列越界則迴圈到陣列頭部。

```java public E pollFirst() { // head 指標本身就是指向隊頭元素,所以直接獲取 int h = head; E result = (E) elements[h]; if (result == null) return null; elements[h] = null; // 修改 head 指標 head = (h + 1) & (elements.length - 1); return result; }

public E pollLast() { // tail 指標本身是指向隊尾元素的下一個位置,所以需要返回上一個位置 int t = (tail - 1) & (elements.length - 1); E result = (E) elements[t]; if (result == null) return null; elements[t] = null; tail = t; return result; } ```

4.5 ArrayDeque 的迭代器

Java 的 foreach 是語法糖,本質上也是採用 iterator 的方式。ArrayDeque 提供了 2 個迭代器:

  • iterator():DeqIterator(): 正向迭代器
  • ListIterator DescendingIterator(): 反向迭代器

ArrayDeque 迭代器同樣有 fail-fast 機制,不給過ArrayDeque 並沒有使用類似 ArrayList 類似的 modCount 檢查併發修改,而是通過頭尾指標的位置和元素檢查併發修改。這個方法不一定能保證檢測到所有的併發修改情況,例如無法檢查先移除了尾部元素,又馬上添加了一個尾部元素的情況。

```java private class DeqIterator implements Iterator {

private int cursor = head;

private int fence = tail;

private int lastRet = -1;

public boolean hasNext() {
    return cursor != fence;
}

public E next() {
    if (cursor == fence) throw new NoSuchElementException();
    E result = (E) elements[cursor];
    // 無法檢測到所有併發修改的情況
    if (tail != fence || result == null)
        throw new ConcurrentModificationException();
    lastRet = cursor;
    cursor = (cursor + 1) & (elements.length - 1);
    return result;
}
...

} ```


5. 總結

  • 1、ArrayDeque 是基於動態陣列的線性表,具備 Queue 和 Stack 的行為,但不具備 List 的行為;

  • 2、ArrayDeque 的陣列容量是 2 的整數冪,在擴容時容量會翻倍,且不支援 null 元素;

  • 3、ArrayDeque 和 LinkedList 的棧和佇列行為都是 O(1) 時間複雜度,ArrayDeque 的入棧和入隊有可能會觸發擴容,但從均攤分析上看依然是 O(1) 時間複雜度;

  • 4、ArrayDeque 是一塊連續記憶體空間,基於區域性性原理能夠更好地命中 CPU 快取行,而 LinkedList 是離散的記憶體空間對快取行不友好;

  • 5、ArrayDeque 和 LinkedList 都不考慮執行緒同步,不保證執行緒安全。


本文為稀土掘金技術社群首發簽約文章,14天內禁止轉載,14天后未獲授權禁止轉載,侵權必究!

參考資料