从源码看本质：手把手带你图解ArrayDeque的循环数组和LinkedList的双向链表

深度解析ArrayDeque与LinkedList：从数据结构到实战选择

在Java集合框架中，ArrayDeque和LinkedList作为两种经典的双端队列实现，常常让开发者陷入选择困境。本文将通过可视化数据结构演变和关键方法执行路径追踪，带您彻底理解两者的底层机制与性能特性差异。

1. ArrayDeque的循环数组奥秘

ArrayDeque之所以能在O(1)时间复杂度下完成首尾操作，核心在于其精心设计的循环数组结构。想象一个环形跑道，跑者（元素）可以从任意位置加入或离开，而不会造成位置浪费。

1.1 循环数组的物理实现

实际存储仍然使用普通数组，但通过两个关键指针实现"循环"效果：

• head：指向队列头部元素
• tail：指向下一个插入位置

当指针到达数组末尾时，通过简单的模运算回到起点：

// 添加元素时的指针移动 tail = (tail + 1) & (elements.length - 1) // 移除元素时的指针移动 head = (head + 1) & (elements.length - 1)

注意：&运算替代模运算的前提是数组长度为2的幂次方，这也是ArrayDeque强制扩容为2^n的原因

1.2 扩容机制详解

当数组填满时，ArrayDeque会执行扩容操作，这个过程分为三步：

1. 创建新数组（通常为原数组2倍）
2. 将原数组元素复制到新数组
3. 调整head和tail指针位置

扩容前后的指针变化对比：

1.3 位运算优化技巧

ArrayDeque中大量使用位运算提升性能：

• 计算元素数量：(tail - head) & (elements.length - 1)
• 检查是否为空：head == tail
• 计算插入位置：(head - 1) & (elements.length - 1)

这些技巧使得ArrayDeque在大多数硬件架构上都能获得接近原生数组的访问速度。

2. LinkedList的双向链表实现

LinkedList采用经典的双向链表结构，每个节点都像列车车厢一样相互连接：

class Node<E> { E item; Node<E> prev; Node<E> next; }

2.1 节点操作可视化

头部插入新节点的过程：

1. 创建新节点，next指向当前头节点
2. 如果链表非空，原头节点的prev指向新节点
3. 更新头节点引用

[新节点] -> [原头节点] -> [节点2] -> ... ↑____________|

中间删除节点的指针变化：

[前驱节点] [待删除节点] [后继节点] next ---------> next prev <--------- prev 变为： [前驱节点] -> [后继节点] prev <-/

2.2 索引访问的代价

虽然LinkedList在任意位置插入删除都是O(1)，但随机访问需要遍历：

Node<E> node(int index) { if (index < (size >> 1)) { // 前半部分从头遍历 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 后半部分从尾遍历 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

这种二分遍历优化虽然减少了平均比较次数，但时间复杂度仍然是O(n)。

3. 关键操作性能对比

通过实际测试数据对比两种结构在不同操作下的表现（单位：纳秒/op）：

测试环境：JDK17，队列初始大小16，测试数据为100万次操作平均值

4. 实战选型指南

4.1 优先选择ArrayDeque的场景

• 高频首尾操作：如实现滑动窗口算法
• 栈结构需求：比Stack类性能更好
• 内存敏感场景：连续内存占用更少
• 批量遍历操作：缓存局部性更好

// 典型栈用法示例 ArrayDeque<String> stack = new ArrayDeque<>(); stack.push("A"); stack.push("B"); String top = stack.pop(); // "B"

4.2 适合LinkedList的用例

• 频繁中间插入删除：如文本编辑器中的行缓冲区
• 不确定容量场景：避免频繁扩容
• 需要null元素：ArrayDeque不支持null
• 实现特殊数据结构：如跳表的基础结构

// 中间插入示例 LinkedList<String> editorBuffer = new LinkedList<>(); editorBuffer.add("Line1"); editorBuffer.add("Line3"); editorBuffer.add(1, "Line2"); // 在中间插入

4.3 并发场景下的替代方案

虽然两者都不是线程安全的，但有不同的并发替代方案：

在实际项目中，我多次遇到因为错误选择集合类型导致的性能问题。有一次在开发高频交易系统时，使用LinkedList作为订单队列导致GC压力剧增，切换到ArrayDeque后性能提升了40%。关键是要理解数据结构的底层实现，才能做出合理选择。