Java集合-ArrayDeque

前言

ArrayDeque 是 Java 集合框架中的一个双端队列（Double-Ended Queue），它实现了 Deque 接口，支持从队列的两端高效地添加和移除元素。它的底层实现基于动态数组，具有较高的性能，适用于需要频繁操作队列头尾的场景。以下从源码逐步解析其实现原理。

源码分析

数据结构

ArrayDeque 是一个基于循环数组（circular array）实现的双端队列。与普通的数组不同，它的头指针（head）和尾指针（tail）可以在数组中循环移动，从而避免了频繁的数组拷贝操作。源码中核心字段如下：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable {
    // 底层存储元素的数组
    transient Object[] elements;
    // 头指针，指向队列的第一个元素
    transient int head;
    // 尾指针，指向队列最后一个元素的下一个位置
    transient int tail;
    // 最小初始容量
    private static final int MIN_INITIAL_CAPACITY = 8;
}

elements：存储元素的数组，默认初始容量为 16（稍后会分析）。
head：指向队列头部的位置。
tail：指向队列尾部下一个可插入的位置。
transient：表示这些字段不会被序列化，因为 ArrayDeque 自定义了序列化逻辑。

构造方法

ArrayDeque 提供了三种构造方法：

// 无参构造，默认容量为 16
public ArrayDeque() {
    elements = new Object[16];
}

// 指定初始容量的构造
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

// 从另一个集合构造
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

`allocateElements` 方法

这个方法用于初始化数组容量，值得注意的是，容量必须是 2 的幂次方：

private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY; // 8
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>> 1);
        initialCapacity |= (initialCapacity >>> 2);
        initialCapacity |= (initialCapacity >>> 4);
        initialCapacity |= (initialCapacity >>> 8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        if (initialCapacity < 0)   // 处理溢出
            initialCapacity >>>= 1;
    }
    elements = new Object[initialCapacity];
}

如果指定的 numElements 小于 8，则使用默认最小容量 8。
如果大于等于 8，则通过位运算计算出大于等于 numElements 的最小 2 的幂次方。
为什么要用 2 的幂次方？因为循环数组的索引计算依赖模运算，而 2 的幂次方可以用位与（&）操作高效实现，避免除法运算。

核心方法

添加元素

ArrayDeque 支持从头部或尾部添加元素，主要方法包括 addFirst 和 addLast。

addLast 方法（尾部添加）

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ((tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity(); // 容量不足时扩容
}

将元素放入 tail 位置。
更新 tail：(tail + 1) & (elements.length - 1) 是循环数组的关键，通过位与操作实现模运算。
如果 tail 追上 head，说明数组已满，调用 doubleCapacity 扩容。

addFirst 方法（头部添加）

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

head 前移一位：(head - 1) & (elements.length - 1)，同样利用位运算实现循环。
如果 head 和 tail 重合，触发扩容。

扩容机制

当数组满时，调用 doubleCapacity 方法将容量翻倍：

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head 到数组末尾的元素数
    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); // 拷贝 head 到末尾的部分
    System.arraycopy(elements, 0, a, r, p); // 拷贝开头到 head 的部分
    elements = a;
    head = 0;
    tail = n;
}

新容量是旧容量的两倍（n << 1）。
将原数组的元素按顺序拷贝到新数组，调整后 head 指向 0，tail 指向新插入位置。
扩容后，队列从数组开头连续排列，便于后续操作。

移除元素

ArrayDeque 支持从头部或尾部移除元素，例如 pollFirst 和 pollLast。

pollFirst 方法（移除头部）

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    if (result == null)
        return null;
    elements[h] = null; // 帮助 GC
    head = (h + 1) & (elements.length - 1);
    return result;
}

返回 head 位置的元素，并将其置为 null。
head 前进一位，依然通过位运算实现循环。

pollLast 方法（移除尾部）

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

tail 后退一位，移除最后一个元素。

后记

时间复杂度：
- 添加（addFirst、addLast）：$O(1)$（均摊）
- 删除（pollFirst、pollLast）：$O(1)$
- 扩容：$O(n)$，但均摊后为 $O(1)$。
- 空间复杂度：$O(n)$，$n$ 为元素个数。

优势：相比 LinkedList，ArrayDeque 使用连续内存，缓存友好，性能更高。
限制：不支持随机访问，不适合需要索引操作的场景。

ArrayDeque 不允许插入 null，否则抛出 NullPointerException。
ArrayDeque 线程不安全，需要外部同步机制（如 Collections.synchronizedDeque）。