并发集合8-LinkedBlockingDeque源码分析

前言

LinkedBlockingDeque是基于双向链表的双端有界阻塞队列，使用非公平ReentrantLock实现线程安全，默认和最大长度都为Integer.MAX_VALUE；不允许null元素添加；实现骨架和ConcurrentLinkedDeque一样，只是对并发控制的细节不同（volatile+循环CAS），双端队列可以用来实现 "窃取算法" ,两头都可以操作队列，相对于单端队列可以减少一半的竞争。

定义

实现了BlockingDeque接口

重要字段

双向链表节点

first和last节点在初始化时同时为null。

first和last节点状态相对于ConcurrentLinkedDeque的比较简单，因为此first和last节点都为普通变量，并不会因为频繁的读写（相对于volatile变量）造成性能瓶颈。

count：元素数量计数
capacity：队列最大容量

一个ReentrantLock锁，两个Condition。

构造器

无参构造器，默认容量Integer.MAX_VALUE

指定大于0的容量

集合构造器，默认容量Integer.MAX_VALUE，加锁，保证普通变量刷新到主内存中，保证其线程可见性。

offerFirst方法（不响应中断）

offerLast方法（不响应中断）

putFirst方法（响应中断）

如果已经满了，则等待直到队列不满

putLast（响应中断）

offerFirst （响应中断超时）

offerLast（响应中断超时）

pollFirst（不响应中断）

pollLast（不响应中断）

remove方法

两个方法分别遍历队列头尾遍历数组，时间复杂度为O(n)

contains方法

两个方法分别遍历队列头尾遍历数组，时间复杂度为O(n)

size方法

时间复杂度为O(1)

iterator迭代器

迭代器都是弱一致性的，在操作队列元素时需要加锁，但是在迭代操作之间，队列有可能被其他线程修改，当hasNext返回true，但是下一次next和remove方法元素已经被删除了，此时将抛出NoSuchElementException异常。

方法列表

总结

LinkedBlockingDeque性能基本和LinkedBlockingQueue一致，只是双端队列和单端队列的区别，一把锁和两把锁的区别。