Java ArrayDeque源码解读

ArrayDeque 是 Java 中一个高效、动态的双端队列（deque）实现，它继承了 AbstractCollection 类并实现了 Deque 接口。ArrayDeque 底层基于循环数组实现，允许从两端快速添加和删除元素，是一种常用的无锁非阻塞队列。接下来，我们分几个关键部分来解读它的源码：

1. 基本属性

在 ArrayDeque 的源码中，我们可以看到一些关键的属性：

transient Object[] elements; // 存储元素的数组

transient int head; // 指向队首的指针

transient int tail; // 指向队尾的指针

elements 数组：用来存储双端队列中的元素。

head 和 tail：分别指向队首和队尾的位置，通过这两个指针来实现从两端添加和删除的操作。

默认情况下，ArrayDeque 的初始容量是 16，并且容量总是 2 的幂，这有助于在实现上利用位运算来提升效率。

2. 核心方法解析

添加元素

addFirst(E e) 和 addLast(E e)：用于在队列的头部和尾部添加元素。

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)：这里用到了位运算 (elements.length - 1) 来做循环，这样可以在数组满了之后从数组的末尾重新回到开头。

当 head 和 tail 重合时，说明数组已满，需要扩容，调用 doubleCapacity() 方法。

doubleCapacity()：负责扩容数组，将容量加倍。

private void doubleCapacity() {

int p = head;

int n = elements.length;

int r = n - p; // 队尾到数组末尾的元素数量

Object[] a = new Object[n << 1];

System.arraycopy(elements, p, a, 0, r);

System.arraycopy(elements, 0, a, r, p);

elements = a;

head = 0;

tail = n;

}

在 doubleCapacity() 方法中，通过 System.arraycopy 方法将旧数组中的元素复制到新数组中。通过 n << 1 扩容至原来的两倍。扩容完成后，重置 head 和 tail 的位置。

删除元素

removeFirst() 和 removeLast()：用于从队列的头部和尾部删除元素。

public E removeFirst() {

E x = (E) elements[head];

if (x == null)

throw new NoSuchElementException();

elements[head] = null; // 避免内存泄漏

head = (head + 1) & (elements.length - 1);

return x;

}

删除队首元素后，将 head 向后移动，并使用位运算保证循环。

为了避免内存泄漏，将 elements[head] 置为 null。

3. 容量控制

ArrayDeque 在添加和删除元素时，均会进行容量检查和扩容控制，确保不发生溢出和资源浪费。

检查数组是否满

if (head == tail)

doubleCapacity();

在每次添加元素时，都会检查 head 是否和 tail 重合，如果重合则意味着数组已满，需要调用 doubleCapacity() 扩容。

检查数组是否为空

if (x == null)

throw new NoSuchElementException();

在删除元素时，会检查头或尾位置的元素是否为 null，若为 null 则表示队列为空，抛出 NoSuchElementException。

4. 总结

ArrayDeque 是一个基于循环数组的双端队列，支持在队首和队尾的快速增删操作，且不会像 LinkedList 一样产生额外的节点开销。其扩容机制也比较高效，通过位运算实现循环和扩容，可以达到 O(1) 的时间复杂度，非常适合对性能有较高要求的场景。