ArrayDeque源码解读

出来看星星吗？不看星星出来也行。 / 2024-08-23 / 原文

ArrayDeque

ArrayDeque和LinkedList是Deque的两个通用实现，在使用Queue时，由于Queue只是一个接口，因此创建Queue时也会使用ArrayDeque

为了实现在数组两端进行操作元素的需求，因此ArrayDeque使用循环数组作为底层数据结构，同时，ArrayDeque中定义了head和tail两个指针指向头和尾

因为是循环数组，所以head可能比tail大，head指向第一个有效元素，tail指向尾部第一个可以插入元素的空位。

插入元素

因为是循环数组，扩容比较棘手，因此扩容操作是在插入操作完成之后进行的。

tail永远执行一个空位置，所以插入操作永远是有空余位置的。

下标越界直接取余就行。

public void addFirst(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
    if (head == tail)//1.空间是否够用
        doubleCapacity();//扩容
}

扩容操作

扩容操作的逻辑是申请一个更大的数组（两倍），然后使用System.arraycopy进行数据拷贝，拷贝的时候拷贝到新数组的头部。

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边元素的个数
    int newCapacity = n << 1;//原空间的2倍
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    //第一次复制head右边的元素
    System.arraycopy(elements, p, a, 0, r);
    //第二次复制head左边的元素
    System.arraycopy(elements, 0, a, r, p);
    elements = (E[])a;
    head = 0;
    tail = n;
}

删除操作

删除只需要挪动下标，然后原来位置置null（方便GC回收）

public E pollFirst() {
    int h = head;
    E result = elements[head];
    if (result == null)
        return null;
    elements[h] = null;//方便GC回收
    head = (head + 1) & (elements.length - 1);//下标越界处理
    return result;
}