Java 数据结构：说一下 ArrayDeque 和 LinkedList 的区别?

本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 发问。

前言

大家好，我是小彭。

在上一篇文章里，咱们聊到了根据链表的 Queue 和 Stack 完成 —— LinkedList。那么 Java 中有没有根据数组的 Queue 和 Stack 完成呢？今日咱们就来聊聊这个话题。

---

思想导图：

---

1. 回忆 LinkedList

在数据结构上，LinkedList 不只完成了与 ArrayList 相同的 List 接口，还完成了 Deque 接口，而咱们今日要讲的 ArrayDeque 便是完成于 Deque 接口的动态数组。

Deque 接口表明一个双端行列（Double Ended Queue），允许在行列的首尾两头操作，所以既能完成行列行为，也能完成栈行为。

1.1 Queue 接口

Queue 的 API 能够分为 2 类，区别在于办法的回绝战略上：

• 抛反常：
  • 向空行列取数据，会抛出 NoSuchElementException 反常；
  • 向容量满的行列加数据，会抛出 IllegalStateException 反常。
• 回来特别值：
  • 向空行列取数据，会回来 null；
  • 向容量满的行列加数据，会回来 false。

回绝战略	抛反常	回来特别值
入队（队尾）	add(e)	offer(e)
出队（队头）	remove()	poll()
调查（队头）	element()	peek()

1.2 Deque 接口（承继于 Queue 接口）

Java 没有供给规范的栈接口（很好奇为什么不供给），而是放在 Deque 接口中：

回绝战略	抛反常	等价于
入栈	push(e)	addFirst(e)
出栈	pop()	removeFirst()
调查（栈顶）	peek()	peekFirst()

除了规范的行列和栈行为，Deque 接口还供给了 12 个在两头操作的办法：

回绝战略	抛反常	回来值
增加	addFirst(e)/ addLast(e)	offerFirst(e)/ offerLast(e)
删除	removeFirst()/ removeLast()	pollFirst()/ pollLast()
调查	getFirst()/ getLast()	peekFirst()/ peekLast()

---

2. ArrayDeque 的特色

2.1 说一下 ArrayDeque 的特色

• 1、ArrayDeque 是根据动态数组完成的 Deque 双端行列，内部封装了扩容和数据转移的逻辑；

• 2、ArrayDeque 的数组容量确保是 2 的整数幂；

• 3、ArrayDeque 不是线程安全的；

• 4、ArrayDeque 不支撑 null 元素；

• 5、ArrayDeque 虽然入栈和入队有或许会触发扩容，但从均摊分析上看仍然是 O(1) 时刻杂乱度；

2.2 说一下 ArrayDeque 和 LinkedList 的区别?

• 1、数据结构： 在数据结构上，ArrayDeque 和 LinkedList 都完成了 Java Deque 双端行列接口。但 ArrayDeque 没有完成了 Java List 列表接口，所以不具有根据索引方位操作的行为；

• 2、线程安全： ArrayDeque 和 LinkedList 都不考虑线程同步，不确保线程安全；

• 3、底层完成： 在底层完成上，ArrayDeque 是根据动态数组的，而 LinkedList 是根据双向链表的。

  • 在遍历速度上： ArrayDeque 是一块连续内存空间，根据局部性原理能够更好地射中 CPU 缓存行，而 LinkedList 是离散的内存空间对缓存行不友好；

  • 在操作速度上： ArrayDeque 和 LinkedList 的栈和行列行为都是 O(1) 时刻杂乱度，ArrayDeque 的入栈和入队有或许会触发扩容，但从均摊分析上看仍然是 O(1) 时刻杂乱度；

  • 额外内存耗费上： ArrayDeque 在数组的头指针和尾指针外部有闲置空间，而 LinkedList 在节点上增加了前驱和后继指针。

---

3. 怎么运用数组完成栈和行列？

咱们知道栈和行列都是 “操作受限” 的线性表：栈是 LIFO，约束在表的一端入栈和出栈。而行列是 FIFO，约束在表的一端入队，在另一端出队。栈和行列既能够用数组完成，也能够用链表完成：

• 数组：用数组完成时叫作次序栈和次序行列；
• 链表：用链表完成时叫作链式栈和链式行列。

3.1 为什么 ArrayList 不适合完成行列？

在上一篇文章里，咱们提到了 LinkedList 的多面人生，它即作为 List 的链式表，又作为 Queue 的链式行列，又作为 “Stack” 的链式栈，功能很全面。相较之下，ArrayList 却只作为完成了 List 的次序表，为什么呢？

这是因为在数组上同时完成 List 和 Queue 时，无法平衡这两个行为的性能矛盾。具体来说：ArrayList 不允许底层数据有空泛，一切的有用数据都会 “紧缩” 究竟层数组的首部。所以，运用 ArrayList 开发栈的结构或许适宜，能够在数组的尾部操作数据。但运用 ArrayList 开发行列就不适宜，因为在数组的首部入队或出队需求转移数据。

3.2 运用数组完成栈结构

运用数组完成栈相对简略，因为栈结构的操作被约束在数组的一端，所以咱们能够挑选数组的尾部作为栈顶，并且运用一个 top 指针记录栈顶方位：

• 栈空： top == 0；
• 栈满： top == n；
• 入栈： 将数据增加到栈顶方位，均摊时刻杂乱度是 O(1)；
• 出栈： 将栈顶方位移除，时刻杂乱度是 O(1)；

关于出栈而言，时刻杂乱度总是 O(1)，可是关于入栈而言，却不必定。因为当数组的空间缺乏（top == n）时，就需求扩容和转移数据来容纳新的数据。此刻，时刻杂乱度就从 O(1) 退化到 O(n)。

关于这种大部分操作时刻杂乱度很低，只要个别状况下时刻杂乱度会退化，并且这些操作之间存在很激烈的次序联系的状况，就很适合用 “均摊时刻杂乱度分析” 了：

假设咱们的扩容战略是将数组扩大到旧数组的 2 倍，用均摊分析法：

• 1、关于一个巨细为 K 的空数组，在前 K – 1 次入栈操作中，时刻杂乱度都是 O(1)；
• 2、在第 K 次入栈中，因为数组容量缺乏，所以咱们将数组扩大为 2K，并且转移 K 个数据，时刻杂乱度退化为 O(K)；
• 3、关于一个巨细为 2K 的数组，在接下来的 K – 1 次入栈操作中，时刻杂乱度都是 O(1)；
• 4、在第 2K 次入栈中，因为数组容量缺乏，所以咱们将数组扩大为 4K，并且转移 2K 个数据，时刻杂乱度再次退化为 O(K)；
• 5、依此类推。

能够看到，在每次转移 K 个次数后，随后的 K – 1 次入栈操作就仅仅简略的 O(1) 操作，K 次入栈操作涉及到 K 个数据转移和 K 次赋值操作。那咱们从全体看，假如把杂乱度较高的 1 次入栈操作的耗时，均摊到其他杂乱度较低的操作上，就等于说 1 次入栈操作只需求转移 1 个数据和 1 次赋值操作，所以入栈的均摊时刻杂乱度便是 O(1)。

入栈的均摊时刻杂乱度分析

3.3 运用数组完成行列结构

运用数组完成行列相对杂乱，咱们需求一个队头指针和一个队尾指针：

• 队空： head == tail；
• 队满： tail == n（并不是真的满，仅仅无法填充新数据）；
• 入队： 将数据增加到队尾方位，均摊时刻杂乱度是 O(1)；
• 出队： 将队头方位移除，时刻杂乱度是 O(1)。

关于出队而言，时刻杂乱度总是 O(1)。关于入队而言，当 tail == n 时，就需求扩容和转移数据来容纳新的数据，咱们用均摊分析法得出均摊时刻杂乱度仍然是 O(1)，就不重复了。

可是咱们发现，栈的 top == n 表明栈空间缺乏，扩容没有问题，而行列的 tail == n 却不必定表明行列空间缺乏。因为入队和出队发生在不同方向，有或许出现 tail == n 但队头仍然有十分多剩余空间的状况。此刻，扩容显得没有必要。

扩容显得没有必要

那么，怎么防止没有必要的扩容和数据搬移呢？—— 循环数组。

咱们在逻辑上将数组的首尾相连，当 tail == n 时，假如数组头部还有空闲方位，咱们就把 tail 指针调整到数组头部，在数组头部增加数据。咱们下面要分析的 ArrayDeque 数据结构，便是选用了循环数组的完成。

运用循环数组后，行列空和行列满的判别条件会发生变化：

• 行列空： head == tail；
• 行列满： (tail + 1)%size == head，假如 size 是 2 的整数幂，还能够用位运算判别：(tail + 1) & (size – 1) == head。

理解了运用数组完成栈和行列的思路后，下面再来分析 ArrayDeque 的完成原理，就显得游刃有余了。

---

4. ArrayDeque 源码分析

这一节，咱们来分析 ArrayDeque 中主要流程的源码。

4.1 ArrayDeque 的特点

• ArrayDeque 底层是一个 Object 数组；
• ArrayDeque 用 head 和 tail 指针指向数组的 “队头方位” 和 “队尾方位”，需求注意 tail 队尾指针实际上是指向队尾最后一个有用元素的下一位。

ArrayDeque 的特点很好理解的，不出意外的话又有小朋友出来举手发问了：

• ‍♀️疑问 1： 为什么字段都不声明 private 关键字？（答复过多少次了，把手给我放下）
• ‍♀️疑问 2： 为什么字段都声明 transient 关键字？（答复过多少次了，把手给我放下）
• ‍♀️疑问 3： 为什么 elements 字段不声明为泛型类型 E？（答复过多少次了，把手给我放下）
• ‍♀️疑问 4：为什么没有看到 ArrayList 相似的 MAX_ARRAY_SIZE 最大容量约束？

这个问题咱们在分析源码的进程中答复。有了 ArrayList 的分析基础，问题少了很多，ArrayDeque 真香。

public class ArrayDeque<E> extends AbstractCollection<E>
		implements Deque<E>, Cloneable, Serializable
{
    // 疑问 1：为什么字段都声明 private 关键字？
    // 疑问 2：为什么字段都声明 transient 关键字？
    // 疑问 3：为什么 elements 字段不声明为泛型类型 E？
    // 疑问 4：为什么没有看到 ArrayList 相似的 MAX_ARRAY_SIZE 最大容量约束？
    // 底层数组
    transient Object[] elements; // non-private to simplify nested class access
    // 队头指针
    transient int head;
    // 队尾指针
    transient int tail;
    // new ArrayDeque(0) 最小初始容量
    private static final int MIN_INITIAL_CAPACITY = 8;
    // 尾指针 - 头指针
    public int size() {
        return (tail - head) & (elements.length - 1);
    }
}

4.2 ArrayDeque 的结构办法

ArrayDeque 有 3 个结构函数：

• 1、无参结构办法： 初始化容量为 16 的数组；
• 2、带初始容量的结构办法： 假如初始容量小于 8 (MIN_INITIAL_CAPACITY)，则初始化数组巨细为 8。假如初始容量大于 8，则核算 “最近的 2 的整数幂” 作为初始巨细。例如 numElements 为 8，则初始化容量为 16。numElements 为 19，则初始化容量为 32；
• 3、带调集的结构办法： 用相同的办法创建初始容量为 2 的整数幂的数组，并调用 addAll 逐一增加元素。

ArrayDeque.java

// 无参结构办法
public ArrayDeque() {
    elements = new Object[16];
}
// 带初始容量的结构办法
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
// 带调集的结构办法
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    // 疑问 5：为什么带调集的结构办法不运用 Arrays 东西全体仿制，而是逐一增加？
    addAll(c);
}
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
// 求离 numElements 最近的 2 的整数幂，即 nextPow2 问题
// 疑问 6：为什么 ArrayDeque 要求容量是 2 的整数幂？
// 疑问 7：calculateSize() 的函数体解释一下？
private static int calculateSize(int numElements) {
    // 假如 numElements 小于 8（MIN_INITIAL_CAPACITY），则回来 8
    int initialCapacity = MIN_INITIAL_CAPACITY;
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        // 五轮无符号右移和或运算后，变成最高有用位开端后边都是 1
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        // 加 1 进位，得到最近 2 的整数幂
        initialCapacity++;
        // 变成负数（高位是 1000，低位都是 0000）
        if (initialCapacity < 0)
            // 右移 1 位，取 2^30 为初始容量
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    return initialCapacity;
}

AbstractCollection.java

// 逐一增加元素
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

小朋友总有太多的问号，举手发问 ‍♀️：

• ‍♀️疑问 5：为什么带调集的结构办法不运用 Arrays 东西全体仿制，而是逐一增加？

因为 ArrayDeque 制止存储 null 元素，所以需求逐一判别元素是否为 null 值后才增加。

• ‍♀️疑问 6：为什么 ArrayDeque 要求数组容量是 2 的整数幂？

在循环数组中需求运用取余运算核算游标指针循环后的方位，例如 (tail + 1) % size，而假如数组的尺度 size 是 2 的整数幂，那么就能够将取余运算替换为位运算，例如 (tail + 1) & (size - 1) ，不论被除数是正负成果都是正数。 不只将取余运算替换为位运算，并且减少了一次取绝对值运算，提高了索引的核算功率。

size     = 0 0 0 1 0 0 0 0 0 0     // 2^n 的补码
size - 1 = 0 0 0 0 1 1 1 1 1 1     // 2^n - 1 的补码
-1       = 1 1 1 1 1 1 1 1 1 1     // -1 的补码
0        = 0 0 0 0 0 0 0 0 0 0     // 0 的补码
// 尾指针的循环：
1、假如 tail + 1 <= size - 1，则 (tail + 1) & (size - 1) 后坚持不变
2、假如 tail + 1 == size，则 size & (size - 1) 为 0
// 头指针的循环
1、假如 head - 1 >= 0，则（head - 1) & (size - 1) 后坚持不变
2、假如 head - 1 == -1，则 -1 & (size - 1) 后为 size - 1

• ‍♀️疑问 7：calculateSize() 的函数体解释一下？

calculateSize() 是求离 numElements 最近的 2 的整数幂，即 nextPow2 问题。

• 1、首先，假如 numElements 小于 8（MIN_INITIAL_CAPACITY），则直接回来 8；
• 2、否则履行 nextPow2 运算，经过五轮无符号右移和或运算，将 numElements 转换为从最高位开端后边都是 1 的数。再履行 +1 运算，就求出了最近的 2 的整数幂（最高有用位是 1，低位都是 0）；
• 3、当 numElements 在 2^30 到 2^ 31-1 之间（即最高位是 0100 的数），核算后得到的 nextPow2 便是负数（最高位是 1000，低位都是 0），此刻就需求右移一位，取 2^30 为初始容量。

n = 0 0 0 0 1 x x x x x     // n
n = 0 0 0 0 1 1 x x x x     // n |= n >>> 1;
n = 0 0 0 0 1 1 1 1 x x     // n |= n >>> 2;
n = 0 0 0 0 1 1 1 1 1 1     // n |= n >>> 4;
n = 0 0 0 0 1 1 1 1 1 1     // n |= n >>> 8;（这一步对 n 没有影响了）
n = 0 0 0 0 1 1 1 1 1 1     // n |= n >>> 16;（这一步对 n 没有影响了）
n = 0 0 0 1 0 0 0 0 0 0     // n ++（进位，得到最近 2 的整数幂）

4.3 ArrayDeque 的增加和扩容办法

ArrayDeque 能够在数组的两头增加元素，不支撑在数组的中心增加元素：

• 在队头增加： 在 head 指针的上一个方位赋值，假如数组越界则循环到数组尾部；
• 在队尾增加： 在 tail 指针的方位赋值，并将 tail 指针指向下一个方位，假如数组越界则循环到数组头部。

public void addLast(E e) {
    // 疑问：为什么 ArrayDeque 不支撑增加 null 元素
    if (e == null)
        throw new NullPointerException();
    // tail 指针自身便是指向下一个方位，所以直接填充
    elements[tail] = e;
    // 修正 tail 指针到下一个方位，并经过取余操作循环到数组头部
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}
public void addFirst(E e) {
    // 疑问 8：为什么 ArrayDeque 制止存储 null 元素？
    if (e == null)
        throw new NullPointerException();
    // 修正 head 指针到前一个方位，并经过取余操作循环到数组尾部
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

不出意外小朋友又要出来举手发问了‍♀️：

• ‍♀️疑问 8：为什么 ArrayDeque 制止存储 null 元素？

其实在 Deque 接口上并不严格制止存储 null 元素，可是会激烈建议 Deque 的完成不供给存储 null 值的才能。因为 null 通常会作为一个特别值来判别行列是否为空。

Deque javadoc

While Deque implementations are not strictly required to prohibit the insertion of null elements, they are strongly encouraged to do so. Users of any Deque implementations that do allow null elements are strongly encouraged not to take advantage of the ability to insert nulls. This is so because null is used as a special return value by various methods to indicated that the deque is empty.

public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    // 行列为空
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

在每次增加元素后，假如队头指针和队尾指针相遇，说明数组空间已满，此刻就需求扩容操作。ArrayDeque 会将新数组的容量扩大到旧数组的 2 倍 ，因为旧数组的容量也是 2 的整数幂，因而乘以 2 之后仍然是 2 的整数幂。

转移数据的进程便是把 head 头指针到数组结尾的元素拷贝到数组头部，而剩余的从数组头部到尾指针的元素则衔接到后边，使得一切元素规整地排列在数组的头部：

// 扩容操作
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    // 队头指针到数组结尾的元素个数
    int r = n - p;
    // 容量翻倍
    int newCapacity = n << 1;
    // 容量变成负数
    if (newCapacity < 0)
        // ArrayList 扩容整型溢出时会抛出 OutOfMemoryError
        // ArrayDeque 扩容整型溢出时会抛出 IllegalStateException
        // 看了一下，发现这两个容器出自不同作者，不能一致下吗哈哈
        throw new IllegalStateException("Sorry, deque too big");
    // 创建新数组
    Object[] a = new Object[newCapacity];
    // 将队头指针到数组结尾的元素拷贝到数组头部
    System.arraycopy(elements, p, a, 0, r);
    // 拷贝剩余的从数组头部到尾指针的元素
    System.arraycopy(elements, 0, a, r, p);
    // 指向新数组
    elements = a;
    // 重置头尾指针
    head = 0;
    tail = n;
}

扩容操作

• ‍♀️疑问 4：为什么没有看到 ArrayList 相似的 MAX_ARRAY_SIZE 最大容量约束？

现在咱们能够答复这个疑问了， 网上也有资料说 ArrayDeque 没有容量约束，最坑的是代码注释也这么说：“Array deques have no capacity restrictions”。 显然不是这么一回事。 榜首，数组的容量显现是被虚拟机固化的，不或许无限容量。第二，从 doubleCapacity() 函数能够看出， 最大容量值是 2^30（高位 0100，低位都是0）， 假如超越这个数，在 doubleCapacity() 扩容的时候就会抛出反常了。

4.4 ArrayDeque 的获取和移除办法

ArrayDeque 能够在数组的两头移除元素，不支撑在数组的中心移除元素：

• 在队头移除： 在 head 指针的方位获取，再将 head 指向上一个方位，假如数组越界则循环到数组尾部；
• 在队尾移除： 在 tail 指针的下一个方位获取，假如数组越界则循环到数组头部。

public E pollFirst() {
    // head 指针自身便是指向队头元素，所以直接获取
    int h = head;
    E result = (E) elements[h];
    if (result == null)
        return null;
    elements[h] = null;
    // 修正 head 指针
    head = (h + 1) & (elements.length - 1);
    return result;
}
public E pollLast() {
    // tail 指针自身是指向队尾元素的下一个方位，所以需求回来上一个方位
    int t = (tail - 1) & (elements.length - 1);
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

4.5 ArrayDeque 的迭代器

Java 的 foreach 是语法糖，本质上也是选用 iterator 的方法。ArrayDeque 供给了 2 个迭代器：

• iterator():DeqIterator()： 正向迭代器
• ListIterator DescendingIterator()： 反向迭代器

ArrayDeque 迭代器同样有 fail-fast 机制，不给过ArrayDeque 并没有运用相似 ArrayList 相似的 modCount 查看并发修正，而是经过头尾指针的方位和元素查看并发修正。这个办法不必定能确保检测到一切的并发修正状况，例如无法查看先移除了尾部元素，又立刻增加了一个尾部元素的状况。

private class DeqIterator implements Iterator<E> {
    private int cursor = head;
    private int fence = tail;
    private int lastRet = -1;
    public boolean hasNext() {
        return cursor != fence;
    }
    public E next() {
        if (cursor == fence) throw new NoSuchElementException();
        E result = (E) elements[cursor];
        // 无法检测到一切并发修正的状况
        if (tail != fence || result == null)
            throw new ConcurrentModificationException();
        lastRet = cursor;
        cursor = (cursor + 1) & (elements.length - 1);
        return result;
    }
    ...
}

4.6 ArrayDeque 的序列化进程

ArrayDeque 重写了 JDK 序列化的逻辑，只把 elements 数组中有用元素的部分序列化，而不会序列化整个数组。

// 序列化进程
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    // 写入数组长度
    s.writeInt(size());
    // 写入从 head 指针到 tail 指针之间的有用元素
    int mask = elements.length - 1;
    for (int i = head; i != tail; i = (i + 1) & mask)
        s.writeObject(elements[i]);
}
// 反序列化进程
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    // 读取数组长度
    int size = s.readInt();
    // 核算最近的 2 的整数幂
    int capacity = calculateSize(size);
    // 分配数组
    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
    allocateElements(size);
    // 设置头尾指针
    head = 0;
    tail = size;
    // 将数据规整到数组下标 0 方位
    for (int i = 0; i < size; i++)
        elements[i] = s.readObject();
}

4.7 ArrayDeque 的 clone() 进程

ArrayDeque 中的 elements 数组是引证类型，因而在 clone() 中需求完成深拷贝，否则原目标与克隆目标会相互影响：

public ArrayDeque<E> clone() {
    try {
        @SuppressWarnings("unchecked")
        ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
        result.elements = Arrays.copyOf(elements, elements.length);
        return result;
    } catch (CloneNotSupportedException e) {
        throw new AssertionError();
    }
}

---

5. 总结

• 1、ArrayDeque 是根据动态数组的线性表，具有 Queue 和 Stack 的行为，但不具有 List 的行为；

• 2、ArrayDeque 的数组容量是 2 的整数幂，在扩容时容量会翻倍，且不支撑 null 元素；

• 3、ArrayDeque 和 LinkedList 的栈和行列行为都是 O(1) 时刻杂乱度，ArrayDeque 的入栈和入队有或许会触发扩容，但从均摊分析上看仍然是 O(1) 时刻杂乱度；

• 4、ArrayDeque 是一块连续内存空间，根据局部性原理能够更好地射中 CPU 缓存行，而 LinkedList 是离散的内存空间对缓存行不友好；

• 5、ArrayDeque 和 LinkedList 都不考虑线程同步，不确保线程安全。

---

版权声明

本文为稀土技能社区首发签约文章，14天内制止转载，14天后未获授权制止转载，侵权必究！

参考资料

• 数据结构与算法之美（第 4、8、9 讲） —— 王争 著，极客时刻 出品
• 17 张图带你深度分析 ArrayDeque（JDK双端行列）源码 —— 一无可取的研讨僧
• Java 容器源码分析之 Deque 与 ArrayDeque —— jrthe42 著
• Why null values are not allowed in ArrayDeque? —— stack overflow