第十五篇：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; } }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

从上节点的定义我们可以看出，与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();

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
 

全局变量主要是定义队列的容量，头指针，尾指针，锁和等待条件。

构造方法

  	//无参构造器，调用的话则队列的容量是Integer.MAX_VALUE public LinkedBlockingDeque() { this(Integer.MAX_VALUE); } //指定容量的队列。 public LinkedBlockingDeque(int capacity) { if (capacity <= 0) throw new IllegalArgumentException(); this.capacity = capacity; }


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

如上，构造函数主要是一个指定容量，一个是无参构造器。在实际的应用中我们最好指定队列的容量。防止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(); } }


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

如上，前面的方法比较简单，主要是做一些参数校验，加锁等操作，核心的入队方法是 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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

如上，是将新节点插入到队列的头部，无非就是将新节点设置成头节点。
接下来，我们来看看尾插法。
入队的流程图如下：
如下图，插入前假设有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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

入队的流程图如下, 插入之前同样是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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

队头出队的方法相对也比较简单，下面我们以一张流程图说明下：头出队法就是将队列的第一个元素出队。只需要移动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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

尾出队法的流程图如下所示：尾出队法就是将队列的最后一个元素出队。只需要移动last节点。

总结

LinkedBlockingDeque和LinkedBlockingQueue的相同点在于：

1. 两者都是基于链表
2. 两者容量都是可选的，不设置的话默认为int的最大值
   不同点在于
3. LinkedBlockingDeque是双端链表，可以队头出队，队尾出队。LinkedBlockingQueue是单端队列，队尾入队，队头入队。
4. 不存在哨兵节点
5. LinkedBlockingDeque是一把锁+两个条件，LinkedBlockingQueue是两把锁+两个条件。

参考

LinkedBlockingDeque
深入理解阻塞队列（四）——LinkedBlockingDeque源码分析

文章来源: feige.blog.csdn.net，作者：码农飞哥，版权归原作者所有，如需转载，请联系作者。

原文链接：feige.blog.csdn.net/article/details/104334090