Java 併發集合深度解析：LinkedBlockingDeque 雙向阻塞雙端隊列原理與實戰

Java 併發隊列框架：LinkedBlockingDeque 完整技術剖析

LinkedBlockingDeque 是 JDK 1.6 引入的雙向鏈表實現的阻塞雙端隊列，同時支援 FIFO（隊列）與 FILO（棧）語義，提供豐富的首尾操作 API。本文深度解析其數據結構、雙條件變量協調機制、核心操作源碼、迭代器弱一致性特性與併發測試驗證。

核心特性速覽

• 雙端操作：首尾均可插入/刪除（addFirst/addLast, pollFirst/pollLast）
• 阻塞語義：put/take 系列方法支援滿等待/空等待
• 可選容量：無界（默認 Integer.MAX_VALUE）或有界
• 線程安全：單鎖 + 兩個 Condition 協調
• 實現接口：BlockingDeque、Deque、Queue

數據結構設計

public class LinkedBlockingDeque<E> 
    extends AbstractQueue<E> 
    implements BlockingDeque<E>, java.io.Serializable {
    
    // 雙向鏈表節點
    static final class Node<E> {
        E item;
        Node<E> prev, next;
        Node(E x) { item = x; }
    }
    
    // 核心字段
    transient Node<E> first;  // 隊首
    transient Node<E> last;   // 隊尾
    private transient int count;  // 當前大小
    private final int capacity;   // 容量上限
    
    // 同步機制：單鎖 + 兩條件
    final ReentrantLock lock = new ReentrantLock();
    private final Condition notEmpty = lock.newCondition();  // 非空條件
    private final Condition notFull = lock.newCondition();   // 未滿條件
}

核心操作源碼深度解析

創建構造函數

public LinkedBlockingDeque(int capacity) {
    if (capacity <= 0) throw new IllegalArgumentException();
    this.capacity = capacity;
}

添加操作：offerLast (尾部插入)

public boolean offerLast(E e) {
    if (e == null) throw new NullPointerException();
    Node<E> node = new Node<>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        return linkLast(node);  // 鏈表尾部插入
    } finally { lock.unlock(); }
}

private boolean linkLast(Node<E> node) {
    if (count >= capacity) return false;  // 容量檢查
    Node<E> l = last;
    node.prev = l;
    last = node;
    if (first == null) first = node;
    else l.next = node;
    ++count;
    notEmpty.signal();  // 喚醒等待取元素的線程
    return true;
}

取出操作：takeFirst (首部阻塞取出)

public E takeFirst() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E x;
        while ((x = unlinkFirst()) == null)  // 空則等待
            notEmpty.await();
        return x;
    } finally { lock.unlock(); }
}

private E unlinkFirst() {
    Node<E> f = first;
    if (f == null) return null;
    Node<E> n = f.next;
    E item = f.item;
    f.item = null; f.next = f;  // help GC
    first = n;
    if (n == null) last = null;
    else n.prev = null;
    --count;
    notFull.signal();  // 喚醒等待插入的線程
    return item;
}

迭代器實現：弱一致性快照遍歷

public Iterator<E> iterator() { return new Itr(); }

private class Itr extends AbstractItr {
    Node<E> firstNode() { return first; }
    Node<E> nextNode(Node<E> n) { return n.next; }
}

private abstract class AbstractItr implements Iterator<E> {
    Node<E> next; E nextItem; Node<E> lastRet;
    abstract Node<E> firstNode();
    abstract Node<E> nextNode(Node<E> n);
    
    AbstractItr() {
        lock.lock();
        try {
            next = firstNode();
            nextItem = (next == null) ? null : next.item;
        } finally { lock.unlock(); }
    }
    
    // 跳過已刪除節點 (item == null)
    private Node<E> succ(Node<E> n) {
        for (;;) {
            Node<E> s = nextNode(n);
            if (s == null) return null;
            if (s.item != null) return s;
            if (s == n) return firstNode();  // 循環鏈表保護
            n = s;
        }
    }
    
    public boolean hasNext() { return next != null; }
    public E next() { 
        if (next == null) throw new NoSuchElementException();
        lastRet = next;
        E x = nextItem;
        advance();  // 獲取下一個有效節點
        return x;
    }
    public void remove() { /* 加鎖調用 unlink(lastRet) */ }
}

併發測試驗證

Queue<String> queue = new LinkedBlockingDeque<>();
new Thread(() -> { for (int i=0; i<6; i++) { queue.add("TA"+i); printAll(); } }).start();
new Thread(() -> { for (int i=0; i<6; i++) { queue.add("TB"+i); printAll(); } }).start();

結果：雙線程並發添加與遍歷正常運行，無 ConcurrentModificationException。
對比：改為 LinkedList 必現併發修改異常。

API 分類速查表

總結

LinkedBlockingDeque 通過雙向鏈表 + 單 ReentrantLock + 雙 Condition(notEmpty/notFull) 經典設計，實現了功能最完整的併發雙端隊列。其弱一致性迭代器巧妙利用 item == null 標記已刪除節點，配合 succ() 跳過機制，在無鎖遍歷與併發修改之間達到優雅平衡。掌握其 API 分類與阻塞語義，是構建高性能生產者-消費者、工作盜取隊列、雙端緩衝區的利器。