前言
今天我們繼續(xù)分析 java 并發(fā)包的源碼，今天的主角是誰呢？ConcurrentLinkedQueue，上次我們分析了并發(fā)下 ArrayList 的替代 CopyOnWriteArrayList，這次分析則是并發(fā)下 LinkedArrayList 的替代 ConcurrentLinkedQueue， 也就是并發(fā)鏈表。
Demo
該類繼承結(jié)構(gòu)如下：
該類是 Collection 框架下的實現(xiàn)。也就是Java 類庫提供的數(shù)據(jù)結(jié)構(gòu)。
add 方法將指定元素插入此隊列的尾部。
poll 方法 獲取并移除此隊列的頭，如果此隊列為空，則返回 null。
peek 方法 獲取但不移除此隊列的頭；如果此隊列為空，則返回 null。
那么我們就看看 doug lea 是如何實現(xiàn)并發(fā)安全的吧。在這之前，我們可以試想一下，實現(xiàn)并發(fā)安全無非兩種方式，一種是鎖，就像我們之前分析的容器，比如 concurrentHashMap，CopyOnWriteArrayList ， LinkedBolckingQueue，還有一種是 CAS，在這些容器里也用到了。那么，如果是我們來實現(xiàn)這個隊列，使用什么方式呢？有趣的問題。
開始看源碼吧。
add 方法源碼剖析
實際上是調(diào)用 offer 方法，add 方法是 Collection 接口規(guī)定的容器方法，而 offer 方法是 Queue 接口的方法。
那我們就看看 offer 方法：
public boolean offer(E e) {
// 檢查是否是null，如果是null ，拋出NullPointerException
checkNotNull(e);
// 創(chuàng)建一個node 對象，使用 CAS 創(chuàng)建對象
final Node<E> newNode = new Node<E>(e);
// 輪詢鏈表節(jié)點，知道找到節(jié)點的 next 為null，才會進(jìn)行賦值
for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
// 找到null值之后將剛剛創(chuàng)建的值通過CAS放入
if (p.casNext(null, newNode)) {
// 因為 p 遍歷在輪詢后會變化，因此需要判斷，如果不相等，則使用CAS將新節(jié)點作為尾部節(jié)點。
if (p != t)
casTail(t, newNode); // Failure is OK.
// 放入成功后返回 ture
return true;
}
}
// 輪詢后 p 有可能等于 q，此時，就需要對 p 重新賦值。
else if (p == q)
// 這里需要注意一下：判斷t != t，是因為并發(fā)下可能 tail 被改了，如果被改了，則使用新的 t，否則從鏈表頭重新輪詢。
p = (t != (t = tail)) ? t : head;
else
// 同樣，當(dāng) t 不等于 p 時，說明 p 在上面被重新賦值了，并且 tail 也被別的線程改了，則使用新的 tail，否則循環(huán)檢查p的下個節(jié)點
p = (p != t && t != (t = tail)) ? t : q;
}
}
代碼行數(shù)很少，樓主注釋也寫了，這里可以看到 doug lea 使用了 CAS 的方式防止并發(fā)錯誤，同時，也看得出對 tail 變量被修改的擔(dān)憂，通過 t != t 的判斷，來檢查 tail 是否被其他線程修改了，而這個offer 操作，如果不成功，則永遠(yuǎn)不會返回，這個隊列同時也是無界的。這點在使用的時候需要注意一下。
那么 poll 方法如何實現(xiàn)呢？
poll 方法源碼剖析
public E poll() {
// 循環(huán)跳出標(biāo)記，類似goto
restartFromHead:
// 死循環(huán)
for (;;) {
// 死循環(huán)，從 head 開始遍歷
for (Node<E> h = head, p = h, q;;) {
E item = p.item;
// 如果 head 不是null 且 將 head 的 item 屬性設(shè)置為null成功，則返回并更新頭節(jié)點
if (item != null && p.casItem(item, null)) {
// 如果 p ！= h 說明在 p 輪詢時被修改了
if (p != h)
// 如果p 的next 屬性不是null ，將 p 作為頭節(jié)點，而 q 將會消失
updateHead(h, ((q = p.next) != null) ? q : p);
return item;
}
// 如果 p（head） 的 next 節(jié)點 q 也是null，則表示沒有數(shù)據(jù)了，返回null，則將 head 設(shè)置為null
// 注意： updateHead 方法最后還會將原有的 head 作為自己 next 節(jié)點，方便offer 連接。
else if ((q = p.next) == null) {
updateHead(h, p);
return null;
}
// 如果 p == q，說明別的線程取出了 head，并將 head 更新了。就需要重新開始
else if (p == q)
// 從頭開始重新循環(huán)
continue restartFromHead;
// 如果都不是，則將 h 的 next 賦給 h，并重新循環(huán)。
else
p = q;
}
}
}
上面樓主已經(jīng)寫了注釋，但是有一個非常困擾哦樓主的疑點，就是 else if （p == q） 這行代碼，樓主分析的沒有問題，但是再樓主的單線程測試這段代碼時，出現(xiàn)了詭異的情況，無法解釋，因此， 樓主貼出測試用例，大家一起看看：
測試代碼：
斷點代碼：
注意，斷點位置一定要和我的一致。會出現(xiàn)一些奇怪的效果。樓主無法解釋，因為這個問題，樓主一直都不敢發(fā)這篇文章出來，但樓主覺得有必要說出這個問題，拋磚引玉。
問題在于：單線程怎么會進(jìn)入這段代碼？按道理，但線程是不會出現(xiàn)這個情況的。
總結(jié)
這次的源碼分析讓樓主很痛苦，網(wǎng)上很多的文章也無法解釋這是為什么，希望有高人能告訴樓主，到底是怎么回事？
