我們來看下節(jié)點類Node

private static class Node<E> {
????E?item; //元素 Nodenext; //向后的節(jié)點鏈接 Nodeprev; //向前的節(jié)點鏈接 Node(Nodeprev,?E?element,?Nodenext)?{ this.item?=?element; this.next?=?next; this.prev?=?prev;
????}
}

10.2 與ArrayList的區(qū)別

• 1.LinkedList的增加和刪除效率相對較高，而查找和修改的效率相對較低。

• 2.以下情況建議使用ArrayList

• 頻繁訪問列表中的一個元素。
• 只在列表的首尾添加元素。

• 3.以下情況建議使用LinkedList

• 頻繁地在列表開頭、中間、末尾添加和刪除元素。
• 需要通過循環(huán)迭代來訪問列表中的元素。

10.3 LinkedList不是線程安全的

LinkedList不是線程安全的，所以可以使用如下方式保證線程安全。

List?list?=?Collections.synchronizedList(new LinkedList<>());

10.4 LinkedList的家庭成員關(guān)系

• LinkedList 繼承了 AbstractSequentialList 類。

• LinkedList 實現(xiàn)了 Queue 接口，可作為隊列使用。

• LinkedList 繼承了 AbstractQueue抽象類，具有隊列的功能。

• LinkedList 實現(xiàn)了 List 接口，可進行列表的相關(guān)操作。

• LinkedList 實現(xiàn)了 Deque 接口，可作為雙向隊列使用。

• LinkedList 實現(xiàn)了 Cloneable 接口，可實現(xiàn)克隆。

• LinkedList 實現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

十一、并發(fā)安全ConcurrentLinkedQueue類

10.1 理解ConcurrentLinkedQueue

• ConcurrentLinked是由鏈表結(jié)構(gòu)組成的線程安全的先進先出無界隊列。
• 當多線程要共享訪問集合時，ConcurrentLinkedQueue是一個比較好的選擇。
• 不允許插入null元素
• 支持非阻塞地訪問并發(fā)安全的隊列，不會拋出ConcurrentModifiationException異常。
• size方法不是準確的，因為在統(tǒng)計集合的時候，隊列可能正在添加元素，導致統(tǒng)計不準。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保證原子性（操作不可分割）
• 添加元素happen-before其他線程移除元素。
• 用法如下：

ConcurrentLinkedQueue?queue?= new ConcurrentLinkedQueue();
BuildingBlockWithName?buildingBlock?= new BuildingBlockWithName("三角形", "A");
concurrentLinkedQueue.add(buildingBlock);

10.2 ConcurrentLinkedQueue類繼承了哪些類？

• AbstractQueue抽象類，具有隊列的功能

10.3 ConcurrentLinkedQueue類實現(xiàn)了哪些接口？

• Queue接口，可作為隊列使用

十二、雙向數(shù)組ArrayDeque類

12.1 理解ArrayDeque

• 由數(shù)組組成的雙端隊列。
• 沒有容量限制，根據(jù)需要擴容。
• 不是線程安全的。
• 禁止插入null元素。
• 當用作棧時，比棧速度快，當用作隊列時，速度比LinkList快。
• 大部分方法的算法時間復雜度為O(1)。
• remove、removeFirstOccurrence、removeLastOccurrence、contains、remove 和批量操作的算法時間復雜度O(n)

12.2 使用方法

創(chuàng)建一個ArrayDeque，往arrayDeque隊尾添加元素。

ArrayDeque?arrayDeque?= new ArrayDeque(); for (int i?= 0;?i?< 50;?i++)?{
????arrayDeque.add(buildingBlock); //?add方法等價于addLast方法 }

12.3 ArrayDeque實現(xiàn)了哪些接口

• Deque接口 - 可用于雙端隊列

十三、雙向并發(fā)ConcurrentLinkedDeque類

13.1 理解ConcurrentLinkedDeque類

• 由鏈表結(jié)構(gòu)組成的雙向無界阻塞隊列
• 插入、刪除和訪問操作可以并發(fā)進行，線程安全的類
• 不允許插入null元素
• 在并發(fā)場景下，計算隊列的大小是不準確的，因為計算時，可能有元素加入隊列。
• 批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保證原子性（操作不可分割）

13.2 ConcurrentLinkedDeque使用示例

創(chuàng)建兩個積木：三角形、四邊形，然后添加到隊列：

BuildingBlockWithName?buildingBlock1?= new BuildingBlockWithName("三角形", "A");
BuildingBlockWithName?buildingBlock2?= new BuildingBlockWithName("四邊形", "B");
ConcurrentLinkedDeque?concurrentLinkedDeque?= new ConcurrentLinkedDeque();
concurrentLinkedDeque.addFirst(buildingBlock1);
concurrentLinkedDeque.addLast(buildingBlock2); //結(jié)果：順序：三角形、四邊形 

13.3 ConcurrentLinkedDeque實現(xiàn)了哪些接口

• Deque接口 - 可用于雙端隊列

十四、數(shù)組阻塞ArrayBlockingQueue類

14.1 理解ArrayBlockingQueue

• ArrayBlockingQueue是一個用數(shù)組實現(xiàn)的有界阻塞隊列。
• 隊列慢時插入操作被阻塞，隊列空時，移除操作被阻塞。
• 按照先進先出（FIFO）原則對元素進行排序。
• 默認不保證線程公平的訪問隊列。
• 公平訪問隊列：按照阻塞的先后順序訪問隊列，即先阻塞的線程先訪問隊列。
• 非公平性是對先等待的線程是非公平的，當隊列可用時，阻塞的線程都可以爭奪訪問隊列的資格。有可能先阻塞的線程最后才訪問訪問隊列。
• 公平性會降低吞吐量。

14.2 ArrayBlockingQueue使用示例

創(chuàng)建兩個積木：三角形、四邊形，然后添加到隊列：

BuildingBlockWithName?buildingBlock1?= new BuildingBlockWithName("三角形", "A");
BuildingBlockWithName?buildingBlock2?= new BuildingBlockWithName("四邊形", "B");
ArrayBlockingQueue?arrayBlockingQueue?= new ArrayBlockingQueue(100, true);
arrayBlockingQueue.add(buildingBlock1);
arrayBlockingQueue.add(buildingBlock2);

14.3 ArrayBlockQueue實現(xiàn)了哪些接口

• Deque接口 - 可用于雙端隊列

十五、鏈表阻塞LinkedBlockingQueue類

15.1 理解LinkedBlockingQueue

• LinkedBlockingQueue具有單鏈表和有界阻塞隊列的功能。
• 隊列慢時插入操作被阻塞，隊列空時，移除操作被阻塞。
• 默認和最大長度為Integer.MAX_VALUE，相當于無界(值非常大：2^31-1)。

15.2 LinkedBlockingQueue使用示例

LinkedList?linkedList1?= new LinkedList();
linkedList1.add("A");
linkedList1.add("B");
linkedList1.add("C");

15.3 LinkedBlockingQueue的應用場景

• 吞吐量通常要高于ArrayBlockingQueue。創(chuàng)建線程池時，參數(shù)runnableTaskQueue（任務隊列），用于保存等待執(zhí)行的任務的阻塞隊列可以選擇LinkedBlockingQueue。靜態(tài)工廠方法Executors.newFixedThreadPool()使用了這個隊列。

15.4 LinkedBlockingQueue實現(xiàn)了哪些接口

• LinkedBlockingQueue繼承了 BlockingQueue類，可作為阻塞隊列使用
• LinkedBlockingQueue繼承了 AbstractQueue抽象類，具有隊列的功能。
• LinkedBlockingQueue實現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

十六、雙向阻塞LinkedBlockingDeque類

16.1 理解LinkedBlockingDeque類

• 由鏈LinkedBlockingDeque = 阻塞隊列+鏈表+雙端訪問
• 線程安全。
• 多線程同時入隊時，因多了一端訪問入口，所以減少了一半的競爭。
• 默認容量大小為Integer.MAX_VALUE?？芍付ㄈ萘看笮?。

16.2 LinkedBlockingDeque的應用場景

LinkedBlockingDeque可以用在“工作竊取“模式中。

工作竊取算法：某個線程比較空閑，從其他線程的工作隊列中的隊尾竊取任務來幫忙執(zhí)行。

16.3 LinkedBlockingDeque實現(xiàn)了哪些接口

• LinkedBlockingDeque繼承了 BlockingDeque類，可作為阻塞隊列使用
• LinkedBlockingDeque繼承了 AbstractQueue抽象類，具有隊列的功能。
• LinkedBlockingDeque實現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

十七、鏈表阻塞LinkedTransferQueue類

17.1 理解LinkedTransferQueue類

LinkedTransferQueue原理圖

LinkedTransferQueue = 阻塞隊列+鏈表結(jié)構(gòu)+TransferQueue

之前我們講“使命必達TransferQueue接口時已經(jīng)介紹過了TransferQueue接口 ，所以LinkedTransferQueue接口跟它相似，只是加入了阻塞插入和移除的功能，以及結(jié)構(gòu)是鏈表結(jié)構(gòu)。

之前的TransferQueue也講到了3個案例來說明TransferQueue的原理，大家可以回看TransferQueue。

17.2 LinkedTransferQueue接口比其他阻塞隊列多了5個方法

• transfer(E e)
• tryTransfer(E e)
• tryTransfer(E e, long timeout, TimeUnit unit)
• getWaitingConsumerCount()
• hasWaitingConsumer()

17.3 LinkedTransferQueue代碼示例

• 創(chuàng)建一個LinkedTransferQueue，生產(chǎn)者1 依次往隊列中添加 A、B、C

生產(chǎn)者1 依次往隊列中添加 A、B、C

• 生產(chǎn)者2 依次往隊列中添加 D、E、F

生產(chǎn)者2 依次往隊列中添加 D、E、F

• 消費者依次從隊列首部開始消費元素，每次消費前，先sleep 2s，來演示transfer方法是否進行了等待。

消費者消費元素

• 運行結(jié)果

生產(chǎn)者1 transfer?A?
生產(chǎn)者2 transfer?D 2s后...
??
消費者??????take?A
生產(chǎn)者1 put?B 2s后...
?????
消費者??????take?D
生產(chǎn)者2 transfer?E 2s后...
??
消費者??????take?B
生產(chǎn)者1 transfer?C

• 代碼執(zhí)行結(jié)果分析

（1）首先生產(chǎn)者線程1和2 調(diào)用transfer方法來傳輸A和D，發(fā)現(xiàn)沒有消費者線程接收，所以被阻塞。

（2）消費者線程過了2s后將A拿走了，然后生產(chǎn)者1 被釋放繼續(xù)執(zhí)行，傳輸元素B，發(fā)現(xiàn)又沒有消費者消費，所以進行了等待。

（3）消費者線程過了2s后，將排在隊列首部的D元素拿走，生產(chǎn)者2繼續(xù)往下執(zhí)行，傳輸元素E，發(fā)現(xiàn)沒有消費者，所以進行了等待。

（4）消費者線程過了2s后，將排在隊列首部的B元素拿走，生產(chǎn)者1傳輸C元素，等待消費者拿走。

（5）消費者不再消費了，所以生產(chǎn)者1和生產(chǎn)者2都被阻塞了，元素C和，元素E都沒有被拿走，而且生產(chǎn)者2的F元素還沒有開始傳輸，因為在等待元素D被拿走。

（6）看下隊列里面確實有C和E元素，而且E排在隊列的首部。

隊列里面的元素

17.4 LinkedTransferQueue實現(xiàn)了哪些接口

• LinkedBlockingDeque繼承了 BlockingQeque類，可作為阻塞隊列使用
• LinkedBlockingDeque繼承了 AbstractQueue抽象類，具有隊列的功能。

十八、傳球好手SynchronousQueue類

18.1 理解SynchronousQueue類

SynchronousQueue原理圖

• 我稱SynchronousQueue為”傳球好手“。想象一下這個場景：小明抱著一個籃球想傳給小花，如果小花沒有將球拿走，則小明是不能再拿其他球的。

• SynchronousQueue負責把生產(chǎn)者產(chǎn)生的數(shù)據(jù)傳遞給消費者線程。

• SynchronousQueue本身不存儲數(shù)據(jù)，調(diào)用了put方法后，隊列里面也是空的。

• 每一個put操作必須等待一個take操作完成，否則不能添加元素。

• 適合傳遞性場景。

• 性能高于ArrayBlockingQueue和LinkedBlockingQueue。

18.2 SynchronousQueue示例

我們創(chuàng)建了兩個線程，一個線程用于生產(chǎn)，一個線程用于消費

• 生產(chǎn)的線程依次put A、B、C三個值

生產(chǎn)的線程依次put A、B、C三個值

• 消費線程使用take來消費阻塞隊列中的內(nèi)容，每次消費前，等待5秒

消費線程每隔5s調(diào)用take方法

• 運行結(jié)果

t1?????put?A?
t2?????take?A 5秒后...

t1?????put?B?
t2?????take?B 5秒后...

t1?????put?C?
t2?????take?C

小結(jié)：說明生產(chǎn)線程執(zhí)行put第一個元素"A" 操作后，需要等待消費者線程take完“A”后，才能繼續(xù)往下執(zhí)行代碼。

18.1 SynchronousQueue應用場景

• 吞吐量通常要高于LinkedBlockingQueue。創(chuàng)建線程池時，參數(shù)runnableTaskQueue（任務隊列），用于保存等待執(zhí)行的任務的阻塞隊列可以選擇SynchronousQueue。靜態(tài)工廠方法Executors.newCachedThreadPool()使用了這個隊列

18.2 SynchronousQueue和LinkedTransferQueue的區(qū)別

• SynchronousQueue 不存儲元素，而LinkedTransferQueue存儲元素。
• SynchronousQueue 隊列里面沒有元素，而LinkedTransferQueue可以有多個存儲在隊列等待傳輸。
• LinkedTransferQueue還支持若傳輸不了，則丟到隊列里面去。
• LinkedTransferQueue還支持若超過一定時間傳輸不了，則丟到隊列里面去。

十九、優(yōu)先級阻塞PriorityBlockingQueue類

19.1 理解PriorityBlockQueue類

PriorityBlockQueue的原理圖

• PriorityBlockQueue = PriorityQueue + BlockingQueue
• 之前我們也講到了PriorityQueue的原理，支持對元素排序。
• 元素默認自然排序。
• 可以自定義CompareTo()方法來指定元素排序規(guī)則。
• 可以通過構(gòu)造函數(shù)構(gòu)造參數(shù)Comparator來對元素進行排序。

19.2 PriorityBlockQueue實現(xiàn)了哪些接口

• LinkedBlockingQueue繼承了 BlockingQueue接口，可作為阻塞隊列使用
• LinkedBlockingQueue繼承了 AbstractQueue抽象類，具有隊列的功能。
• LinkedBlockingQueue實現(xiàn)了 java.io.Serializable 接口，即可支持序列化，能通過序列化去傳輸。

二十、延時阻塞DelayQueue類

20.1 理解DelayQueue

DelayQueue原理圖

• DelayQueue = Delayed + BlockingQueue。隊列中的元素必須實現(xiàn)Delayed接口。

public class DelayQueue<E extends Delayed> extends AbstractQueue<E> implements BlockingQueue<E> {

• 在創(chuàng)建元素時，可以指定多久可以從隊列中獲取到當前元素。只有在延時期滿才能從隊列中獲取到當前元素。

20.2 源碼解析

• 添加元素時，指定延時多久可以從隊列中獲取元素

public boolean offer(E?e, long timeout,?TimeUnit?unit) { return offer(e);
}

• 獲取元素的方法poll需要等待延時時間過了才能獲取到元素

if (first?== null ||?first.getDelay(NANOSECONDS)?> 0) return null; else return q.poll();

poll方法

20.3 應用場景

• 緩存系統(tǒng)的設計：可以用DelayQueue保存緩存元素的有效期。然后用一個線程循環(huán)的查詢DelayQueue隊列，一旦能從DelayQueue中獲取元素時，表示緩存有效期到了。

• 定時任務調(diào)度：使用DelayQueue隊列保存當天將會執(zhí)行的任務和執(zhí)行時間，一旦從DelayQueue中獲取到任務就開始執(zhí)行。比如Java中的TimerQueue就是使用DelayQueue實現(xiàn)的。

20.4 DelayQueue實現(xiàn)了哪些接口

• DelayQueue實現(xiàn)了 BlockingQueue接口，可作為阻塞隊列使用

這一篇花了很多心思在上面，看官方英文文檔、畫原理圖、寫demo代碼，排版。這恐怕是市面上最全最細講解Queue的。