如果你在网上搜“双端队列”十个回答里有八个会先拿出LinkedList。但在真实的Java项目里单线程场景下的双端队列推荐实现其实是ArrayDeque。我之前负责过一个实时数据流看板要用队列保存最近N条滚动记录最初用LinkedListQPS一起来就频繁创建节点对象、GC毛刺明显改成ArrayDeque之后头尾操作的性能反而更稳定内存占用也降下来。那之后我花时间把ArrayDeque的底层源码完整读了一遍又通过反射和调试器把内部字段的状态打印出来等于是把“底层原理可视化”这件事真正做了一遍。这篇文章就是这次完整过程适合准备面试讲数据结构、想读源码、或者正在优化队列类代码的Java开发者。1. 为什么值得把ArrayDeque翻个底朝天LinkedList不是不行只是代价高1.1 一个真实场景滚动窗口数据结构该选谁做实时看板时业务方要求只保留最近1000条事件旧数据自动淘汰。最直接的写法是用LinkedList因为Deque接口提供了addLast和pollFirst作为FIFO队列用得很顺手。但压测阶段就发现问题LinkedList的每个节点都是一个独立对象节点里还要存prev、next两个引用头部增加、尾部删除时虽然时间复杂度是O(1)可这个O(1)的常数非常大。1000条还好当窗口放大到几十万条时节点对象的创建与回收对年轻代造成不小压力GC日志里Minor GC的次数肉眼可见地变多。后来我换成ArrayDeque代码层面几乎只改了一个类型名因为两者都实现了Deque接口。运行一段时间后GC毛刺明显减少。原因很简单ArrayDeque底层是连续数组元素之间不需要额外的节点指针也没有逐节点分配的开销。这个替换让我意识到很多程序员默认LinkedList是“链表队列”的代名词却忽略了JDK里还有ArrayDeque这个更适合单线程场景的选项。1.2 首部插入、尾部删除LinkedList和ArrayDeque的差距不止在常数如果只看大O复杂度LinkedList和ArrayDeque的addFirst/addLast基本都是O(1)。但复杂度相同不等于实际表现相同。LinkedList每个节点对象大概包括对象头、item引用、next引用、prev引用64位JVM上未压缩时单节点占用往往超过40字节ArrayDeque则是维护一个Object[]每个引用只占4或8字节并且数组在内存中是连续区域遍历时CPU缓存命中率也更高。我自己在JMH里简单测过数据量在10万以上时同样的offer/poll循环ArrayDeque吞吐量明显高于LinkedList尤其当元素本身是不大不小的普通对象时差距能拉开一位数。这个结果并不神秘就是连续内存和离散节点在缓存局部性上的差异。API一样性能却不同这恰恰是值得去看底层实现的原因。1.3 从三个字段开始认识ArrayDeque打开JDK源码ArrayDeque的核心字段不超过这几个public class ArrayDequeE extends AbstractCollectionE implements DequeE, Cloneable, Serializable { transient Object[] elements; transient int head; transient int tail; private static final int MIN_INITIAL_CAPACITY 8; }elements底层对象数组真正存放元素的仓库。head逻辑上第一个元素所在数组下标。tail逻辑上下一个待插入元素的下标注意这里不是最后一个元素的下标。这三个字段组合在一起就是一个典型的环形缓冲区。官方类注释里也明确说ArrayDeque是“resizable-array”实现没有任何存储桶。看到这里你应该能理解ArrayDeque不是拿数组硬套成链表而是靠“循环利用”数组下标来实现双端队列。2. “数组也能首尾相连”环形数组的容量设计与掩码运算2.1 数组长度为什么必须是2的幂ArrayDeque的数组长度有一个硬性规定总保持2的幂次方比如8、16、32、64。这是环形数组能够高效运作的关键。原因在于当长度为2的幂时length - 1的二进制低位全是1这时可以用位运算代替取模index (index 1) (elements.length - 1);如果直接写index (index 1) % elements.length在每次出入队时都要执行一次64位除法性能有额外消耗。而换成按位与CPU只要一条指令就能完成循环回绕。这个设计同时也是环形数组的“防越界”机制。假设长度为16下标15加1变成1616与15做按位与结果是0数组下标又从尾部跳回头部这就是“环形”二字的来源。2.2 从空队列到满队列数组状态是怎么变的我们用默认构造的ArrayDeque演示初始数组长度是16head和tail都从0开始。操作headtail数组内容简要初始00全部nulladdLast(A)01elements[0]AaddLast(B)02elements[0]A, elements[1]BaddFirst(C)152elements[15]CaddLast(D)153elements[2]D注意addFirst(C)这个操作新元素被放到了数组末尾的下标15处但它在逻辑上是队列的开头。数组物理上不是从0开始排列而是从head开始转圈读取。这种“明明是放进尾部读起来却是开头”的错位正是环形数组的核心特征。基础比较薄的同学第一次看往往发蒙画一张环形图就清楚了把数组首尾接成一个圆head指针和tail指针在这个圆上移动越过末尾就自动回到开头。2.3 为什么ArrayDeque不允许存放nullDeque接口本身没规定不能放nullLinkedList也是允许null的。但从ArrayDeque源码能看到pollFirst等操作要把清除掉的槽位置为null以此帮助GC并利用null作为“槽位空闲”的判据。如果允许用户存null就无法区分“这个槽位本来就是空的”和“这个槽位装了一个null值”很多逻辑会变得不可判定。因此ArrayDeque的addFirst/addLast/offerFirst等所有入队方法第一步都是if (e null) throw new NullPointerException();这一点在业务中经常被忽视如果你习惯用LinkedList存null做占位切换到ArrayDeque时要注意。3. 四个核心出入队操作在内存里到底做了什么3.1 addFirst/addLast一写一移方向相反看JDK实现addFirst和addLast的代码非常短public void addFirst(E e) { if (e null) throw new NullPointerException(); final Object[] es elements; es[head (head - 1) (es.length - 1)] e; if (head tail) grow(es.length); } public void addLast(E e) { if (e null) throw new NullPointerException(); final Object[] es elements; es[tail] e; if (head (tail (tail 1) (es.length - 1))) grow(es.length); }addFirst是“先移动指针再写入”把head减1并做掩码回绕得到新下标再把元素写进去。addLast是“先写入再移动指针”先把元素写到当前tail位置再把tail加1并做掩码回绕。两个方向本质上都是“指针在环上移动”。3.2 pollFirst/pollLast取出后为什么要手动置null出队操作和入队是对称的public E pollFirst() { final Object[] es elements; int h head; SuppressWarnings(unchecked) E e (E) es[h]; if (e ! null) { es[h] null; head (h 1) (es.length - 1); } return e; } public E pollLast() { final Object[] es elements; int t (tail - 1) (es.length - 1); SuppressWarnings(unchecked) E e (E) es[t]; if (e ! null) { es[t] null; tail t; } return e; }pollFirst先把head位置的元素取出来然后把该位置置null最后head后移。pollLast先算tail前一个位置取元素、置null、再回写tail。置null这一步不是可有可无如果不做数组里就会残留对已删除对象的强引用对象无法被GC回收在长生命周期队列里很容易造成内存泄漏。这里顺带说明一个误区head tail到底代表空还是满在ArrayDeque的设计里每次插入完成时都会检查head是否等于新的tail如果相等就立即扩容。所以无论在扩容前还是扩容后只要处于正常状态head tail就表示队列为空。满员状态在ArrayDeque中不会作为持久状态存在它会在写满的瞬间被扩容打断。这跟一般教科书里“预留一个空槽位区分空和满”的环形队列略有不同看代码时不要被固有印象带偏。3.3 size、peekFirst/peekLast这些“只看不动”的操作size的计算同样用掩码public int size() { return (tail - head) (elements.length - 1); }当tail大于head时直接相减就是元素个数当tail已经回绕到head前面时按位与会自动把负数补正得到正确的环形距离。peekFirst/peekLast更简单只读head位置和tail前一个位置不移动任何指针SuppressWarnings(unchecked) public E peekFirst() { return (E) elements[head]; } SuppressWarnings(unchecked) public E peekLast() { return (E) elements[(tail - 1) (elements.length - 1)]; }4. 扩容背后的两段复制这还是“环形”在发挥作用4.1 什么时候触发扩容从3.1的代码可以看到每次写入元素后ArrayDeque会检查head与tail是否碰撞。因为grow是在“已经写满”的瞬间被调用的JDK源代码里甚至有注释专门说明这个扩容检查虽然只有在满员时才会真正进入但普通路径上的成本非常低JIT可以把它优化得很好。扩容后的新数组长度是旧长度的两倍这样2的幂性质不丢失掩码运算继续有效。为什么一定要翻倍而不是按固定步长增加因为如果长度不是2的幂所有基于(length - 1)的掩码回绕就会失效整个环形数组的索引计算都要推翻。翻倍同时还能让均摊扩容成本保持在O(1)这是动态数组的通用结论ArrayList也是类似的思路。4.2 数据不是简单整体拷贝而是分两段搬家这是ArrayDeque底层原理中最有意思、也最容易被背漏的细节。假设当前数组长度是16head是10tail是5size为11。此时物理下标10到15存放着队列前6个元素物理下标0到4存放着后5个元素。扩容到32之后如果用普通的Arrays.copyOf整体拷贝新数组里元素还是散在两段逻辑顺序对应不上需要重新排列。经典实现是两段复制private void doubleCapacity() { assert head tail; int p head; int n elements.length; int r n - p; int newCapacity n 1; if (newCapacity 0) throw new IllegalStateException(Sorry, deque too big); Object[] a new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements a; head 0; tail n; }第一段把从head到数组末尾的元素复制到新数组开头第二段把从0到tail的元素接在第一段后面。复制结束后head归零tail等于旧数组长度n也就是当前元素个数。这样新数组里元素连续排列逻辑顺序与物理顺序一致。从效果上看扩容把一个“环形的断裂点”重新焊成了一根直线。只要理解了这一点你看后续再插入元素时head在0、tail从n开始继续增长的形态就非常自然。4.3 为什么要坚持用System.arraycopySystem.arraycopy是JVM底层方法对应内存块复制比for循环逐元素赋值快很多。在扩容这种低频但数据量大的场景里性能差距非常明显。所以读源码时看到arraycopy不要觉得只是写法问题它本身就是性能优化的一部分。5. 可视化实操用一段代码把ArrayDeque内部搬到屏幕上5.1 用反射读取三个private字段源码分析了半天很多人还是停留在“好像懂了”的状态。想要真正可视化最直接的办法是把ArrayDeque的elements、head、tail三个私有字段读出来打印。Java反射可以做这件事import java.lang.reflect.Field; import java.util.ArrayDeque; public class DequeVisualizer { public static void dump(String tag, ArrayDeque? deque) { try { Class? clazz ArrayDeque.class; Field elementsField clazz.getDeclaredField(elements); Field headField clazz.getDeclaredField(head); Field tailField clazz.getDeclaredField(tail); elementsField.setAccessible(true); headField.setAccessible(true); tailField.setAccessible(true); Object[] elements (Object[]) elementsField.get(deque); int head headField.getInt(deque); int tail tailField.getInt(deque); int mask elements.length - 1; System.out.println( tag ); System.out.printf(底层数组长度%d, head%d, tail%d, size%d%n, elements.length, head, tail, deque.size()); for (int i 0; i elements.length; i) { int logicIndex (i - head) mask; System.out.printf(物理下标[%2d] 逻辑下标[%2d] %s%n, i, logicIndex, elements[i]); } } catch (Exception e) { e.printStackTrace(); } } }如果你用的是JDK 9以上的模块化版本直接运行反射代码可能报InaccessibleObjectException这是因为java.base模块默认不开放内部字段。这时候给JVM加一个参数即可--add-opens java.base/java.utilALL-UNNAMED这个参数只用于本地调试学习不要用在生产环境。5.2 物理下标和逻辑下标别搞混上面代码里有个关键换算int logicIndex (i - head) mask;物理下标就是数组的真实位置逻辑下标就是从当前队列头开始数的位置。对普通数组来说二者相等但环形数组里经常不相等。写打印工具时如果不做这一步你会看到head在15、tail在3这样的“诡异”输出却不知道元素真实顺序是什么。加上这一个换算输出立刻可读。5.3 一段真实操作的完整输出用下面的demo做验证public class Demo { public static void main(String[] args) { ArrayDequeString deque new ArrayDeque(); DequeVisualizer.dump(初始状态, deque); deque.addLast(A); deque.addLast(B); DequeVisualizer.dump(addLast A/B, deque); deque.addFirst(C); DequeVisualizer.dump(addFirst C, deque); deque.addLast(D); DequeVisualizer.dump(addLast D, deque); deque.pollFirst(); DequeVisualizer.dump(pollFirst, deque); } }我在本机跑过一次截取关键输出 初始状态 底层数组长度16, head0, tail0, size0 addFirst C 底层数组长度16, head15, tail2, size3 物理下标[ 0] 逻辑下标[ 1] A 物理下标[ 1] 逻辑下标[ 2] B 物理下标[15] 逻辑下标[ 0] C这个输出就是“底层原理可视化”最有说服力的画面逻辑上排在最前面的C物理上放在数组末尾A和B虽然在下标0和1逻辑顺序却在C之后。你盯着源码想半天不如看这样一张表直观。5.4 调试器里也能看不用写代码如果不想用反射打开IDE的Debugger断点在ArrayDeque的使用处也能在Variables面板里看到elements、head、tail字段。IDEA里可以展开elements数组配合Evaluate Expression输入表达式例如deque.size()、elements[deque.head]实时观察指针变化。这种方法适合临时排查问题要沉淀成一个工具类还是反射打印或者写一个测试断言更可靠。6. 看过底层之后ArrayDeque的选型经验与避坑清单6.1 别把ArrayDeque当随机访问数组用ArrayDeque名字里带“Array”但Deque接口没有提供类似get(index)的方法它也不支持按位置索引。如果你需要随机访问中间元素应该用ArrayList而不是ArrayDeque。数组底层不等于随机访问这是很多初学Java的开发者容易混淆的一点。6.2 迭代顺序和物理顺序不一致才是常态Iterator的输出顺序是逻辑顺序从head开始沿着环形数组依次走到tail结束。如果你不先了解环形结构可能会在打印数组时误以为数据“乱序”了。实际上ArrayDeque的迭代器非常稳定先进先出语义不会受影响。需要从尾部反向遍历时用descendingIterator即可。6.3 线程安全与栈场景的选择ArrayDeque没有任何锁或原子操作多线程并发写同一个实例会得到不可预期的结果。单线程栈操作上它明显优于遗留的Stack类因为Stack的每个方法都带synchronized每次调用都有额外同步开销。但如果确实需要线程安全的双端队列不要自己用Collections.synchronizedCollection硬包优先考虑ConcurrentLinkedDeque或者根据业务改用BlockingDeque的实现类。另外还有一个高频踩坑点ArrayDeque不支持null元素如果你原先使用LinkedList保存过null换到这里会直接抛异常。最好在建队列前约定好业务上不需要null或者统一用Optional之类做包装。最后再分享一条我自己的经验别小看那几行掩码运算。很多面试题喜欢问ArrayDeque为什么扩容要翻倍、为什么用按位与代替取模真正上手写一个DequeVisualizer之后你会发现在自己脑子里印下的不是背下来的答案而是活生生的环形图。以后无论分析别的环形队列还是自己设计有界缓冲区都能更快找到感觉。