前沿拓展：java中整形多少位
基于JDK1.8對Java中的ArrayDeque集合的源碼進行了深度解析，包括各種方法的底層實現(xiàn)，在后給出了ArrayDeque和LinkedList的對比案例以及使用建議。
1 ArrayDeque的概述public class ArrayDeque< E > extends AbstractCollection< E > implements Deque< E >, Cloneable, Serializable
ArrayDeque，來自于JDK1.6，底層是采用可變?nèi)萘康沫h(huán)形數(shù)組實現(xiàn)的一個雙端隊列，內(nèi)部元素有序（存放順序），不支持null元素（LinkedList是支持的）。
繼承了AbstractCollection，屬于Java集合體系中的一員，具有Collection體系集合的通用方法，比如通過iterator()獲取iterator迭代器方法。
沒有實現(xiàn)List接口，不具有通過listiterator()獲取更高級的listiterator迭代器的方法，同時不具有通過索引操作元素的一系列方法，例如add(int index, E element)，get(int index)，remove(int index)，set(int index, E element)等一系列方法都沒有！
實現(xiàn)了Deque接口，即“double ended queue，雙端隊列”，因此具有在雙端隊列兩端訪問元素的方法，同時可以模擬“先進先出FIFO”的隊列，也可以模擬“先進后出FILO”的棧。
實現(xiàn)了Cloneable、Serializable標志性接口，支持克隆、序列化操作。
ArrayDeque的實現(xiàn)不是同步的，但可以使用Collections.synchronizedCollection()來轉換成線程的Collection！
ArrayDequed的學習通常伴隨著和LinkedList的對比，關于LinkedList可以看這篇文章：Java的LinkedList集合源碼深度解析以及應用介紹。
2 ArrayDeque的API方法和LinkedList一樣，ArrayDeque由于實現(xiàn)了Deque接口，擁有幾套操作鏈表頭尾的方法，比如插入、獲取、移除，同樣有一些方法會拋出異常，有些是返回一個特殊的值比如null：
行為
第一個元素（頭部）
后一個元素（尾部）
結果
拋出異常
特殊值
拋出異常
特殊值
插入
addFirst(e)
offerFirst(e)
addLast(e)
offerLast(e)
移除
removeFirst()
pollFirst()
removeLast()
pollLast()
獲取
getFirst()
peekFirst()
getLast()
peekLast()
由于Deque接口繼承了 Queue 接口。在將雙端隊列用作隊列時，將得到 FIFO（先進先出）行為。將元素添加到雙端隊列的末尾，從雙端隊列的開頭移除元素。
從 Queue 接口繼承的方法完全等效于 Deque 方法，如下表所示：
Queue 方法
等效 Deque 方法
add(e)
addLast(e)
offer(e)
offerLast(e)
remove()
removeFirst()
poll()
pollFirst()
element()
getFirst()
peek()
peekFirst()
雙端隊列Deque也可用作 LIFO（后進先出）棧，應優(yōu)先使用此接口而不是遺留 Stack 類（關于Stack 的解析可以看：Java的Stack集合源碼深度解析以及應用介紹）。 在將雙端隊列用作棧時，元素被推入雙端隊列的開頭并從雙端隊列開頭彈出。棧方法完全等效于 Deque 方法，如下表所示：
堆棧方法
等效 Deque 方法
push(e)
addFirst(e)
pop()
removeFirst()
peek()
peekFirst()
無論是隊列或者棧，都從雙端隊列的開頭抽取元素。
3 ArrayDeque的源碼解析3.1 主要類屬性/** * 內(nèi)部存儲元素的數(shù)組,即ArrayDeque采用數(shù)組實現(xiàn)的雙端隊列 */ transient Object[] elements; /** * 雙端隊列的頭節(jié)點索引 */ transient int head; /** * 雙端隊列的尾節(jié)點的下一位的索引,即下一個將要被加入到尾部的元素的索引。 */ transient int tail; /** * 新創(chuàng)建的集合使用的小容量。 容量,一定是2的冪 */ private static final int MIN_INITIAL_CAPACITY = 8; 復制代碼從這幾個主要屬性能夠看出來，ArrayDeque使用數(shù)組來實現(xiàn)雙端隊列，并且將數(shù)組的索引當作隊頭或者隊尾的下一位，并且小容量為8，并且容量必須是2的冪次方。
3.2 構造器與初始容量3.2.1 ArrayDeque()public ArrayDeque()
構造一個初始容量為16的空數(shù)組雙端隊列。
public ArrayDeque() { //很簡單,創(chuàng)建一個長度16的空數(shù)組 elements = new Object[16]; } 復制代碼3.2.2 ArrayDeque(int numElements)public ArrayDeque(int numElements)
構造一個指定初始容量的空數(shù)組雙端隊列。
private void allocateElements(int numElements) { //獲取固定的小容量 int initialCapacity = MIN_INITIAL_CAPACITY; // 如果指定容量大于等于固定的小容量 // 那么通過下面的算法 嘗試尋找 大于指定容量的小的2的冪次方 if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } //如果指定容量小于固定的小容量,那么初始容量就是固定的小容量8 //根據(jù)終的容量創(chuàng)建數(shù)組 elements = new Object[initialCapacity]; } 復制代碼我們重點看看尋找真正初始化容量的算法！
第一行是initialCapacity = numElements，將指定容量的值賦值給初始容量；
然后是接下來六行：
initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; 復制代碼這是一個很巧妙的算法，對于傳入的任何一個小于2^30^（大于等于8）的int類型正整數(shù)值initialCapacity，經(jīng)過五次無符號右移和位或操作后，將會得到一個2^k-1^的值，后再自增1，得到2^k^，該2^k^就是大于initialCapacity的小的2的冪次方。
|= 是“位或等”的的連寫，a|=b，即表示a=a|b。這里的|是位或運算符，在計算時先將十進制數(shù)轉換為二進制補碼，位數(shù)對齊，兩個位數(shù)只要有一個為1，結果就為1，否則結果為0。
>>>表示無符號右移，a>>>n，表示數(shù)a右移n位，包括符號位。即先將十進制數(shù)a轉換為二進制補碼，然后帶著符號位向右邊移動n位，左邊的空位都以0補齊，這里的無符號右移a>>>n可以表示為a=a/2^n
這里可能比較可抽象，我們來看案例，假如開始的initialCapacity是8。
8的二進制補碼：0000 0000 0000 0000 0000 0000 0000 1000 >>>1之后變成: 0000 0000 0000 0000 0000 0000 0000 0100 |運算之后變成：0000 0000 0000 0000 0000 0000 0000 1100 >>>2之后變成: 0000 0000 0000 0000 0000 0000 0000 0011 |運算之后變成：0000 0000 0000 0000 0000 0000 0000 1111 >>>4之后變成: 0000 0000 0000 0000 0000 0000 0000 0000 |運算之后變成：0000 0000 0000 0000 0000 0000 0000 1111 >>>8之后變成: 0000 0000 0000 0000 0000 0000 0000 0000 |運算之后變成：0000 0000 0000 0000 0000 0000 0000 1111 >>>16之后變成: 0000 0000 0000 0000 0000 0000 0000 0000 |運算之后變成：0000 0000 0000 0000 0000 0000 0000 1111 自增1之后變成：0000 0000 0000 0000 0000 0000 0001 0000 復制代碼右移運算和位或運算之后的終結果轉換為十進制就是15，然后再自增1，變成16，即計算出大于8的小2次冪為16。
實際上該算法的核心就是通過右移和或運算把這個數(shù)的高位1的所有低位全部轉換為1。由于在java中整型是固定的32位，我們可以看到5次右移操作一共右移了32位數(shù)，這樣對于所以int類型范圍內(nèi)的正整數(shù)的高位1的所有低位全部都可以變?yōu)?。
然后再加上1，二進制向前進位1，后面的所有低位變成0，這樣就獲取了大于n的小2次冪。
后面的代碼則是考慮到的特殊情況：
if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements 復制代碼如果指定初始值是一個特別大的（大于等于2^30^）int類型的值，那么它的二進制補碼為 “01 ……”，這樣在經(jīng)過上面的算法之后，得到的值肯定是0111 1111 1111 1111 1111 1111 1111 1111。后面再自增1，這樣就變成了1000 0000 0000 0000 0000 0000 0000 0000。
我們可以看到，后的結果高位符號位變成了1，這就變成了一個負數(shù)，出現(xiàn)錯誤，實際上這是由于超過了int值的大限制導致的。對于這種情況，ArrayDeque的做法是將該initialCapacity無符號右移一位，這樣它就變成了0100 0000 0000 0000 0000 0000 0000 0000，轉換為10進制就是2^30^，這實際上就是int類型范圍內(nèi)的2次冪的大值（Java的int類型范圍是-2^31^ ~ 2^31^-1）。
總結：
對于指定容量的構造器，它的實際容量并不一定是指定容量，分為三種情況：
如果指定容量numElements小于MIN_INITIAL_CAPACITY，那么實際初始化容量為MIN_INITIAL_CAPACITY；如果指定容量numElements大于等于MIN_INITIAL_CAPACITY且小于2^30^，那么實際初始化容量為大于numElements的小二次冪；如果指定容量numElements大于等于2^30^，那么實際初始化容量為2^30^；補充： 實際上Hashmap的源碼中對于指定初始容量的計算也用到了類似的算法。另外，為什么初始容量一定是2的冪次方呢？下面會有解答！
3.2.3 ArrayDeque(Collection<? extends E> c)public ArrayDeque(Collection<? extends E> c)
構造一個包含指定 collection 的元素的雙端隊列，這些元素按 collection 的迭代器返回的順序排列。
public ArrayDeque(Collection<? extends E> c) { //分配足夠容量的空數(shù)組 allocateElements(c.size()); //批量添加 addAll(c); } public boolean addAll(Collection<? extends E> c) { boolean modified = false; //內(nèi)部是循環(huán)調(diào)用的add方法 for (E e : c) if (add(e)) modified = true; return modified; } 復制代碼3.3 添加的方法3.3.1 添加到尾部的方法public void addLast(E e)
將指定元素插入此雙端隊列的末尾。
/** * 將指定元素添加到雙端隊列的末尾。 * * @param e 需要被添加的元素 */ public void addLast(E e) { //如果被添加的元素為null,則拋出NullPointerException異常 if (e == null) throw new NullPointerException(); //將元素存放在tail位置,即原尾節(jié)點的下一個空節(jié)點位置 elements[tail] = e; /*計算新的下一個尾節(jié)點索引*/ if ((tail = (tail + 1) & (elements.length - 1)) == head) //擴容的方法 doubleCapacity(); } 復制代碼首先，如果被添加的元素為null,則拋出NullPointerException異常；然后插入元素；接著計算新的下一個尾節(jié)點索引，并且判斷是否需要擴容。
主要看計算新的下一個尾節(jié)點索引的算法和擴容機制！
3.3.1.1 計算新索引首先，說明一下使用數(shù)組實現(xiàn)隊列的傳統(tǒng)方法一個缺點，即“假溢出”。對于傳統(tǒng)數(shù)組實現(xiàn)隊列的方式，一般來說頭節(jié)點和尾節(jié)點位于數(shù)組的頭尾部分，如果尾節(jié)點達到了數(shù)組末尾，直接增加尾節(jié)點索引將會導致數(shù)組長度溢出，因此常?？紤]擴容。但是此時該數(shù)組的前半部分還有剩余空間，例如在插入尾節(jié)點時刪除了一些頭節(jié)點），這種現(xiàn)象稱為"假溢出"，因為真實的數(shù)組空間并沒有用完，造成了空間的浪費。關于此在Java中的隊列數(shù)據(jù)結構詳解以及實現(xiàn)案例演示一文中有更加詳細的解釋！
為了優(yōu)化這種“假溢出”的缺點。我們可以取消頭、尾節(jié)點的相對先后位置，例如，如果尾節(jié)點達到了數(shù)組末尾，先不急著擴容數(shù)組，此時將下一個尾節(jié)點的索引置為0索引，即數(shù)組的開頭，然后判斷此時頭索引和下一個尾節(jié)點索引是否重合，如果沒有重合，那么說明該數(shù)組還有可以利用的空間，如果重合那么則可以擴容，這樣就能利用前半部分的空閑空間了。
這種解決方法得到的隊列的頭、尾節(jié)點索引，與數(shù)組索引的頭、尾沒有聯(lián)系，頭節(jié)點索引可能比尾節(jié)點索引值更大，該數(shù)組被“循環(huán)利用”！
在ArrayDeque中，尋找下一個尾節(jié)點的操作就實現(xiàn)了上面的解決算法。并且它的實現(xiàn)也的巧妙，少量的代碼就能夠計算出新的下一個尾節(jié)點的索引的同時還能處理頭、尾索引達到數(shù)組兩端時的情況，終得到的tail值是將會被固定在[0 , elements.length-1]之間。它的算法實現(xiàn)如下：
tail = (tail + 1) & (elements.length - 1) 復制代碼&表示“位與”運算，它會將十進制數(shù)轉換為二進制補碼，然后如果對位都是1，結果為1，否則結果為0，例如當elements.length =8時，tail=7時，下一個尾節(jié)點索引將會是8，此時計算出的值應該變成0，8&7：
0000 1000 -->8 0000 0111 -->7 ————————— 0000 0000 -->0 復制代碼這里還需要解釋：為什么數(shù)組的初始容量一定是2的冪次方？
一個正整數(shù)如果2的冪次方，那么該數(shù)的二進制一定是 “高位是1，低位全是0”的形式；如果該數(shù)減去1之后，它的二進制變成“高位降低一位，并且低位全部變成了1”的形式，上面的8和7，的二進制是1000，7的二進制是0111。
如果我們的elements.length是2的冪次方，那么elements.length-1的二進制就會變成上面所說的低位全部變成1的情況。例如，如果elements.length為8，某一時刻tail為3，那么下一個尾部應該為4，經(jīng)過&計算之后：
0000 0100 -->4 0000 0111 -->7 ———————— 0000 0100 -->4 復制代碼還是得到4，我們可以發(fā)現(xiàn)，對于第一個操作數(shù)tail+1（1~ elements.length），(tail + 1) & (elements.length - 1)的計算結果能夠得到0~ elements.length-1的全部結果。
如果我們的elements.length不是2的冪次方，那么elements.length-1的二進制就會變成“高位降低一位，并且低位全部變成了1”的形式。
例如，如果elements.length為9，某一時刻tail為3，那么下一個尾部應該為4，經(jīng)過&計算之后：
0000 0100 -->4 0000 1000 -->8 —————————— 0000 0000 -->0 復制代碼變成了0，我們可以發(fā)現(xiàn)，對于第一個操作數(shù)tail+1（1~ elements.length），(tail + 1) & (elements.length - 1)的計算結果不能夠得到0~ elements.length-1的全部結果，這樣的話計算出來的下一個尾節(jié)點索引就會有問題。
實際上這里有一個計算規(guī)律。對于正整數(shù)m，n：
如果n=m，那么m&n=n；如果n為2的冪次方，且m<n，那么m&n=0；如果n不為2的冪次方，且m<n，那么m&n=m；如果n為2的冪次方，那么n+1&n=n；如果n不為2的冪次方，那么n+1&n=0；如果elements.length為2的冪次方，那么elements.length-1自然就不是2的冪次方。根據(jù)上面的計算規(guī)律，“數(shù)組容量（長度）必須是2的冪次方”這一要求是為了計算下一個尾節(jié)點索引和頭節(jié)點索引的值的正確性，即為了計算出的索引能夠取到[0~elements.length-1]之間的全部值！
3.3.1.2 擴容機制在通過上面的算法計算出新尾節(jié)點的下一個索引tail之后，我們看到該值將會與head進行比較，如果相等，即下一個尾節(jié)點和頭節(jié)點索引重合了，那么說明說組容量真正的用完了，此時需要進行擴容。
擴容的方法就是doubleCapacity方法，從名字上能夠看出來，擴容增量是原容量的一倍，即變成原容量的兩倍，我們來看具體源碼：
/** * 擴容方法,盡量擴容為原容量的兩倍,但是沒那么簡單 */ private void doubleCapacity() { //斷言 首尾節(jié)點重合 assert head == tail; //保存頭節(jié)點索引值 int p = head; //保存原數(shù)組容量值 int n = elements.length; //獲取頭節(jié)點右側的元素個數(shù) int r = n - p; // number of elements to the right of p //新容量等于原容量左移一位，轉換為十進制計算就是：newCapacity=n*(2^1) int newCapacity = n << 1; //如果新容量小于0,這里肯定又是超過int值上限之后變成負數(shù)的情況了,從這里能夠看出來原容量大于等于2^30之后，擴容后的容量就會小于0 if (newCapacity < 0) //直接拋出異常 throw new IllegalStateException("Sorry, deque too big"); //newCapacity大于0，新建一個數(shù)組 Object[] a = new Object[newCapacity]; /*拷貝原數(shù)組的數(shù)據(jù)到新數(shù)組*/ //拷貝原頭節(jié)點右側的數(shù)據(jù),索引為[p,elements.length-1],到新數(shù)組索引為[0,r-1] System.arraycopy(elements, p, a, 0, r); //拷貝原頭節(jié)點左側的數(shù)據(jù),索引為[0,p-1],到新數(shù)組索引為[r,p-1] System.arraycopy(elements, 0, a, r, p); //通過上面的拷貝,將頭節(jié)點索引重新變成了0,下一個尾節(jié)點索引變成了n(即原數(shù)組的容量,因為此時數(shù)組能夠容納該索引值了) /*改變引用*/ elements = a; //頭節(jié)點索引重新賦值 head = 0; //下一個尾節(jié)點索引重新賦值 tail = n; } 復制代碼我們來總結一下擴容的主要步驟：
首先計算出新容量,使用<<運算計算出理論新容量應該為原容量的兩倍或者為負數(shù)，然后進入步驟2；實際上原容量大于等于2^30^之后，擴容后的容量值就會小于0，即ArrayDeque大容量為2^30^。然后判斷新容量是否小于0，如果小于0那說明新容量超過了int值上限，拋出異常程序結束，如果大于0，那么說明可以擴容，進入步驟3；新建新容量大小的空數(shù)組，拷貝原數(shù)組的數(shù)據(jù)到新數(shù)組，通過兩次拷貝，將頭節(jié)點索引重新變成了0,下一個尾節(jié)點索引變成了原數(shù)組長度。然后改變數(shù)組引用和相關值，擴容結束！3.3.1.3 其他方法public boolean add(E e)
將指定元素添加到雙端隊列的末尾。
public boolean add(E e) { //內(nèi)部調(diào)用addLast的方法 addLast(e); return true; } 復制代碼public boolean offerLast(E e)
將指定元素添加到雙端隊列的末尾。
public boolean offerLast(E e) { //內(nèi)部調(diào)用addLast的方法 addLast(e); return true; } 復制代碼public boolean offer(E e)
將指定元素添加到雙端隊列的末尾。
public boolean offer(E e) { //內(nèi)部調(diào)用offerLast的方法 return offerLast(e); } 復制代碼3.3.2 添加到頭部的方法public void addFirst(E e)
將指定元素插入此雙端隊列的開頭。
public void addFirst(E e) { //判空 if (e == null) throw new NullPointerException(); //計算新的頭節(jié)點索引并且插入元素 //這里的計算方法和下一個尾節(jié)點索引計算方法差不多 elements[head = (head - 1) & (elements.length - 1)] = e; //如果頭節(jié)點索引等于下一個尾節(jié)點索引,那么嘗試擴容 if (head == tail) doubleCapacity(); } 復制代碼我們看看頭節(jié)索引的計算方法：
head = (head - 1) & (elements.length - 1) 復制代碼該方法與下一個尾節(jié)點索引的計算方法差不多，不同之處在于這里的第一個操作數(shù)是head-1，由于初始head是0，這樣當添加第一個數(shù)到頭節(jié)點時，就是-1&(elements.length - 1)，該結果固定返回elements.length – 1，即頭節(jié)點索引是從數(shù)組尾部開始的，然后依次遞減；而前面的下一個尾節(jié)點索引的計算方法中，我們還記得第一個操作數(shù)是tail+1，即尾節(jié)點索引是從數(shù)組頭部開始的，依次遞增，這也是一個有趣的結果！
3.3.2.1 其他方法public boolean offerFirst(E e)
將指定元素插入此雙端隊列的開頭。
public boolean offerFirst(E e) { //內(nèi)部調(diào)用addFirst方法 addFirst(e); return true; } 復制代碼public void push(E e)
將元素推入此雙端隊列所表示的堆棧。換句話說，將元素插入此雙端隊列的開頭。
public void push(E e) { //內(nèi)部調(diào)用addFirst方法 addFirst(e); } 復制代碼3.4 移除的方法3.4.1 移除尾部的方法public E pollLast()
獲取并移除此雙端隊列的后一個元素；如果此雙端隊列為空，則返回 null。
public E pollLast() { //由于tail表示尾節(jié)點的下一個節(jié)點索引,因此這里獲取真正尾節(jié)點的索引 int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") //獲取該索引處的節(jié)點元素result E result = (E) elements[t]; //如果result為null,則返回null if (result == null) return null; //將該索引處空間置空 elements[t] = null; //tail賦值為該索引 tail = t; //返回元素值 return result; } 復制代碼3.4.1.1 其他方法public E removeLast()
獲取并移除此雙端隊列的后一個元素；如果此雙端隊列為空，它將拋出NoSuchElementException異常。
public E removeLast() { //內(nèi)部調(diào)用pollLast方法 E x = pollLast(); //如果返回值為null,則拋出異常 if (x == null) throw new NoSuchElementException(); return x; } 復制代碼3.4.2 移除頭部的方法public E pollFirst()
獲取并移除此雙端隊列的第一個元素；如果此雙端隊列為空，則返回 null。
public E pollFirst() { //獲取頭結節(jié)點索引 int h = head; @SuppressWarnings("unchecked") //獲取該索引處的元素 E result = (E) elements[h]; // 如果該元素為null，則返回null if (result == null) return null; //該索引處空間置空 elements[h] = null; //計算下一個新的頭節(jié)點索引 head = (h + 1) & (elements.length - 1); //返回該元素節(jié)點 return result; } 復制代碼3.4.2.1 其他方法public E removeFirst()
獲取并移除此雙端隊列第一個元素。如果此雙端隊列為空，它將拋出NoSuchElementException異常。
public E removeFirst() { //內(nèi)部調(diào)用pollFirst方法 E x = pollFirst(); //如果返回null.則拋出異常 if (x == null) throw new NoSuchElementException(); return x; } 復制代碼public E remove()
獲取并移除此雙端隊列第一個元素。如果此雙端隊列為空，它將拋出NoSuchElementException異常。
public E remove() { //內(nèi)部調(diào)用removeFirst方法 return removeFirst(); } 復制代碼public E poll()
獲取并移除此雙端隊列所表示的隊列的頭部（換句話說，此雙端隊列的第一個元素）；如果此雙端隊列為空，則返回 null。
public E poll() { //內(nèi)部調(diào)用pollFirst方法 return pollFirst(); } 復制代碼3.4.3 移除指定元素3.4.3.1 移除第一次出現(xiàn)的元素public boolean removeFirstOccurrence(Object o)
從此雙端隊列移除第一次出現(xiàn)的指定元素。如果此雙端隊列不包含該元素，則不作更改。更確切地講，移除第一個滿足 (o == null ? e == null : o.equals(e)) 的元素 e（如果存在這樣的元素）。如果此雙端隊列包含指定的元素（或者此雙端隊列由于調(diào)用而發(fā)生了更改），則返回 true。
public boolean removeFirstOccurrence(Object o) { //null檢查 if (o == null) //如果o為null，則返回false return false; //獲取大索引 int mask = elements.length - 1; //獲取頭節(jié)點索引 int i = head; Object x; //從頭節(jié)點開始循環(huán)查找 while ( (x = elements[i]) != null) { //如果節(jié)點不為null //如果節(jié)點等于o，這里使用equals進行比較的 if (o.equals(x)) { /*調(diào)用delete刪除該位置的元素,并且調(diào)整后續(xù)元素的位置*/ delete(i); //返回true return true; } //索引i的值，類似于添加節(jié)點時的獲取下一個節(jié)點索引的處理方法，即循環(huán)查找 i = (i + 1) & mask; } //走到這一步,說明循環(huán)完畢,還是沒有找到相等的元素，返回false return false; } 復制代碼我們來看delete方法源碼：
/** * 刪除指定索引的元素,并且調(diào)節(jié)其他元素的位置 * * @param i 索引 * @return 如果i到頭節(jié)點比較近則返回false ;如果i到尾節(jié)點比較近則返回true,該返回值在迭代器中會用到 */ private boolean delete(int i) { //一系列斷言，數(shù)據(jù)結構是正確的 checkInvariants(); //保存原數(shù)組的引用 final Object[] elements = this.elements; //獲取大索引,即&運算的第二個操作數(shù) final int mask = elements.length - 1; final int h = head; final int t = tail; //獲取i到頭節(jié)點索引的距離 final int front = (i - h) & mask; //獲取i到尾節(jié)點索引的距離 final int back = (t - i) & mask; // 檢測并發(fā)修改，如果front 大于等于尾節(jié)點到頭節(jié)點的距離，那么說明出現(xiàn)了"并發(fā)修改"，拋出異常 if (front >= ((t - h) & mask)) throw new ConcurrentModificationException(); /*需要移動元素數(shù)量優(yōu)化 如果i到頭節(jié)點比較近，則將該位置到頭部之間的元素進行移動，如果i到尾節(jié)點比較近，則將該位置到尾部之間的元素進行移動 盡量減少移動的元素數(shù)量*/ /*1 如果i到頭節(jié)點比較近*/ if (front < back) { if (h <= i) { //如果i大于等于頭節(jié)點索引h，那么直接arraycopy一次就行了，將[h,i-1]的元素移動至[h+1,i]的位置，如果h=i那么說明不需要移動 System.arraycopy(elements, h, elements, h + 1, front); } else { //如果i小于頭節(jié)點索引h，那么稍微復雜點，因為出現(xiàn)了不連續(xù)的兩段元素，即[h,elements.length - 1]和[0,i-1]，需要arraycopy兩次 //首先將[0,i-1]的元素移動至[1,i]的位置 System.arraycopy(elements, 0, elements, 1, i); //然后將數(shù)組后一個元素(elements.length - 1的索引位置處)移動至開頭(0索引位置處) elements[0] = elements[mask]; //后將[h,elements.length - 1- 1]的元素移動至[h+1,elements.length - 1]的位置 System.arraycopy(elements, h, elements, h + 1, mask - h); } //將原頭節(jié)點位置 置空 elements[h] = null; //計算新的head索引 head = (h + 1) & mask; //返回false return false; } /*2 如果i到尾節(jié)點比較近*/ else { if (i < t) { //如果i小于尾節(jié)點的下一個節(jié)點索引t,那么直接arraycopy一次就行了，將[i+1,t]的元素移動至[i,t-1]的位置 System.arraycopy(elements, i + 1, elements, i, back); //計算新的尾節(jié)點的下一個節(jié)點索引,直接減少1就可以了,因此此時t肯定大于0,減去1不會是負數(shù)；同時不需要手動置空t的位置,因為在上面移動時,后一個元素為null tail = t - 1; } else { //如果i大于等于尾節(jié)點的下一個節(jié)點索引t,那么稍微復雜點，因為出現(xiàn)了不連續(xù)的兩段元素，即[i+1,elements.length - 1]和[0,t]，需要arraycopy兩次 //首先將[i+1,elements.length - 1]的元素移動至[i,elements.length - 1 - 1]的位置 System.arraycopy(elements, i + 1, elements, i, mask - i); //然后將數(shù)組第一個元素(0索引位置處)移動至末尾(elements.length - 1的索引位置處) elements[mask] = elements[0]; //后將[1,t]的元素移動至[0,t - 1]的位置 System.arraycopy(elements, 1, elements, 0, t); //計算新的尾節(jié)點的下一個節(jié)點索引；同時不需要手動置空t的位置,因為在上面移動時,后一個元素為null tail = (t - 1) & mask; } //返回true return true; } } 復制代碼看起來很多，實際上也不是很難，主要注意的其中一個優(yōu)化方案是：先計算出需要刪除的索引到頭節(jié)點和尾節(jié)點的距離，然后取較小的哪一段距離進行元素移動，這樣能減少需要移動的元素的個數(shù)。
public boolean remove(Object o)
從此雙端隊列中移除第一次出現(xiàn)的指定元素。
public boolean remove(Object o) { //內(nèi)部調(diào)用removeFirstOccurrence方法 return removeFirstOccurrence(o); } 復制代碼3.4.3.1 移除后一次出現(xiàn)的元素public boolean removeFirstOccurrence(Object o)
從此雙端隊列移除后一次出現(xiàn)的指定元素。如果此雙端隊列不包含該元素，則不作更改。更確切地講，移除后一個滿足 (o == null ? e == null : o.equals(e)) 的元素 e（如果存在這樣的元素）。如果此雙端隊列包含指定的元素（或者此雙端隊列由于調(diào)用而發(fā)生了更改），則返回 true。
public boolean removeLastOccurrence(Object o) { //null檢查 if (o == null) //如果o為null，則返回false return false; //獲取大索引 int mask = elements.length - 1; //獲取尾節(jié)點的索引 int i = (tail - 1) & mask; Object x; //從尾節(jié)點開始循環(huán)查找 while ( (x = elements[i]) != null) { //如果節(jié)點不為null //如果節(jié)點等于o，這里使用equals進行比較的 if (o.equals(x)) { /*調(diào)用delete刪除該位置的元素,并且調(diào)整后續(xù)元素的位置*/ delete(i); return true; } //索引i的值，類似于添加節(jié)點時的獲取下一個節(jié)點索引的處理方法，即循環(huán)查找,這里是遞減循環(huán) i = (i - 1) & mask; } //走到這一步,說明循環(huán)完畢,還是沒有找到相等的元素，返回false return false; } 復制代碼3.5 獲取的方法3.5.1 獲取頭部的方法public E getFirst()
獲取，但不移除此雙端隊列的后一個元素。如果此雙端隊列為空，它將拋出NoSuchElementException異常。
public E getFirst() { //獲取頭節(jié)點 @SuppressWarnings("unchecked") E result = (E) elements[head]; //如果頭節(jié)點為null,則拋出異常 if (result == null) throw new NoSuchElementException(); return result; } 復制代碼public E peekFirst()
獲取，但不移除此雙端隊列的后一個元素；如果此雙端隊列為空，則返回 null。
public E peekFirst() { // elements[head] is null if deque empty return (E) elements[head]; } 復制代碼pubilc E element()
獲取，但是不移除此隊列的頭。如果此隊列為空，它將拋出NoSuchElementException異常。
public E element() { //內(nèi)部調(diào)用getFirst的方法 return getFirst(); } 復制代碼public E peek()
獲取，但不移除此雙端隊列的第一個元素；如果此雙端隊列為空，則返回 null。
public E peek() { //內(nèi)部調(diào)用peekFirst的方法 return peekFirst(); } 復制代碼3.5.2 獲取尾部的方法public E getLast()
獲取，但不移除此雙端隊列的后一個元素。如果此雙端隊列為空，它將拋出NoSuchElementException異常。
public E getLast() { //獲取尾部元素 @SuppressWarnings("unchecked") E result = (E) elements[(tail - 1) & (elements.length - 1)]; //如果尾節(jié)點為null,則拋出異常 if (result == null) throw new NoSuchElementException(); return result; } 復制代碼public E peekLast()
獲取，但不移除此雙端隊列的后一個元素；如果此雙端隊列為空，則返回 null。
public E peekLast() { return (E) elements[(tail - 1) & (elements.length - 1)]; } 復制代碼3.6 其他方法public boolean contains(Object o)
如果此雙端隊列包含指定元素，則返回 true。更確切地講，當且僅當此雙端隊列至少包含一個滿足 o.equals(e) 的元素 e 時，返回 true。
public boolean contains(Object o) { //判空 if (o == null) return false; int mask = elements.length - 1; int i = head; Object x; //循環(huán)查找,內(nèi)部使用equals判斷是是否相等 while ( (x = elements[i]) != null) { if (o.equals(x)) return true; i = (i + 1) & mask; } return false; } 復制代碼public void clear()
從此雙端隊列中移除所有元素。在此調(diào)用返回之后，該雙端隊列將為空。
public void clear() { int h = head; int t = tail; if (h != t) { // clear all cells head = tail = 0; int i = h; int mask = elements.length - 1; do { //循環(huán)將每一個節(jié)點置空 elements[i] = null; i = (i + 1) & mask; } while (i != t); } } 復制代碼4 ArrayDeque和LinkedList的區(qū)別相同點：
ArrayDeque和LinkedList都實現(xiàn)了Deque接口，都是雙端隊列的實現(xiàn)，都具有操作隊列頭尾的一系列方法。都是非線程的集合。不同點：
ArrayDeque來自JDK1.6，底層是采用數(shù)組實現(xiàn)的雙端隊列，而LinkedList來自JDK1.2，底層則是采用鏈表實現(xiàn)的雙端隊列。
ArrayDeque不允許null元素，而LinkedList則允許null元素。如果僅僅使用Deque的方法，即從隊列兩端操作元素，用作隊列或者棧，并且如果數(shù)據(jù)量比較大，一般來說ArrayDeque的效率要高于LinkedList，其效率更高的原因可能是ArrayDeque不需要創(chuàng)建節(jié)點對象，添加的元素直接作為節(jié)點對象，LinkedList則需要對添加的元素進行包裝為Node節(jié)點，并且還具有其他引用的賦值操作。LinkedList還同時實現(xiàn)了List接口，具有通過“索引”操作隊列數(shù)據(jù)的方法，雖然這里的“索引”只是自己維護的索引，并非數(shù)組的索引，但該功能這是ArrayDeque所不具備的。如果需要對 隊列中間的進行元素的增、刪、改操作，那么你只能使用LinkedList，因此LinkedList的應用（或者說可用方法）更加廣泛。5 性能對比附，使用Deque的方法時的ArrayDeque和LinkedList的性能對比：
/** * @author lx */ public class ArrayDequeTest2 { static ArrayDeque<Integer> arrayDeque = new ArrayDeque<Integer>(); static LinkedList<Integer> linkedList = new LinkedList<Integer>(); public static long arrayDequeAdd() { //開始時間 long startTime = System.currentTimeMillis(); for (int i = 1; i <= 5000000; i++) { arrayDeque.addLast(i); arrayDeque.addFirst(i); } //結束時間 long endTime = System.currentTimeMillis(); //返回所用時間 return endTime - startTime; } public static long arrayDequeDel() { //開始時間 long startTime = System.currentTimeMillis(); for (int i = 1; i <= 5000000; i++) { arrayDeque.pollFirst(); arrayDeque.pollLast(); } //結束時間 long endTime = System.currentTimeMillis(); //返回所用時間 return endTime - startTime; } public static long linkedListAdd() { //開始時間 long startTime = System.currentTimeMillis(); for (int i = 1; i <= 5000000; i++) { linkedList.addLast(i); linkedList.addFirst(i); } //結束時間 long endTime = System.currentTimeMillis(); //返回所用時間 return endTime - startTime; } public static long linkedListDel() { //開始時間 long startTime = System.currentTimeMillis(); for (int i = 1; i <= 5000000; i++) { linkedList.pollFirst(); linkedList.pollLast(); } //結束時間 long endTime = System.currentTimeMillis(); //返回所用時間 return endTime - startTime; } public static void main(String[] args) throws InterruptedException { Thread.sleep(100); long time1 = arrayDequeAdd(); long time3 = arrayDequeDel(); System.out.println("arrayDeque添加元素所用時間====>" + time1); System.out.println("arrayDeque刪除元素所用時間====>" + time3); System.gc(); Thread.sleep(100); long time2 = linkedListAdd(); long time4 = linkedListDel(); System.out.println("linkedList添加元素所用時間====>" + time2); System.out.println("linkedList刪除元素所用時間====>" + time4); } } 復制代碼如果有什么不懂或者需要交流，可以留言。另外希望點贊、收藏、關注，我將不間斷更新各種Java學習文章！
拓展知識：java中整形多少位
首先，java有八大基本數(shù)據(jù)類型：byte：8位，大存儲數(shù)據(jù)量是255，存放的數(shù)據(jù)范圍是-128~127之間。
short：16位，大數(shù)據(jù)存儲量是65536，數(shù)據(jù)范圍是-32768~32767之間。
int：32位，大數(shù)據(jù)存儲容量是2的32次方減1，數(shù)據(jù)范圍是負的2的31次方到正的2的31 次方減1。
long：64位，大數(shù)據(jù)存儲容量是2的64次方減1，數(shù)據(jù)范圍為負的2的63次方到正的2的63次方減1。
float：32位，數(shù)據(jù)范圍在3.4e-45~1.4e38，直接賦值時必須在數(shù)字后加上f或F。
double：64位，數(shù)據(jù)范圍在4.9e-324~1.8e308，賦值時可以加d或D也可以不加。
boolean：只有true和false兩個取值。
char：16位，存儲Unicode碼，用單引號賦值。
其中，int,short,long,為整型變量（整型，即有范圍限制的整數(shù)）。
除以上類型，其它均為非整型
float,double，為浮點數(shù)（即帶有小數(shù)的數(shù)字）。
char,為字符型，如 char tmp = 'a';(單引號)
byte，字節(jié)型，如 byte tmp= 0;
boolean,布爾型，如 boolean tmp = false;
知識拓展，String 是引用數(shù)據(jù)類型，不是字符型，注意區(qū)分！
整型變量指的就是整數(shù)，用int表示，如可以定義整型變量x為：int x=1,不屬于整型變量那就是非整型變量咯!
java中長整形類型為:long,
定義就像定義整型(int),字符串(String)一樣.
long a = 1L; // L標識長整型數(shù)值 追答 用下面的語句就行
long var = 2L; int(4字節(jié)),long(8字節(jié)），一字節(jié)8bits
能表示更大的數(shù) 本回答被網(wǎng)友采納
還有其他疑惑？想了解更多？可以點擊 【在線咨詢】
