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

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

10.2 與ArrayList的區(qū)別

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

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

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

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

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

10.3 LinkedList不是線程安全的

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

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

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

• LinkedList 繼承了 AbstractSequentialList 類。

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

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

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

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

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

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

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

10.1 理解ConcurrentLinkedQueue

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

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

10.2 ConcurrentLinkedQueue類繼承了哪些類？

• AbstractQueue抽象類，具有隊(duì)列的功能

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

• Queue接口，可作為隊(duì)列使用

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

12.1 理解ArrayDeque

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

12.2 使用方法

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

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

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

• Deque接口 - 可用于雙端隊(duì)列

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

13.1 理解ConcurrentLinkedDeque類

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

13.2 ConcurrentLinkedDeque使用示例

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

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

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

• Deque接口 - 可用于雙端隊(duì)列

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

14.1 理解ArrayBlockingQueue

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

14.2 ArrayBlockingQueue使用示例

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

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實(shí)現(xiàn)了哪些接口

• Deque接口 - 可用于雙端隊(duì)列

十五、鏈表阻塞LinkedBlockingQueue類

15.1 理解LinkedBlockingQueue

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

15.2 LinkedBlockingQueue使用示例

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

15.3 LinkedBlockingQueue的應(yīng)用場(chǎng)景

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

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

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

十六、雙向阻塞LinkedBlockingDeque類

16.1 理解LinkedBlockingDeque類

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

16.2 LinkedBlockingDeque的應(yīng)用場(chǎng)景

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

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

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

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

十七、鏈表阻塞LinkedTransferQueue類

17.1 理解LinkedTransferQueue類

LinkedTransferQueue原理圖

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

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

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

17.2 LinkedTransferQueue接口比其他阻塞隊(duì)列多了5個(gè)方法

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

17.3 LinkedTransferQueue代碼示例

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

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

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

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

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

消費(fèi)者消費(fèi)元素

• 運(yùn)行結(jié)果

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

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

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

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

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

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

（5）消費(fèi)者不再消費(fèi)了，所以生產(chǎn)者1和生產(chǎn)者2都被阻塞了，元素C和，元素E都沒有被拿走，而且生產(chǎn)者2的F元素還沒有開始傳輸，因?yàn)樵诘却谼被拿走。

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

隊(duì)列里面的元素

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

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

十八、傳球好手SynchronousQueue類

18.1 理解SynchronousQueue類

SynchronousQueue原理圖

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

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

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

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

• 適合傳遞性場(chǎng)景。

• 性能高于ArrayBlockingQueue和LinkedBlockingQueue。

18.2 SynchronousQueue示例

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

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

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

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

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

• 運(yùn)行結(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第一個(gè)元素"A" 操作后，需要等待消費(fèi)者線程take完“A”后，才能繼續(xù)往下執(zhí)行代碼。

18.1 SynchronousQueue應(yīng)用場(chǎng)景

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

18.2 SynchronousQueue和LinkedTransferQueue的區(qū)別

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

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

19.1 理解PriorityBlockQueue類

PriorityBlockQueue的原理圖

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

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

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

二十、延時(shí)阻塞DelayQueue類

20.1 理解DelayQueue

DelayQueue原理圖

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

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

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

20.2 源碼解析

• 添加元素時(shí)，指定延時(shí)多久可以從隊(duì)列中獲取元素

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

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

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

poll方法

20.3 應(yīng)用場(chǎng)景

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

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

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

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

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