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

hi 大家好，我是 DHL。公众号：ByteCode ，专注分享最新技术原创文章，涉及 Kotlin、Jetpack、算法动画、数据结构 、系统源码、 LeetCode / 剑指 Offer / 多线程 / 国内外大厂算法题 等等。

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

twitter.com/joshbloch/s…

大神真的不用 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 是基于数组实现的双端队列，ArrayDeque 和 LinkedList 数据结构的特点如下所示。

更多关于 ArrayDeque 和 LinkedList 的优缺点，在什么情况下使用，以及它们谁更快，请前往查看 图解 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 快

• ArrayDeque 和 LinkedList 数据结构的特点？
• 为什么 ArrayDeque 比 LinkedList 快？

• 跟源码学数据结构 | 循环队列

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

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

代码不止，文章不停

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

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

• 个人博客，将所有文章进行分类，欢迎前去查看 hi-dhl.com
  
• KtKit 小巧而实用，用 Kotlin 语言编写的工具库，欢迎前去查看 KtKit
  
• 计划建立一个最全、最新的 AndroidX Jetpack 相关组件的实战项目 以及 相关组件原理分析文章，正在逐渐增加 Jetpack 新成员，仓库持续更新，欢迎前去查看 AndroidX-Jetpack-Practice
  
• LeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解，语言 Java 和 kotlin，包含多种解法、解题思路、时间复杂度、空间复杂度分析

• 剑指 offer 及国内外大厂面试题解：在线阅读
• LeetCode 系列题解：在线阅读

近期必读热门文章

• Oracle 官方推荐，使用 ReentrantLock 需要注意的细节
• Kotlin 宣布一个重磅特性
• Google 宣布废弃 LiveData.observe 方法
• 使用 kotlin 需要注意的一个细节
• 跟源码学数据结构 | 循环队列
• 图解 ArrayDeque 比 LinkedList 快
• 为什么不推荐 ArrayDeque 代替 Stack
• 算法动画图解 | 被 "废弃" 的 Java 栈，为什么还在用
• 影响性能的 Kotlin 代码（一）
• Jetpack Splashscreen 解析 | 助力新生代 IT 农民工 事半功倍
• 为数不多的人知道的 Kotlin 技巧及解析(三)
• 为数不多的人知道的 Kotlin 技巧以及 原理解析（二）
• 为数不多的人知道的 Kotlin 技巧以及 原理解析（一）
• 揭秘 Kotlin 中的 == 和 ===
• Kotlin 密封类进化了
• Kotlin 中的密封类 优于 带标签的类
• Kotlin Sealed 是什么？为什么 Google 都在用
• Android 12 行为变更，对应用产生的影响
• 图解多平台 AndroidStudio 技巧(三)