ArrayDeque 和 LinkedList 都能做队列，为什么工程上更常推荐 ArrayDeque？
简化版
ArrayDeque 底层是可扩容循环数组，入队出队通常是摊还 O(1)，缓存局部性好、节点开销小；LinkedList 是链表结构，每个元素有额外节点和指针，遍历与分配成本更高。所以不需要在中间插删时，工程上常优先用 ArrayDeque 做栈或队列。
详细版
两者都能实现队列接口，但底层结构差别很大。
ArrayDeque：用数组加头尾下标维护双端队列，空间连续，扩容时整体搬迁。LinkedList：用双向链表维护元素，每个元素一个节点，节点里有prev、next。- 队列常见操作是头部出队、尾部入队，不需要中间插删。
- 在这种访问模式下，数组环形缓冲更贴近 CPU 缓存，少对象分配，通常更快。
所以面试回答不要只说“它们复杂度都是 O(1)”。大 O 一样，不代表工程性能一样；节点开销、缓存局部性和 GC 压力也很重要。
完整版教学
一、队列接口相同不代表底层代价相同
队列只要求先进先出：尾部加入，头部取出。ArrayDeque 和 LinkedList 都能暴露类似的 offer、poll、peek 操作，但它们为这些操作付出的底层成本不一样。
ArrayDeque 可以理解成一段循环数组：
数组槽位：[_, A, B, C, _, _]
head 指向 A，tail 指向 C 后面的空位LinkedList 则是一个个节点串起来：
head <-> A <-> B <-> C <-> tail接口让使用者看不到这些细节，但性能差异就藏在这些细节里。
二、ArrayDeque 为什么适合队列
队列的尾插和头删都发生在两端。循环数组只要维护两个下标，就能把数组尾部“绕回”数组头部继续使用。
例如容量为 5，做 3 次入队、2 次出队、再 2 次入队：
初始：[_,_,_,_,_]
入队 A B C：[A,B,C,_,_]
出队 A B：[_,_,C,_,_]
入队 D E：[_,_,C,D,E]如果继续入队，tail 可以回到前面的空位。这样就避免了普通数组头删时整体搬移元素的问题。只有容量不够时才扩容，扩容成本摊还到多次操作后仍是摊还 O(1)。
三、LinkedList 的额外节点成本是什么
链表每个元素不只是值本身，还要有节点对象和指针字段。双向链表通常至少有 prev、next 两个引用。
如果存 100000 个元素，LinkedList 可能对应 100000 个节点对象。每个节点分散在堆上，访问下一个元素要跟随指针跳转。
| 维度 | ArrayDeque | LinkedList |
|---|---|---|
| 元素存储 | 数组槽位 | 独立节点 |
| 额外指针 | 头尾下标 | 每节点 prev/next |
| 缓存局部性 | 通常较好 | 通常较差 |
| 中间插删 | 不擅长 | 已知节点时较擅长 |
队列操作不需要中间插删，因此 LinkedList 的优势很难发挥，反而承担了节点开销。
四、缓存局部性为什么会影响真实性能
数组元素连续，CPU 读取一个缓存行时，可能顺便把相邻多个槽位带进缓存。顺序访问或两端附近访问都比较友好。
链表节点分散，当前节点的 next 指向哪里，要读到当前节点后才知道。这个过程叫指针追逐，硬件预取不容易提前判断下一步地址。
数组：base + index * size，可预测
链表：node.next，读完当前节点才知道所以即使理论复杂度都写 O(1)，真实运行时 ArrayDeque 经常更省时、更省内存，也更少给 GC 制造压力。
五、ArrayDeque 有没有缺点
有。它是数组结构，扩容时要分配新数组并搬移元素。虽然摊还复杂度仍然好，但某一次操作可能出现短暂尖峰。
另外，很多语言的 ArrayDeque 不允许存 null，因为 null 可能被用来表示空槽或空返回值。不同语言实现细节不同，面试时可以说“要看具体库的约束”。
六、什么时候 LinkedList 仍有意义
如果你已经拿到了某个中间节点，并且需要频繁在它附近插入或删除，链表有价值。或者你需要稳定节点引用，外部结构保存节点对象，那么链表也可能合适。
记忆钩子：做普通队列时，ArrayDeque 赢在“连续数组 + 少分配”；LinkedList 的中间插删优势，在普通 FIFO 队列里用不上。
七、常见误区与追问
- 误区：两者队列操作都是 O(1)，所以性能一样。 大 O 不包含缓存局部性、对象分配、指针跳转和 GC 成本。
- 误区：链表插删快，所以做队列一定更好。 普通队列只在两端操作，循环数组也能高效完成。
- 误区：ArrayDeque 永远没有开销。 扩容时仍会搬迁元素，只是摊还后很划算。
- 追问：为什么不建议用 Stack 类做栈？ 很多语言里的旧 Stack 类有历史同步开销或设计包袱，Deque 通常更推荐。
- 追问：LinkedList 什么时候更适合？ 已知中间节点后频繁插删，或需要节点稳定引用时更有意义。
八、加强记忆
这题的关键不是背 Java 容器名，而是看操作模式和底层结构。FIFO 队列主要在两端操作，循环数组正好能用 head/tail 做到摊还 O(1)，还享受连续内存；链表虽然也能 O(1) 两端操作，但节点分散、指针多、分配多，所以普通工程队列常优先 ArrayDeque。