LinkedList 源码分析

LinkedList 简介 是一个基于双向链表实现的集合类，经常被拿来和 做比较。关于 和 的详细对比，我们 Java 集合常见面试题总结(上)有详细介绍到。 不过，我们在项目中一般是不会使用到 的，需要用到 的场景几乎都可以使用 来代替，并且，性能通常会更好！就连 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 。 另外，不要下意识地认为 作为链表就最适合元素增删的场景。我在上面也说了， 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的平均时间复杂度都是 O(n)。 LinkedList 插入和删除元素的时间复杂度？ 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。 LinkedList 为什么不能实现 RandomAccess 接口？ 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 接口。 LinkedList 源码分析 这里以 JDK1.8 为例，分析一下 的底层核心源码。 的类定义如下： 继承了 ，而 又继承于 。 阅读过 的源码我们就知道， 同样继承了 ， 所以 会有大部分方法和 相似。 实现了以下接口： : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。 ：继承自 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。需要注意， 的发音为 "deck" [dɛk]，这个大部分人都会读错。 ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。 : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。 中的元素是通过 定义的： 初始化 中有一个无参构造函数和一个有参构造函数。 插入元素 除了实现了 接口相关方法，还实现了 接口的很多方法，所以我们有很多种方式插入元素。 我们这里以 接口中相关的插入方法为例进行源码讲解，对应的是 方法。 方法有两个版本： ：用于在 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。 :用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/4 个元素，时间复杂度为 O(n)。 获取元素 获取元素相关的方法一共有 3 个： 1. ：获取链表的第一个元素。 2. ：获取链表的最后一个元素。 3. ：获取链表指定位置的元素。 这里的核心在于 这个方法： 或 等方法内部都调用了该方法来获取对应的节点。 从这个方法的源码可以看出，该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半，就从链表头开始遍历，反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率。 删除元素 删除元素相关的方法一共有 5 个： 1. ：删除并返回链表的第一个元素。 2. ：删除并返回链表的最后一个元素。 3. ：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。 4. ：删除指定索引处的元素，并返回该元素的值。 5. ：移除此链表中的所有元素。 这里的核心在于 这个方法： 方法的逻辑如下： 1. 首先获取待删除节点 x 的前驱和后继节点； 2. 判断待删除节点是否为头节点或尾节点： 如果 x 是头节点，则将 first 指向 x 的后继节点 next 如果 x 是尾节点，则将 last 指向 x 的前驱节点 prev 如果 x 不是头节点也不是尾节点，执行下一步操作 3. 将待删除节点 x 的前驱的后继指向待删除节点的后继 next，断开 x 和 x.prev 之间的链接； 4. 将待删除节点 x 的后继的前驱指向待删除节点的前驱 prev，断开 x 和 x.next 之间的链接； 5. 将待删除节点 x 的元素置空，修改链表长度。 可以参考下图理解（图源：LinkedList 源码分析(JDK 1.8)）： 遍历链表 推荐使用 循环来遍历 中的元素， 循环最终会转换成迭代器形式。 的遍历的核心就是它的迭代器的实现。 下面我们对迭代器 中的核心方法进行详细介绍。 我们先来看下从头到尾方向的迭代： 再来看一下从尾到头方向的迭代： 如果需要删除或插入元素，也可以使用迭代器进行操作。 迭代器对应的移除元素的方法如下： LinkedList 常用方法测试 代码： 输出： 写在最后 如果内容对你有帮助的话，欢迎顺手给 JavaGuide 点一个免费的 Star 支持一下：GitHub | Gitee。 JavaGuide 已持续维护近七年，累计 6100+ 次提交，来自 620+ 位贡献者共同完善。你的 Star、反馈和 PR，都是这个项目继续更新的动力。 如果你正在准备后端/AI 应用开发面试，也可以了解一下我的知识星球，里面包括后端和 AI 实战项目、简历优化、一对一提问和高频考点资料，已经持续维护六年。