1.概述
LinkedList 實現了隊列接口 Queue 和雙端隊列接口 Deque ，Java 容器類中還有一個雙端隊列的實現類 ArrayDeque ，它是基於數組實現的。一般來說，由於需要移動元素，數組的插入和刪除效率會非常低，但 ArrayDeque 的效率卻非常高，本章我們就來討論一下它具體是如何實現的。
可能很多讀者認為java開發中容器用的最多的就是ArrayList了，沒有什麼東西ArrayList搞不定的，作為程序員的您有沒有這樣的感覺呢？如果您有這種感覺請您看完我的整篇文章。
1.1 構造方法，老生之談
numElements 表示元素個數，初始分配的空間會至少容納這麼多元素，但空間不是正好 numElements 這麼大。 ArrayDeque 實現了 Deque 接口，同 LinkedList 一樣，它的隊列長度也是沒有限制的， Deque 擴展了 Queue ，有隊列的所有方法，還可以看作棧，有棧的基本方法 push/pop/peek ，此外還包括操作兩端的方法如 addFirst/removeLast 等，具體的使用用法與 LinkedList 類似，我們就不再做過多的講解了。
2.實現原理數據存儲單元
ArrayDeque 內部主要有如下的實例變量：
elements 就是存儲元素的數組。 ArrayDeque 的高效來源於 head 和 tail 這兩個變量，它們使得物理上簡單的從頭到尾的數組變為了一個邏輯上循環的數組，避免了在頭尾操作時的移動操作。從數據存儲單元可以看出，他的結構和ArrayList類似，都是使用了數組，那麼我們可以猜測他的隨機訪問和隊尾添加數據元素與隊尾刪除數據元素效率會和ArrayList一樣高。那麼接下來我們一起分析一下這顆明珠的內核原理。
2.1 循環數組
對於一般數組，比如 arr ，第一個元素為 arr[0] ，最後一個為 arr[arr.length - 1] 。但對於 ArrayDeque 中的數組，它是一個邏輯上的循環數組，所謂循環是指元素到數組尾之後可以接著從數組頭開始，數組的長度、第一個和最後一個元素都與 head 和 tail 這兩個變量有關，其具體實現為：
- 如果 head 和 tail 相同，則數組為空，長度為 0 。
- 如果 tail 大於 head ，則第一個元素為 elements[head] ，最後一個為 elements[tail - 1] ，長度為 tail-head ，元素索引從 head 到 tail - 1 。
- 如果 tail 小於 head ，且為0，則第一個元素為 elements[head] ，最後一個為 elements[elements.length - 1]，元素索引從 head 到 elements.length - 1。
- 如果 tail 小於 head ，且大於0，則會形成循環，第一個元素為 elements[head] ，最後一個是 elements[tail - 1]，元素索引從 head 到 elements.length - 1，然後再從 0 到 tail - 1 。
2.2 構造函數
無參數的構造函數分配了一個長度為 16 的數組。
有參數的構造函數調用了 allocateElements(numElements) 方法，其核心邏輯為：
- 如果 numElements 小於 8，其分配的數組長度就是 8 。
- 如果 numElements 大於等於 8 ，分配的實際長度是基於 numElements 計算出的最接近的一個 2^n 數。例如 numElements 為 10 ，則實際分配的長度為 2^4 = 16 ，如果 numElements 為 32 ，則實際分配長度為： 2^6 = 64 。
2.3 為什麼要分配的實際長度必須要大於 numElements ？
因為循環數組必須至少留出一個空餘的位置， tail 變量指向下一個空位，為了容納 numElements 個元素，至少需要 numElements + 1 個位置。
除了上述兩個構造函數之外， ArrayDeque 還有一個構造方法：
同樣調用 allocateElements 分配數組，隨後調用了 addAll ，而 addAll 只是循環調用了 add 方法。
2.4 從尾部添加元素 add
首先將元素添加到 tail 處，然後 tail 指向下一個位置，即 tail = (tail + 1) & (elements.length - 1)，如果與 head 相同，說明隊列滿了，會調用 doubleCapacity 擴展數組。
這裡重點解釋一下 tail = (tail + 1) & (elements.length - 1) 代碼的原理：
tai + 1 與 elements.length - 1 的 位與 操作就可以得到下一個元素的位置，原因是 elements.length 是 2 的冥次方，而 elements.length - 1 的後幾位全都是 1 。例如，elements.length - 1 = 7 ，二進制為 0111 。
上面兩個 位與 操作都能夠正確找出循環數組中下一個元素的位置。這種位操作是循環數組中一種常見的操作，效率非常高。
2.5 為什麼分配的實際長度是基於 numElements 計算出的最接近的一個 2^n 數 ？
前面我們在講解構造函數時，我們提到了上面的這個規則，但是沒有講解其原因，學習到這裡我們應該明白了，為了支持上述的高效的 位與 操作從而得到下一個元素的位置，因此必須要確保 elements.length 是 2 的冥次方。
doubleCapacity() 方法將數組擴大為兩倍，分配一個長度翻倍的新數組 a ，將 head 右邊的元素複製到新數組開頭處，再複製左邊的元素到新數組中，最後重新設置 head 和 tail ，head 設為 0 ， tail 設為 n ：
我們來看一個例子，假設原長度為 8 ， head 和 tail 為 4 ，現在開始擴大數組，擴大前後的結構如下所示：
2.6 從頭部添加元素 addFirst
在頭部添加，要先讓 head 指向前一個位置，然後再賦值給 head 所在位置。 head 的前一個位置是(head - 1) & (elements.length - 1)。剛開始 head 為 0 ，如果 elements.length 為 8 ，則結果為 位與 操作為 7 。
比如如下的代碼執行：
執行完了之後其內部結構為：
2.7 從頭部刪除元素 removeFirst
將原頭部位置置為 null ，然後 head 置為下一個位置，下一個位置為 (h + 1) & (elements.length - 1) 。
2.8 查看長度 size
2.9 檢查元素是否存在 contains
從 head 開始遍歷並進行對比，循環過程中沒有使用 tail ，而是到元素為 null 就結束了，這是因為在 ArrayDeque 中，有效元素不允許為 null 。
ArrayDeque 的複雜度分析以及應用場景
ArrayDeque 實現了雙端隊列，內部使用動態擴展的循環數組實現，通過 head 和 tail 變量維護數組的開始和結尾，數組長度為2的冪次方，使用高效的位操作進行各種判斷，以及對 head 和 tail 進行維護。其特點為：
- 在兩端添加、刪除元素的效率很高，但是由於支持動態擴展，會產生額外的內存分配以及數組複製開銷，因此，添加 N 個元素的複雜度為 O(N) 。
- 根據元素內容查找效率比較低，為 O(N) 。
- 與 LinkedList 不同，沒有索引位置的概念，不能根據索引位置進行操作；由於沒有索引位置的概念，同樣也無法支持從指定的位置 insert or remove 一個元素。
ArrayDeque 和 LinkedList 都實現了Deque接口，應該用哪一個呢？如果只需要 Deque 接口，從兩端進行操作，一般而言，ArrayDeque 效率更高一些，應該被優先使用；如果同時需要根據索引位置進行操作，或者經常需要在中間進行插入和刪除，則應該選擇 LinkedList 。
閱讀更多 Java高併發框架 的文章
