LinkedBlockingDeque的源码解析（基于JDK1.8）
LinkedBlockingDeque的定义
LinkedBlockingDeque是一个通过链表实现的双端阻塞队列，如果不指定大小时，则默认的大小是Integer.MAX_VALUE，实现原理与LinedBlockingQueue类似。都是通过ReentrantLock+Condition+链表。
使用LinkedBlockingDeque 有哪些风险呢
1.在未来指定容量的情况下，生产速率远高于消费速率时，会导致内存耗尽OOM。2.高并发场景下，性能远低于LinkedBlockingQueue,因为LinkedBlockingDeque 出队和入队用的是同一把锁，同一时刻只能有一个线程出队和入队，而LinedBlockingQueue出队和入队使用的是不同的锁，同一个时刻可以有一个线程出队，一个线程入队。性能更高。3.由于要维持前后节点的链接，内存消耗也高于LinkedBlockingQueue。
LinkedBlockingDeque的应用场景
并发场景下我们可以用LinkedBlockingDeque作为双端队列使用。
源码解析
节点定义
static final class Node<E> {
/**
* The item, or null if this node has been removed.
* 存放数据，当数据为空时节点会被移除
*/
E item;
/**
* One of:
* - the real predecessor Node
* - this Node, meaning the predecessor is tail
* - null, meaning there is no predecessor
* 前驱节点，指向前一个节点
*/
Node<E> prev;
/**
* One of:
* - the real successor Node
* - this Node, meaning the successor is head
* - null, meaning there is no successor
* 后继节点，指向后一个节点
*/
Node<E> next;
Node(E x) {
item = x;
}
}从上节点的定义我们可以看出，与LinkedBlockingQueue相比就多了一个前驱节点prev。其余的结构与LinkedBlockingQueue相同。
全局变量
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
* 头指针，指向第一个节点
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
* 尾指针，指向最后一个节点
*/
transient Node<E> last;
/** Number of items in the deque */
//队列中元素的个数
private transient int count;
/** Maximum number of items in the deque */
//队列的容量大小
private final int capacity;
/** Main lock guarding all access */
//锁，出队和入队都需要获取锁
final ReentrantLock lock = new ReentrantLock();
/** Condition for waiting takes */
//非空等待条件，等待元素出队
private final Condition notEmpty = lock.newCondition();
/** Condition for waiting puts */
//非满等待条件，等待元素入队
private final Condition notFull = lock.newCondition();全局变量主要是定义队列的容量，头指针，尾指针，锁和等待条件。
构造方法
//无参构造器，调用的话则队列的容量是Integer.MAX_VALUE
public LinkedBlockingDeque() {
this(Integer.MAX_VALUE);
}
//指定容量的队列。
public LinkedBlockingDeque(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
}
如上，构造函数主要是一个指定容量，一个是无参构造器。在实际的应用中我们最好指定队列的容量。防止OOM的异常发生。接下来我们来看看入队和出队方法
入队方法
头插法
public void addFirst(E e) {
if (!offerFirst(e))
throw new IllegalStateException("Deque full");
}
//从队头入队
public boolean offerFirst(E e) {
//如果元素为空抛出NEP
if (e == null) throw new NullPointerException();
//创建一个节点
Node<E> node = new Node<E>(e);
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
return linkFirst(node);
} finally {
//解锁
lock.unlock();
}
}
如上，前面的方法比较简单，主要是做一些参数校验，加锁等操作，核心的入队方法是 linkFirst()方法。接下来我们就来看看linkFirst()方法。
private boolean linkFirst(Node<E> node) {
// 如果元素的数量超过设置的容量，直接返回false
if (count >= capacity)
return false;
//获取头节点
Node<E> f = first;
//将要插入节点的next指针指向头节点
node.next = f;
//然后将要插入的节点设置为头节点
first = node;
//如果尾节点为空
if (last == null)
//将要插入的新节点赋值给尾节点
last = node;
else
//f的前驱指针指向新节点
f.prev = node;
//元素数量加1
++count;
//唤醒非空等待队列里的一个线程
notEmpty.signal();
return true;
}如上，是将新节点插入到队列的头部，无非就是将新节点设置成头节点。接下来，我们来看看尾插法。入队的流程图如下：如下图，插入前假设有a，b，c三个节点。链表的存储结构如下图A所示，现在我们要通过头部入队的方法插入一个元素d之后的变化图如下图B所示，我们可以清楚的看到只是first节点做了前移,所以头插法主要就是移动first节点。
尾插法
前面的代码与头插法相同，只是在入队的时候设值的方式不同而已，下面我们来看看。
private boolean linkLast(Node<E> node) {
// assert lock.isHeldByCurrentThread();
if (count >= capacity)
return false;
//获取尾节点
Node<E> l = last;
//将node 节点的prev指向 last
node.prev = l;
//将node赋值给last
last = node;
if (first == null)
first = node;
else
l.next = node;
//元素的数量加1
++count;
//唤醒非空等待队列里的一个线程
notEmpty.signal();
return true;
}入队的流程图如下, 插入之前同样是a，b，c三个节点。当我们需要通过尾插法插入一个新节点e时，我们只需要找到last节点，然后将last节点的向后移。
出队方法
说完了，入队的方法，接下来，我们就来说说出队的方法。由于是双端队列，所以，同样的元素可以在队头出队，也可以在队尾出队。
队头出队
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;
//队列元素减1
--count;
//唤醒非满队列里的线程
notFull.signal();
return item;
}队头出队的方法相对也比较简单，下面我们以一张流程图说明下：头出队法就是将队列的第一个元素出队。只需要移动first节点。
队尾出队
队尾出队，无非就是将last指针向后移动。
private E unlinkLast() {
// 获取尾节点
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;
//队列元素数量减1
--count;
notFull.signal();
return item;
}尾出队法的流程图如下所示：尾出队法就是将队列的最后一个元素出队。只需要移动last节点。
总结
LinkedBlockingDeque和LinkedBlockingQueue的相同点在于：
1.两者都是基于链表2.两者容量都是可选的，不设置的话默认为int的最大值 不同点在于3.LinkedBlockingDeque是双端链表，可以队头出队，队尾出队。LinkedBlockingQueue是单端队列，队尾入队，队头入队。4.不存在哨兵节点5.LinkedBlockingDeque是一把锁+两个条件，LinkedBlockingQueue是两把锁+两个条件。
参考
LinkedBlockingDeque[1] 深入理解阻塞队列（四）——LinkedBlockingDeque源码分析[2]
References
[1] LinkedBlockingDeque: https://www.cnblogs.com/zhuxudong/p/10079511.html
[2] 深入理解阻塞队列（四）——LinkedBlockingDeque源码分析: https://blog.csdn.net/qq_19431333/article/details/73480305
腾讯云开发者
