ArrayDeque循环数组原理深度解析

在文章实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《ArrayDeque循环数组实现原理详解》，聊聊，希望可以帮助到正在努力赚钱的你。

ArrayDeque 的 head 指向队首元素，tail 指向下一个要插入位置，二者在固定数组中通过模运算（位运算优化）循环移动；扩容按需扩至最小2的幂，禁止 null 元素以确保 peek 返回 null 即为空。

ArrayDeque 的 head 和 tail 怎么动？

它不是靠“移动数组”，而是靠两个整数指针在固定大小的数组里绕圈走。head 指向队首元素，tail 指向**下一个要插入的位置**（不是队尾元素）。两者初始都是 0，插入时 tail++，弹出时 head++；当越界就模数组长度，形成循环。

常见错误现象：ArrayDeque 突然报 NullPointerException 或行为反直觉，往往是因为手动修改了 head/tail 字段（它们是包私有字段，不可直接访问），或误以为 tail - head 就是 size——实际得用 (tail - head) & (elements.length - 1)（因为 length 是 2 的幂）。

• 插入操作（addLast / push）只动 tail，但会先检查是否扩容：若 tail == head 且数组已满，则触发扩容
• 删除操作（removeFirst / pop）只动 head，删完不置 null（靠 GC 引用判断）
• 扩容不是翻倍，而是按需扩到能容纳当前 size + 1 的最小 2 的幂（例如 size=15 → 扩到 32）

为什么 ArrayDeque 的数组长度必须是 2 的幂？

为了用位运算替代取模，加速索引计算。所有下标访问（比如 elements[(head + i) & (elements.length - 1)]）都依赖 length - 1 是全 1 的二进制数（如 15 → 0b1111），这样 & 就等价于 % length，但快一个数量级。

使用场景：高频增删、对延迟敏感（如事件循环、解析器 token 缓冲区）。如果你硬塞进去非 2 的幂长度的数组（通过反射），ArrayDeque 会直接崩——它的构造函数内部强制重置为 2 的幂。

• 创建时传入初始容量 10，实际分配长度是 16
• 扩容后新数组仍是 2 的幂，旧元素通过 & 运算重新散列到新位置
• 别试图复用 ArrayDeque 数组做其他用途，它的 layout 是严格按循环队列设计的

peekFirst/peekLast 返回 null 说明什么？

说明队列为空，不是 bug，是约定行为。但要注意：如果队列里存的是 null 元素（虽然 ArrayDeque 不允许 add null），那 peek 返回 null 就无法区分“空队列”和“队首是 null”。所以它干脆禁止 null，避免歧义。

常见错误现象：代码里写了 if (deque.peekFirst() != null) 就认为有元素，结果逻辑跳过——其实只要队列非空，peekFirst 就一定返回非 null 值；反之，返回 null 就代表 isEmpty() 为 true。

• pollFirst() 和 pollLast() 也返回 null 表示空，不是异常
• 想抛异常用 removeFirst()，它在空时抛 NoSuchElementException
• 别用 == null 判断是否为空，用 isEmpty() 更准确、语义清晰

ArrayDeque 和 LinkedList 在栈场景下谁更快？

ArrayDeque 几乎总是更快。它没有节点对象开销、缓存局部性好、指令少。JDK 文档明确建议：当作栈用时，优先选 ArrayDeque 而不是 LinkedList。

性能影响：压栈 100 万次，ArrayDeque 通常比 LinkedList 快 2–5 倍；内存占用低 30%+（无 Node 对象的 24 字节头+引用冗余）。

• push() 对应 addFirst()，pop() 对应 removeFirst()
• LinkedList 的每个操作都要 new Node，GC 压力大；ArrayDeque 只在扩容时 new 数组
• 如果栈深度波动极大（比如从 10 到 100 万），ArrayDeque 扩容成本可接受，而 LinkedList 的随机访问慢（get(i) 是 O(n)）

ArrayDeque 的循环本质不在数组“物理循环”，而在指针计算方式；真正容易被忽略的是：它的所有边界判断都基于位运算，一旦破坏 length 是 2 的幂这个前提，整个逻辑就失效——这不是实现细节，是设计契约。

好了，本文到此结束，带大家了解了《ArrayDeque循环数组原理深度解析》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！