浅谈 ArrayDeque

1.数据结构

ArrayDeque 的底层是一个数组，其结构相当于环形数组。

2.初始化

2.1 无参初始化

transient Object[] elements;

// 无参构造函数
public ArrayDeque() {
    elements = new Object[16];
}

2.2 指定容量初始化

核心是 calculateSize() 方法，它需要找到比指定容量大的最小 2 倍数。

• 首先比较指定容量是否大于 MIN_INITIAL_CAPACITY(8)；不是，则直接返回
• 当指定容量大于 8 时，寻找比指定容量大的最小 2 倍数，计算过程同 HashMap 类似
• 如果计算后所得的容量小于 0，则说明溢出了，应当缩小一倍

例子：

// 指定容量有参构造函数
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}

private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}

private static final int MIN_INITIAL_CAPACITY = 8;

// 在初始化的过程中，它需要找到比当前传输值大的最小的 2 的倍数的一个容量
private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

2.3 初始化时添加数组

// 携带数据的有参构造函数
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

// AbstractCollection $ addAll
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

3.添加数据

3.1 头插

• 首先判断要插入的元素是否为空；为空则抛出空指针异常
• 通过 (head - 1) & (elements.length - 1) 计算首部索引位置
• 当 head 头指针和 tail 尾指针指向相同位置时，进行扩容

计算索引例子：

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

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public void push(E e) {
    addFirst(e);
}

3.2 尾插

• 首先判断要插入的元素是否为空；为空则抛出空指针异常
• 将元素插入 tail 尾指针所指位置
• 通过 (tail = (tail + 1) & (elements.length - 1) 计算尾指针的位置
• 如果新的 tail 尾指针等于 head 头指针，则进行扩容

计算尾指针例子：

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

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

public boolean add(E e) {
    addLast(e);
    return true;
}

public boolean offer(E e) {
    return offerLast(e);
}

4.扩容

扩容例子：

// 两倍扩容，数据迁移
private void doubleCapacity() {
    // 只有 head=tail 时，即数组空间被填满，才需要扩容 
    assert head == tail;
    int p = head;
    int n = elements.length;
    // 计算 [head..n-1] 的个数
    int r = n - p; // number of elements to the right of p
    // 扩容 2 倍
    int newCapacity = n << 1;
    // 判断是否长度溢出
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    // 创建新数组
    Object[] a = new Object[newCapacity];
    // 将 elements[head..n-1] 复制到 a[0,r]
    System.arraycopy(elements, p, a, 0, r);
    // 将 elements[0,head-1] 复制到 a[r+1,r+p]
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

5.删除

5.1 删除头部

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    // 获取 head 指针指向的元素
    E result = (E) elements[h];
    // head 指针指向的元素为空，返回 null
    if (result == null)
        return null;
    // head 指针所指位置置空    
    elements[h] = null;     // Must null out slot
    // 更新 head 指针
    head = (h + 1) & (elements.length - 1);
    return result;
}

public E poll() {
    return pollFirst();
}

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

public E remove() {
    return removeFirst();
}

public E pop() {
    return removeFirst();
}

5.2 删除尾部

public E pollLast() {
    // 获取尾部元素索引 
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    // 获取尾部元素
    E result = (E) elements[t];
    // 尾部元素为空，返回 null
    if (result == null)
        return null;
    // 尾部元素位置置空
    elements[t] = null;
    // 更新尾指针
    tail = t;
    return result;
}

public E removeLast() {
    E x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

5.3 删除指定元素

5.3.1 从头开始删除

从 head 头指针开始遍历，当遇到第一个与 o 相等的元素时，调用 delete() 方法删除该元素；如果容器中不存在该元素，则没有变化。

public boolean removeFirstOccurrence(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x)) {
            // 删除指定位置的元素
            delete(i);
            return true;
        }
        // 指针往后移动一步
        i = (i + 1) & mask;
    }
    return false;
}

5.3.2 从尾开始删除

从 tail 尾指针往前开始遍历，当遇到第一个与 o 相等的元素时，调用 delete() 方法删除该元素；如果容器中不存在该元素，则没有变化。

public boolean removeLastOccurrence(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    // tail 指针总是指向最后一个元素的后边一个位置；所以要 tail-1 找到最后一个元素
    int i = (tail - 1) & mask;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x)) {
            // 删除指定位置的元素
            delete(i);
            return true;
        }
        // 指针向前移动一步
        i = (i - 1) & mask;
    }
    return false;
}

5.3.3 删除指定索引位置的元素

front： 指从 $[head,i)$ 之间有多少个元素

back: 指从 $[i,tail)$ 之间有多少个元素

front >= ((t - h) & mask)： 满足此种情况需要抛异常，因为 $i$ 不合法；推理过程如下。

$\because 数组非环形时，索引 i 有效的条件是\ head \le i \lt tail$

$\therefore i-head \lt tail-head$

$\because 容器中数组为环形$

$\therefore (i-head)\ \&\ mask \lt (tail-head)\ \&\ mask$

$\because front=(i-head)\&mask$

$\therefore 索引 i 有效情况的条件是：front \lt (tail-head)\ \&\ mask$

$\therefore 索引 i 无效情况的条件是：front \ge (tail-head)\ \&\ mask$

元素删除： 主要分为以下四种情况

private boolean delete(int i) {
    // 判断此时容器内元素的分布情况是否合法
    checkInvariants();
    final Object[] elements = this.elements;
    final int mask = elements.length - 1;
    final int h = head;
    final int t = tail;
    // 计算 [head,i) 有多少个元素
    final int front = (i - h) & mask;
    // 计算 [i,tail) 有多少个元素
    final int back  = (t - i) & mask;
    
    if (front >= ((t - h) & mask))
        throw new ConcurrentModificationException();

    // Optimize for least element motion
    if (front < back) {
        if (h <= i) {
            // 情况一
            // 将 elements[h,i-1] 复制到 elements[h+1,i]
            System.arraycopy(elements, h, elements, h + 1, front);
        } else { // Wrap around
            // 情况二
            // 将 elements[0,i-1] 复制到 elements[1,i]
            System.arraycopy(elements, 0, elements, 1, i);
            // elmesnts[mask] 移动到 0 位置
            elements[0] = elements[mask];
            // elements[h,mask] 复制到 elements[h+1,mask]
            System.arraycopy(elements, h, elements, h + 1, mask - h);
        }
        elements[h] = null;
        head = (h + 1) & mask;
        return false;
    } else {
        if (i < t) { // Copy the null tail as well
            // 情况三
            // 将 elements[i+1..tail] 复制到 elements[i..tail-1]
            System.arraycopy(elements, i + 1, elements, i, back);
            tail = t - 1;
        } else { // Wrap around
            // 情况四
            // 将 elements[i+1,mask] 复制到 elements[i,mask-1]
            System.arraycopy(elements, i + 1, elements, i, mask - i);
            // 将 elements[0] 移动到 mask 位置
            elements[mask] = elements[0];
            // 将 elements[1..tail] 复制到 elements[0..tail-1]
            System.arraycopy(elements, 1, elements, 0, t);
            tail = (t - 1) & mask;
        }
        return true;
    }
}

private void checkInvariants() {
    // 判断 tail 尾指针所指位置是否为 null，即判断容器是否已满；容器满了，则说明添加时未扩容，存在问题
    assert elements[tail] == null;
    // 当 head = tail 时，elements 应为空；
    // 当 head != tail 时，head 和 tail-1 所指位置都非空
    assert head == tail ? elements[head] == null :
        (elements[head] != null &&
         elements[(tail - 1) & (elements.length - 1)] != null);
    // 经过以上判断说明容器非空且未满，则 head 头指针的前一个元素应当为 null
    assert elements[(head - 1) & (elements.length - 1)] == null;
}