关于android:说一下-ArrayDeque-和-LinkedList-的区别

大家好，我是小彭。

在上一篇文章里，咱们聊到了基于链表的 Queue 和 Stack 实现 —— LinkedList。那么 Java 中有没有基于数组的 Queue 和 Stack 实现呢？明天咱们就来聊聊这个话题。

小彭的 Android 交换群 02 群曾经建设啦，扫描文末二维码进入~

思维导图：

1. 回顾 LinkedList

在数据结构上，LinkedList 不仅实现了与 ArrayList 雷同的 List 接口，还实现了 Deque 接口，而咱们明天要讲的 ArrayDeque 就是实现于 Deque 接口的动静数组。

Deque 接口示意一个双端队列（Double Ended Queue），容许在队列的首尾两端操作，所以既能实现队列行为，也能实现栈行为。

1.1 Queue 接口

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

• 抛异样：

  • 向空队列取数据，会抛出 NoSuchElementException 异样；
  • 向容量满的队列加数据，会抛出 IllegalStateException 异样。

• 返回非凡值：

  • 向空队列取数据，会返回 null；
  • 向容量满的队列加数据，会返回 false。

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

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

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

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<E> 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 都不思考线程同步，不保障线程平安。

参考资料

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

小彭的 Android 交换群 02 群