LinkedList 落幕了吗?作者自己都不用

LinkedList 落幕了吗?作者自己都不用

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

近期,看到网上有小伙伴们在讨论 LinkedList 作者自己都不用 LinkedList,我特意从网上搜索了一下,结果真让我找到了。

https://twitter.com/joshbloch/status/583813919019573248

大神真的不用 LinkedList 了吗? 我仔细扒了一下,如下图所示,大神的回复。

其实大神非常喜欢链表的数据结构,在 C 语言中是非常有用的。并且也非常认可 ArrayDeque 的实现,因为 ArrayDeque 作为栈使用时可能比 Stack 快,作为队列使用时可能比 LinkedList 快。

但是为什么不用 LinkedList 呢?LinkedList 基于双向链表实现的双端队列,链表 和 队列都是非常好的数据结构,但是 Java 中 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)
  • 它是非线程安全的集合

LinkedList 属于链式队列,与之相对应的 ArrayDeque 是基于数组实现的双端队列,ArrayDequeLinkedList 数据结构的特点如下所示。

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

更多关于 ArrayDequeLinkedList 的优缺点,在什么情况下使用,以及它们谁更快,请前往查看 图解 ArrayDeque 比 LinkedList 快

了解完数据结构特点之后,接下来我们从两个方面分析为什么 LinkedList 存在性能问题。

LinkedList 存在的性能问题

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

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

    • 类加载过程

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

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

在上一篇文章 图解 ArrayDeque 比 LinkedList 快速度内存 两个方面分析了 ArrayDeque 的性能都比 LinkedList 要好,并结合实际的案例来验证,结果如下图所示。

在之前的文章中,我围绕着 LinkedList (栈、队列 等等)写了四篇文章,从不同的角度进行了分析。

  • 算法动画图解 | 被 “废弃” 的 Java 栈,为什么还在用

    • 栈的定义
    • 栈的实现
      • 为什么不推荐使用 Java 栈
        • 性能低
        • 破坏了原有的数据结构
      • 不推荐使用了,为什么现在还在用
      • 为什么推荐使用 Deque 接口替换栈
        • 效率比 Java 栈快
        • 屏蔽掉无关的方法
      • Stack 和 ArrayDeque 区别
      • 栈的时间复杂度
    • 栈的实战
  • 为什么不推荐 ArrayDeque 代替 Stack

    • 为什么不推荐使用 Java 栈
    • JDK 推荐使用 ArrayDeque 代替 Stack 真的合理吗
    • 大神不推荐使用 ArrayDeque 代替 Stack
    • 如何实现一个真正意义上的栈
  • 图解 ArrayDeque 比 LinkedList 快

    • ArrayDequeLinkedList 数据结构的特点?
    • 为什么 ArrayDequeLinkedList 快?
  • 跟源码学数据结构 | 循环队列

    • 主要来学习如何设计循环队列
    • JDK 源码是如何设计队列?
    • 队列的大小为什么要设置成 2 的整数次幂?
    • 位运算 效率比 非位运算 快多少?
    • ArrayDeque 的 2 的整数次幂计算逻辑和 HashMap 有什么区别?
    • 自己如何设计一个循环队列?


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

代码不止,文章不停

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



最后推荐长期更新和维护的项目:

  • 个人博客,将所有文章进行分类,欢迎前去查看 https://hi-dhl.com

  • KtKit 小巧而实用,用 Kotlin 语言编写的工具库,欢迎前去查看 KtKit

  • 计划建立一个最全、最新的 AndroidX Jetpack 相关组件的实战项目 以及 相关组件原理分析文章,正在逐渐增加 Jetpack 新成员,仓库持续更新,欢迎前去查看 AndroidX-Jetpack-Practice

  • LeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解,语言 Java 和 kotlin,包含多种解法、解题思路、时间复杂度、空间复杂度分析

近期必读热门文章

致力于分享一系列 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

评论