LinkedList 和 ArrayDeque的性能分析

LinkedList

LinkedList 不仅实现了与 ArrayList 相同的 List 接口，还实现了 Deque 接口，而我们今天要讲的 ArrayDeque 就是实现于 Deque 接口的动态数组。

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

Queue 的 API 可以分为 2 类，区别在于方法的拒绝策略上：

• 抛异常：
• • 向空队列取数据，会抛出 NoSuchElementException 异常；
  • 向容量满的队列加数据，会抛出 IllegalStateException 异常。
• 返回特殊值：
• • 向空队列取数据，会返回 null；
  • 向容量满的队列加数据，会返回 false。

Deque 接口（继承于 Queue 接口）

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

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

2.1 说一下 ArrayDeque 的特点1、ArrayDeque 是基于动态数组实现的 Deque 双端队列，内部封装了扩容和数据搬运的逻辑；2、ArrayDeque 的数组容量保证是 2 的整数幂；3、ArrayDeque 不是线程安全的；4、ArrayDeque 不支持 null 元素；5、ArrayDeque 虽然入栈和入队有可能会触发扩容，但从均摊分析上看依然是 O(1) 时间复杂度；

区别

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 在节点上增加了前驱和后继指针。

模拟栈和队列

如何使用数组实现队列

我们知道栈和队列都是 “操作受限” 的线性表：栈是 LIFO，限制在表的一端入栈和出栈。而队列是 FIFO，限制在表的一端入队，在另一端出队。栈和队列既可以用数组实现，也可以用链表实现：

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

这是因为在数组上同时实现 List 和 Queue 时，无法平衡这两个行为的性能矛盾。具体来说：ArrayList 不允许底层数据有空洞，所有的有效数据都会 “压缩” 到底层数组的首部。所以，使用 ArrayList 开发栈的结构或许合适，可以在数组的尾部操作数据。但使用 ArrayList 开发队列就不合适，因为在数组的首部入队或出队需要搬运数据。

使用数组实现栈相对容易，因为栈结构的操作被限制在数组的一端，所以我们可以选择数组的尾部作为栈顶，并且使用一个 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)。

使用数组实现队列相对复杂，我们需要一个队头指针和一个队尾指针：

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

对于出队而言，时间复杂度总是 O(1)。对于入队而言，当 tail == n 时，就需要扩容和搬运数据来容纳新的数据，我们用均摊分析法得出均摊时间复杂度依然是 O(1)，就不重复了。

但是我们发现，栈的 top == n 表示栈空间不足，扩容没有问题，而队列的 tail == n 却不一定表示队列空间不足。因为入队和出队发生在不同方向，有可能出现 tail == n 但队头依然有非常多剩余空间的情况。此时，扩容显得没有必要。

使用数组实现队列结构

使用数组实现队列相对复杂，我们需要一个队头指针和一个队尾指针：

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

对于出队而言，时间复杂度总是 O(1)。对于入队而言，当 tail == n 时，就需要扩容和搬运数据来容纳新的数据，我们用均摊分析法得出均摊时间复杂度依然是 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 的实现原理，就显得游刃有余了。

转载自 LinkedList 和 ArrayDeque的性能分析？ - 知乎 (zhihu.com)

linkedList的作者都没有从不使用linkedList

LinkedList的内存占用是ArrayList的4-6倍