上一篇介绍了ArrayBlockingQueue的源码，这节我们介绍它的兄弟，基于链表的实现，直接开看
head见名知意：这里必须要说的是一个好的名字，真的能够给阅读者带来不一样的便利。我读过的源码，是深有体会的。也就是我们链表的头
tail同样我们可以知道是尾巴节点，二者都是一个Node类型，我们看看这个类的定义
只有2个属性，一个是泛型，一个是指向下一个节点的next。
下面是构造函数，一个带集合对象参数的构造函数，一个无参构造函数
如果是无参的直接把头尾都初始化为null，
如果是有参数的，则如下图，遍历我们传进来的集合，然后取出每一个对象，并且包装为node对象，然后遍历并且调用node的lazySetNext执行链条指针设置，通过名字可以理解为是一个延迟设置，并且把t永远指向最新加入的一个。最后然后把head和tail指向了h和t。
我们下面看看lazySetNext的方法实现
这里直接调用了UNSAFE对象的putorderedObject方法，三个参数分别是当前node，偏移量，下一个node对象。从下图中可知，node在初始化的时候根据node类的类对象通过反射获取了next这个属性，我们node类的next属性就是指向的下一个node,然后通过UNSAFE的objectFieldOffset设置为偏移量。这里可以理解为，每次我创建node对象的时候，通过反射机制，返回一个新的node，然后设置为属性偏移量。有兴趣的同学可以去读下反射的这些源码，反射返回的是一个复制的新对象。也就是说我们每次初始化的时候已经对node里面的nextNode通过反射也进行了初始化。
这里不知道大家注意到没，我们并没有设置边界，也就是说很可能链表队列是一个无边界的。
这里提出个问题：队列的大小怎么维护的，目前为止我们还没有看到过队列大小的属性值。
下面我们看add方法，
通过解读可以知道，是没有边界的，所以add方法永远会成功
这里调用了offer方法，我们来看看offer实现
这里假设我们第一次添加一个节点1，然后此时tail为null，然后p.next为null，然后用cas改变head为节点1，tail的next改变为指向自己
接下来我们添加第二个节点2，此时tail为null，t为null，p为null，p.next为自身，显然q不为null，然后q==p，然后通过三目运算符把p指向了节点1.
过程如下图：
后面的继续追加基本就是这个模式了，这里用了个for循环，在并发下保证能追加进去。
这里有一个问题我也搞不清楚，从后面的节点debug查看，CAS算法的确是把next指向了新入的节点，但是当第一个节点null的时候，用CAS产生的效果是，head指向了新加入节点，tail的next指向了自身。我一直也没搞明白，然后在加入节点后把这个Null的节点丢弃掉。至此，无锁的linkedqueue的追加就完成了。
下面我们来看poll方法，poll方法总是弹出第一个，也就是先进先出。从这里可以看得出在并发下，如果产生竞争，也是通过不停的修改head的for循环来进行弹出的。这里p.casitem后同时会把下一个节点升级为head。这里如果多线程环境下，当一个线程拿到了某一个节点a,第二个线程也拿到了a,但是抢先去拿走了值，此时a节点的下一个节点为null，这时候head也为Null，然后p.next为null，h为null,所以直接返回了null值。如果P.next指向了自身，则满足第三个判断，然后这时候跳过本次循环从最上面开始再次进入循环。如果q=p.next不为null，p也不和q相等，则直接把p指向next，然后再次循环。这样就基本解决了所有的可能性：
需要弹出的p节点不为Null
需要弹出的p节点为null，但是下个节点不为null，但指向自己
需要弹出的p节点为null，但是下个节点不为null，但也不指向自己
需要弹出的节点为null，下一个也为null，然后返回null。
peek操作总返回head，但是不从链接上删除，这里的判断条件为，当前节点的item如果不为null，则直接对自身进行一个uphead，如果当前节点的item为null，则继续比价当前节点的下一个节点是不是null，如果是null，则进行一个伪head替换，然后返回Null,如果不是则比较当前节点与当前节点的下一个节点是不是相等，如果相等则跳过本次循环继续从头开始，如果不相等则把当前节点指向下个节点，然后再次循环。
isempty方法是拥来查看是否为空
调用的是first,方法，这里面进行了比较判断，也是基于两个for嵌套循环，这个给我们对于并发下实现无锁模型算法提供了非常好的思路。如果当前节点的item不为null，进行一个伪head替换，然后返回当前节点，如果为null，则查看下一个节点是不是null，如果是null，则进行一个伪升级，然后返回null，如果下一个节点不为null，则考虑是不是指向自身，如果是则重新开始循环，如果不是，则把当前节点指向下一个然后继续循环。
size方法，前面我们注意到了，在这个queue中并未维护关于大小的数字，我们接下来看size怎么实现，这里是在size方法里面进行统计的，在原文注释中解释这个返回值并不准确，并发条件下的追加和删除都可能使得返回的size不正确。
contains(o)方法返回是否包含此对象，由方法可以看出，通过遍历这个链条来比较，直到当前的p为null为止。并发条件下仅仅可以作为判断是否曾经存在过，也许在返回true的那一刻，就被消费掉了。这种状态仅仅保证存在过，不保证下一刻存在。
remove方法需要指定删除，也是需要遍历整个链条，如果找到了则立马把当前的item修改为null，然后获取到下一个节点，然后用前一个指向下一个完成删除。这里的删除分2步，第一步首先把item修改为Null,第二步然后修改前一个链条和下一个链条的关系完成删除。
toArray返回一个Object数组，但是对链条中的节点不进行删除操作
，
toArray数组返回到奥指定的数组中，从源码中可以看到，能返回指定的数组
addAll方法可以直接批量添加一个集合，首先对集合遍历，然后把每一个对象包装为node，然后先将这个集合进行自身链条化，而不是一个个先追加到原来的链条上，这样既能保证我们集合的连续性，同时也避免了并发条件下带来的复杂性。
当上面的链条完成后，我们开始往我们真正的链条上追加，可以看到如果tail的next为null，则直接把我们前面链条的第一个然后连接到next即可，然后把tail指向最后一个，如果失败后先把t指向tail然后把最后一个的next指向null,再进行一次tail的改变。
至此我们整个源码都结束了，由此引出来的2个问题
第一：如果CAS时，需要修改的对象为null的node，则我们会把目标对象变为我们的head，然后把null的node的next指向自身
第二：在我们poll的时候，也可以看出这一点来，如果当前节点为null，则直接把目标对象变为我们的head.这里不知道是CAS的算法，还是java自身对CAS的进一步优化呢？
整个LinkedBlockQueue是无锁的，全部都基于for循环和CAS算法，而且也是无界的。
关于这个的优势就是真的快，无锁并发下，通过不停的循环来追加，会很快，因此也会比较耗内存和CPU，因为如果不对请求线程限制，同一时间会有很多线程在不停的抢cpu资源，他们不存在线程终结的概念，只有线程执行完。
网友评论