说一下 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 的属性很好理解的，不出意外的话又有小朋友出来举手提问了：

• 标签：head,ArrayDeque,LinkedList,区别,tail,elements,数组,null
  From： https://www.cnblogs.com/pengxurui/p/16922402.html