同步器(AQS)为什么维护的同步队列是一个双向队列？

Question

为什么要用双端队列呢？单向队列我感觉也可以实现功能，因为大部分的查找只是查找后继节点，或者是判断当前节点的前驱是不是head。另外，同步器维护的waiter的node到底是什么作用？源码的注释是为了指向condition的waiter节点，但是没有特别看明白。

Answer 1

很明显嘛，假如你的队列是单向的如：Head -> N1 -> N2 -> Tail。出队的时候你要获取N1很简单，Head.next就行了，入队你就麻烦了，你要遍历整个链表到N2，然后N2.next = N3;N3.next = Tail。入队的复杂度就是O(n),而且Tail也失去他的意义。相反双向链表出队和入队都是O(1)时间复杂度。说白了空间换时间。