#ArrayDeque 与 LinkedList 对比
面试官问："ArrayDeque 和 LinkedList 都能做双端队列，有什么区别？"
候选人小秦答不上来。
【面试官心理】 ArrayDeque 和 LinkedList 都能实现双端队列，但底层实现和性能特点完全不同。能说出环形数组实现和性能差异的候选人，说明对数据结构有研究。
#一、底层实现对比 🔴
// ArrayDeque：环形数组
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E> {
transient Object[] elements; // 存储元素的数组
transient int head; // 头部索引
transient int tail; // 尾部索引
// 容量始终是 2 的幂次
// head == tail 表示空
// (tail + 1) % length == head 表示满
}
// LinkedList：双向链表
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E> {
transient Node<E> first;
transient Node<E> last;
int size;
private static class Node<E> {
E item;
Node<E> prev;
Node<E> next;
}
}#二、性能对比 🟡
| 维度 | ArrayDeque | LinkedList |
|---|---|---|
| 头部插入 | O(1) | O(1) |
| 尾部插入 | O(1) 均摊 | O(1) |
| 随机访问 | O(1) | O(n) |
| 内存占用 | 连续内存，少量开销 | 每个节点 2 个引用 |
| 插入效率 | 高（无对象创建） | 中（每次创建节点） |
| CPU 缓存 | 友好 | 不友好 |
#三、ArrayDeque 的环形数组 🟡
// 环形数组操作
public void addFirst(E e) {
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail) // 扩容
doubleCapacity();
}
public void addLast(E e) {
elements[tail] = e;
if ((tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
public E pollFirst() {
int h = head;
E result = (E) elements[h];
if (result == null) return null;
elements[h] = null;
head = (h + 1) & (elements.length - 1);
return result;
}
// & (length - 1) 等价于取模
// 例如：length = 8 (0b1000), h = 7
// (7 - 1) & (8 - 1) = 6 & 7 = 6 ✓
// h = 0
// (0 - 1) & 7 = -1 & 7 = 7 ✓ （环绕到末尾）#四、选型建议 🟡
// 需要队列或栈，且不需要随机访问：ArrayDeque（性能更好）
Deque<Integer> stack = new ArrayDeque<>(); // 栈
Deque<Integer> queue = new ArrayDeque<>(); // 队列
// 需要 List API（随机访问）：LinkedList
List<Integer> list = new LinkedList<>();
// 需要双端队列，且不需要 List API：ArrayDeque（推荐）
Deque<Integer> deque = new ArrayDeque<>();
// Java 建议：ArrayDeque 比 LinkedList 作为栈/队列性能更好
// 《Effective Java》 Item 69：优先使用 ArrayDeque 而不是 LinkedList#五、追问升级
面试官："ArrayDeque 什么时候扩容？"
// 扩容时机：head == tail（队列满）
// 扩容策略：容量翻倍
// 最小容量：16
private void doubleCapacity() {
int p = head;
int n = elements.length;
int r = n - p; // head 到末尾的元素数
int newCapacity = n << 1; // 翻倍
Object[] a = new Object[newCapacity];
// 复制 head 到末尾的元素
System.arraycopy(elements, p, a, 0, r);
// 复制 0 到 head 的元素
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}