LinkedBlockingDeque概述

LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列，支持O(1)的时间复杂度从两端插入和移除元素，如不指定边界，则为Integer.MAX_VALUE。

由一个ReentrantLock保证同步，使用conditions来实现等待通知。

类图结构及重要字段

public class LinkedBlockingDeque<E>     extends AbstractQueue<E>     implements BlockingDeque<E>, java.io.Serializable {      private static final long serialVersionUID = -387911632671998426L;      /** 双向链表节点 */     static final class Node<E> {         E item;         Node<E> prev;         Node<E> next;         Node(E x) {             item = x;         }     }      /**      * 指向第一个节点      * Invariant: (first == null && last == null) ||      *            (first.prev == null && first.item != null)      */     transient Node<E> first;      /**      * 指向最后一个节点      * Invariant: (first == null && last == null) ||      *            (last.next == null && last.item != null)      */     transient Node<E> last;      /** 节点数量 */     private transient int count;      /** 队列容量 */     private final int capacity;      /** 保证同步 */     final ReentrantLock lock = new ReentrantLock();      /** take操作发生的条件 */     private final Condition notEmpty = lock.newCondition();      /** put操作发生的条件 */     private final Condition notFull = lock.newCondition();      }

linkFirst

尝试将节点加入到first之前，更新first，如果插入之后超出容量，返回false。

private boolean linkFirst(Node<E> node) {         // assert lock.isHeldByCurrentThread();         if (count >= capacity)             return false;         Node<E> f = first;         node.next = f;         first = node;         if (last == null)             last = node;         else             f.prev = node;         ++count;         notEmpty.signal();         return true;     }

linkLast

在last节点后加入节点node，更新last。如果插入之后超出容量，返回false。

private boolean linkLast(Node<E> node) {         // assert lock.isHeldByCurrentThread();         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();// 满足notEmpty条件         return true;     }

unlinkFirst

移除first节点，并返回其item值，如果队列为空，则返回full。

private E unlinkFirst() {         // assert lock.isHeldByCurrentThread();         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();// 满足notFull条件         return item;     }

unlinkLast

移除last节点，并返回其item值，如果队列为空，则返回full。

private E unlinkLast() {         // assert lock.isHeldByCurrentThread();         Node<E> l = last;         if (l == null)             return null;         Node<E> p = l.prev;         E item = l.item;         l.item = null;         l.prev = l; // help GC         last = p;         if (p == null)             first = null;         else             p.next = null;         --count;         notFull.signal(); // 满足notFull条件         return item;     }

unlink

移除任意一个节点，注意这里并没有操作x本身的连接，因为它可能仍被iterator使用着。

void unlink(Node<E> x) {         // assert lock.isHeldByCurrentThread();         Node<E> p = x.prev;         Node<E> n = x.next;         // 移除的是first         if (p == null) {             unlinkFirst();         // 移除的是last         } else if (n == null) {             unlinkLast();         } else {             // 移除的是中间节点             p.next = n;             n.prev = p;             x.item = null;             // Don't mess with x's links.  They may still be in use by             // an iterator.             // 这里x的prev和next指针都没有改变，因为他们可能在被iterator使用             --count;             notFull.signal();         }     }