图解 ArrayDeque 比 LinkedList 快

图解 ArrayDeque 比 LinkedList 快

  • 如果评论区没有及时回复,欢迎来公众号:ByteCode 咨询
  • 公众号:ByteCode。致力于分享最新技术原创文章,涉及 Kotlin、Jetpack、算法、译文、系统源码相关的文章

在之前的两篇文章中主要分析了 Java 栈的缺点为什么不推荐使用 Java 栈 ,以及 为什么不推荐直接使用 ArrayDeque 代替 Java Stack 。更多内容点击下方链接前去查看。

接口 Deque 的子类 ArrayDeque ,作为栈使用时比 Stack 快,因为原来的 Java 的 Stack 继承自 Vector,而 Vector 在每个方法中都加了锁,而 Deque 的子类 ArrayDeque 并没有锁的开销。

接口 Deque 还有另外一个子类 LinkedListLinkedList 基于双向链表实现的双端队列,ArrayDeque 作为队列使用时可能比 LinkedList 快。

而这篇文章主要来分析,为什么 ArrayDequeLinkedList 快。在开始分析之前,我们需要简单的了解一下它们的数据结构的特点。

接口 Deque

接口 Deque 继承自 Queue 即队列, 在 Java 中队列有两种形式,单向队列( AbstractQueue ) 和 双端队列( Deque ),单向队列效果如下所示,只能从一端进入,另外一端出去。

而今天主要介绍双端队列( Deque ), Deque 是双端队列的线性数据结构, 可以在两端进行插入和删除操作,效果如下所示。

双端队列( Deque )的子类分别是 ArrayDequeLinkedListArrayDeque 基于数组实现的双端队列,而 LinkedList 基于双向链表实现的双端队列,它们的继承关系如下图所示。

接口 DequeQueue 提供了两套 API ,存在两种形式,分别为抛出异常,和不抛出异常,返回一个特殊值 null 或者布尔值 ( true | false )。

操作类型 抛出异常 返回特殊值
插入 addXXX(e) offerXXX(e)
移除 removeXXX() pollXXX()
查找 element() peekXXX()

ArrayDeque

ArrayDeque 是基于(循环)数组的方式实现双端队列,数组初始化容量为 16(JDK 8),结构图如下所示。

ArrayDeque 具有以下特点:

  • 因为双端队列只能在头部和尾部插入或者删除元素,所以时间复杂度为 O(1),但是在扩容的时候需要批量移动元素,其时间复杂度为 O(n)
  • 扩容的时候,将数组长度扩容为原来的 2 倍,即 n << 1
  • 数组采用连续的内存地址空间,所以查询的时候,时间复杂度为 O(1)
  • 它是非线程安全的集合

LinkedList

LinkedList 基于双向链表实现的双端队列,它的结构图如下所示。

LinkedList 具有以下特点:

  • LinkedList 是基于双向链表的结构来存储元素,所以长度没有限制,因此不存在扩容机制
  • 由于链表的内存地址是非连续的,所以只能从头部或者尾部查找元素,查询的时间复杂为 O(n),但是 JDK 对 LinkedList 做了查找优化,当我们查找某个元素时,若 index < (size / 2),则从 head 往后查找,否则从 tail 开始往前查找 , 但是我们在计算时间复杂度的时候,常数项可以省略,故时间复杂度 O(n)
Node<E> node(int index) {
// size >> 1 等价于 size / 2
if (index < (size >> 1)) {
// form head to tail
} else {
// form tail to head
}
}
  • 链表通过指针去访问各个元素,所以插入、删除元素只需要更改指针指向即可,因此插入、删除的时间复杂度 O(1)
  • 它是非线程安全的集合

最后汇总一下 ArrayDequeLinkedList 的特点如下所示:

集合类型 数据结构 初始化及扩容 插入/删除时间复杂度 查询时间复杂度 是否是线程安全
ArrqyDeque 循环数组 初始化:16
扩容:2 倍
0(n) 0(1)
LinkedList 双向链表 0(1) 0(n)

为什么 ArrayDeque 比 LinkedList 快

了解完数据结构特点之后,接下来我们从两个方面分析为什么 ArrayDeque 作为队列使用时可能比 LinkedList 快。

  • 从速度的角度:ArrayDeque 基于数组实现双端队列,而 LinkedList 基于双向链表实现双端队列,数组采用连续的内存地址空间,通过下标索引访问,链表是非连续的内存地址空间,通过指针访问,所以在寻址方面数组的效率高于链表。

  • 从内存的角度:虽然 LinkedList 没有扩容的问题,但是插入元素的时候,需要创建一个 Node 对象, 换句话说每次都要执行 new 操作,当执行 new 操作的时候,其过程是非常慢的,会经历两个过程:类加载过程 、对象创建过程。

    • 类加载过程

      • 会先判断这个类是否已经初始化,如果没有初始化,会执行类的加载过程
      • 类的加载过程:加载、验证、准备、解析、初始化等等阶段,之后会执行 <clinit>() 方法,初始化静态变量,执行静态代码块等等
    • 对象创建过程

      • 如果类已经初始化了,直接执行对象的创建过程
      • 对象的创建过程:在堆内存中开辟一块空间,给开辟空间分配一个地址,之后执行初始化,会执行 <init>() 方法,初始化普通变量,调用普通代码块

接下来我们通过 算法动画图解 | 被 “废弃” 的 Java 栈,为什么还在用 文章中 LeetCode 算法题:有效的括号,来验证它们的执行速度,以及在内存方面的开销,代码如下所示:

class Solution {
public boolean isValid(String s) {

// LinkedList VS ArrayDeque

// Deque<Character> stack = new LinkedList<Character>();
Deque<Character> stack = new ArrayDeque<Character>();

// 开始遍历字符串
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 遇到左括号,则将其对应的右括号压入栈中
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
// 遇到右括号,判断当前元素是否和栈顶元素相等,不相等提前返回,结束循环
if (stack.isEmpty() || stack.poll() != c) {
return false;
}
}
}
// 通过判断栈是否为空,来检查是否是有效的括号
return stack.isEmpty();
}
}

正如你所看到的,核心算法都是一样的,通过接口 Deque 来访问,只是初始化接口 Deque 代码不一样。

// 通过 LinkedList 初始化     
Deque<Character> stack = new LinkedList<Character>();

// 通过 ArrayDeque 初始化
Deque<Character> stack = new ArrayDeque<Character>();

结果如上所示,无论是在执行速度、还是在内存开销上 ArrayDeque 的性能都比 LinkedList 要好。


如果有帮助 点个赞 就是对我最大的鼓励

代码不止,文章不停

欢迎关注公众号:ByteCode,持续分享最新的技术


致力于分享一系列 Android 系统源码、逆向分析、算法、翻译、Jetpack 源码相关的文章,在技术的道路上一起前进

Android10 源码分析

正在写一系列的 Android 10 源码分析的文章,了解系统源码,不仅有助于分析问题,在面试过程中,对我们也是非常有帮助的,如果你同我一样喜欢研究 Android 源码,可以关注我 GitHub 上的 Android10-Source-Analysis

算法题库的归纳和总结

由于 LeetCode 的题库庞大,每个分类都能筛选出数百道题,由于每个人的精力有限,不可能刷完所有题目,因此我按照经典类型题目去分类、和题目的难易程度去排序。

  • 数据结构: 数组、栈、队列、字符串、链表、树……
  • 算法: 查找算法、搜索算法、位运算、排序、数学、……

每道题目都会用 Java 和 kotlin 去实现,并且每道题目都有解题思路,如果你同我一样喜欢算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:Leetcode-Solutions-with-Java-And-Kotlin

精选国外的技术文章

目前正在整理和翻译一系列精选国外的技术文章,不仅仅是翻译,很多优秀的英文技术文章提供了很好思路和方法,每篇文章都会有译者思考部分,对原文的更加深入的解读,可以关注我 GitHub 上的 Technical-Article-Translation

评论