2025年恋上链表之深入LinkedList源码分析

恋上链表之深入LinkedList源码分析背景摘要 在 List 集合中 我们最熟悉的就是 ArrayList 与 LinkedList 一谈到它们我们第一个反应就是 ArrayList 查询快 LinkedList 增删快 所以在增删操作频繁的场景下适合使用 LinkedList 而在其他场景 ArrayList 就够用了 那么前篇我们提到了 ArrayList 源码分析

大家好,我是讯享网,很高兴认识大家。

背景摘要:在List集合中,我们最熟悉的就是ArrayList与LinkedList。一谈到它们我们第一个反应就是ArrayList查询快,LinkedList增删快,所以在增删操作频繁的场景下适合使用LinkedList,而在其他场景ArrayList就够用了。那么前篇我们提到了ArrayList源码分析,今天再来细聊LinkedList。

目录

一、恋上链表

单向链表

双向链表

二、LinkedList

2.3、LinkedList集合新增快的原因

2.4、LinkedList删除背后的历程

2.5、LinkedList为什么查询慢?

折半查找


一、恋上链表

链表,它是一种数据结构,分为单项链表与双向链表。而今天要讲的LinkedList集合恰好就是双向链表结构的集合。我们要注意,LinkedList集合 不等于链表,它只是底层基于链表这种数据结构而实现。


讯享网

首先我们一张图来简单了解链表的单双向区别。

单向:当前链表节点(后面简称为节点或元素)只链接下一个节点。1链接2,2链接3。

双向:当前节点与上、下一个节点都有链接。1链接2, 2链接1、3, 3链接2。

1.1、单向链表

那么我们再仔细琢磨单向链表是如何链接下一个元素,为什么称作单向。

首先画出单向链表的数据结构,每个节点分为Item(当前元素值)与Next(下一个元素)两部分。那么我们得知在每一个节点中都会包含下一个节点,如1包含2。如果没有下一个节点,如3没有,那么值为NULL,即代表3为最后一个元素。

或许聪明的你会回忆发现LinkedList使用的是双向链表,正在疑惑哪里使用到单向链表呢?答案是HashMap。

我们谈到HashMap的组成,想到的就是数组+链表。那来一起看看JDK1.7中HashMap的一段源码,该源码中是一个链表结构的静态内部类,可以看到当前的结构与上图类似。

那么再看源码图中Entry<K,V>相当于一个节点,Next为当前节点的下一个节点。固我们得知,HashMap是由链表+数组实现,且链表的结构为单向链表。

随后躲在墙角的HashMap:

 

1.2、双向链表

了解完单向链表之后,我们再来看看双向链表。

首先双向链表比单向链表多了个prev(当前节点的上一个节点),如果当前元素是头部节点(First),那么prev值为NULL值,如图中节点1的指向。节点2前后都有数据,那么prev为1,next为3。节点3为尾部节点(Last)固next值为NULL。

这也就说明双向链表特征为前后相呼应。

那么双向列表的例子就是今天要细说的LinkedList主角了。

LinkedList:

二、LinkedList

集合源码分析案例项目码云地址:https://gitee.com/yiang-hz/gather

当前LinkedList类地址:https://gitee.com/yiang-hz/gather/tree/master/list/src/main/java/com/yiang/list

类名:YiangLinkedList,由于贴代码太长,这里就只做片段分析。可直接复制源码在IDEA进行调试。

首先依旧还是上次ArrayList源码分析时的List接口。

public interface YiangList<E> { int size(); E get(int index); boolean add(E e); E remove(int index); }

讯享网

2.1、成员变量

这里分析重要的三个成员变量。集合大小size,集合最后一个元素last,集合第一个元素first。也就是双向链表结构图中的节点1(first)与节点3(last)。

讯享网/ * 集合大小 */ transient int size = 0; / * 集合的最后一个元素 */ transient YiangLinkedList.Node<E> last; / * 集合的第一个元素 */ transient YiangLinkedList.Node<E> first;

2.2、静态内部类Node<E>

在双向链表中谈到的结构分别是prev、item、next。那么在LinkedList源码实现静态内部类中正好是该三项。

private static class Node<E> { / 当前元素 (HZ)*/ E item; / 当前元素的上一个元素 (HZ)*/ YiangLinkedList.Node<E> next; / 当前元素的下一个元素 (HZ)*/ YiangLinkedList.Node<E> prev; Node(YiangLinkedList.Node<E> prev, E element, YiangLinkedList.Node<E> next) { this.item = element; this.next = next; this.prev = prev; } Node(E element) { this.item = element; } }

所以从该源码我们得知,LinkedList底层确实是由双向列表构成。

 

2.3、LinkedList集合新增快的原因

LinkedList我们都知道新增快,那么为什么快?快在哪里?源码中怎么体现的?我们来一一分析。

讯享网/ * 默认会链接元素作为最后一个元素 * @param e 元素对象 * @return 是否添加成功 */ @Override public boolean add(E e) { addLast(e); return true; }

源码中add方法默认是调用addLast(e)方法的,也就是默认是从最后一个元素节点追加。

/ * 追加元素,位于最后一个之后 * @param e 元素 */ void addLast(E e){ //获取最后一个元素 final YiangLinkedList.Node<E> l = last; //创建当前元素 final YiangLinkedList.Node<E> node = new YiangLinkedList.Node<>(l, e, null); //最后一个元素的值等于该元素 last = node; //如果之前的最后一个元素为空,那么代表当前集合为空,node即成为最后一个元素 if (null == l){ first = node; } else { //否则将当前元素设置为之前的最后一个元素的下一个值 l.next = node; } //大小加1 size++; }

添加的实现步骤中

首先获取到之前的最后一个元素L,其次将当前存放的值创建成节点node,那么node的上一个节点为L,并将node设置为last节点。当然这里需要判断一种情况,如果L为空,那么证明当前集合是空集合,固first也要设置为node节点。否则代表L不为空,那么需要将L的下一个节点设置为Node。最后进行size+1。

图示:e为添加的元素

1.当前集合为空情况

2.当前集合包含元素情况

那么我们得知,LinkedList新增快的主要原因是,在添加时只需要获取最后一个节点Last,并更改Last节点和当前创建节点的引用链关系即可。所以相对于ArrayList的数组重新复制要快很多。

2.4、LinkedList删除背后的历程

说完了新增快的原因,我们再来看看删除快的原因以及它的经历过程。

讯享网@Override public E remove(int index) { //检测下标是否越界 checkElementIndex(index); //删除 return unlink(node(index)); }

删除需要检测下标是否越界(当前传入的index是否>0,并且是否小于size最大值)。当然还要找到需要删除的元素,再开始删除方法。

/ * 删除元素 通过链表的结构链接逻辑实现 */ E unlink(Node<E> x) { //当前元素的值, x为当前元素 final E element = x.item; //当前元素的上一个元素 YiangLinkedList.Node<E> prev = x.prev; //当前元素的下一个元素 YiangLinkedList.Node<E> next = x.next; //删除时,如果当前的元素的上一个元素为NULL,那么代表当前元素为第一个元素。 if (null == prev){ //所以删除后设置下一个元素为first first = next; } else{ //否则,代表该元素的上一个元素不为空,那么将上一个元素的下一个元素设置为 当前的next prev.next = next; // 如果上一个元素不为空,那么删除后需将当前元素的上一个元素置空 x.prev = null; } //如果当前的元素的下一个元素为NULL,那么代表当前元素为最后一个元素。 if (null == next){ //所以删除后设置上一个元素为last last = prev; } else{ //当前元素的下一个元素不为空,那么需要将下一个元素的上一个元素,设置为 当前的prev next.prev = prev; // 如果下一个元素不为空,那么删除后需将当前元素的下一个元素置空 x.next = null; } //这里将值赋值为空,让GC进行回收处理 x.item = null; //将大小size - 1 size--; return element; }

删除主要分为三种情况:

  1. 删除的节点为头部节点
  2. 删除的节点为尾部节点
  3. 删除的节点前后有相邻节点。

光看代码和文字是很枯燥乏味的,我们直接看实现原理图,再去看代码是怎么实现,思路就很清晰了。

第一种情况:

操作步骤:首先是删除节点1,其次把节点1的下一个节点,也就是节点2的   prev值  设置为NULL。并将节点2设置为头部节点。

第二种情况:

操作步骤:实现与第一种情况类似,首先是删除节点3,其次把节点3的上一个节点,也就是节点2的 next值 设置为NULL。并将节点2设置为尾部节点。

第三种情况:

这种情况最形象的例子就好比三个人(ABC)手牵着手,中间的那个人(B)离开了。那么A要牵C手,C要牵A手。

操作步骤:

删除节点2 --> 获取节点2上一个节点 节点1 。获取节点2的下一个节点 节点3。 --> 将节点1的 next值 设置为节点3,将节点3的prev值 设置为节点1。


那么当删除原理图看完之后,我们再去看代码中的设计,真是妙啊!

 

2.5、LinkedList为什么查询慢?

我们知道,在ArrayList中,查询快的原因是它底层通过数组实现,直接根据索引找到对应的元素即可。那么在LinkedList集合中是元素一个一个链接起来,没有索引概念的,那么当我们去进行查找时,就只能根据第一个元素,然后一个一个数位置,数到对应位置数量时才能找到需要查询的元素。

那么如果我们要从以下数据中查找 值为3,也就是第三个节点时。通常情况下指针会从1-3一个一个的去查找,非常耗时,且这里相当于Mysql的全表检索,是不是神似根据ID去查询某条记录呢?

当然,LinkedList查找并不完全是这样的,它做了一个优化,称为折半查找。

折半查找

我们看完类似于上图Mysql的全表检索之后,再来细说LinkedList在此做了什么优化。

讯享网/ * 根据索引查找到元素 * @param index 索引 * @return 元素 */ YiangLinkedList.Node<E> node(int index) { //LinkedList底层通过next与prev去连接元素,那么查询时,需要一个一个链接 //相当于一次全表查询,但LinkedList做了一个小优化,那就是 折半查询 //对比:链表 -> 全表查询 数组 -> 索引查询 //如果索引下标 小于 集合大小除2 index < size / 2 那么从 0-5折半查询 // 否之则从 10 - 6反向查询 实现折半查询 // 1.例如索引为0 size为10: 0 < 10 / 2,那么node等于第一个值,并且不会进行循环,直接返回第一个元素 // 2.例如索引为1 size为10: 1 < 10 / 2,那么node等于 第二个值,循环一次。并且返回 if (index < (size >> 1)){ YiangLinkedList.Node<E> node = first; for (int i = 0; i < index; i++) { node = node.next; } return node; } else{ //3.例如索引为6 size为10: 6 > 10 / 2,那么node等于倒数第4个值,循环4次。并且返回 YiangLinkedList.Node<E> node = last; //size - 1 拿到最后一个元素, 因为下标是从0开始,固需要-1 for (int i = size - 1; i > index ; i--) { node = node.prev; } return node; } }

代码中设计很巧妙,那么我们简单画两个图来说明。

从图中可知,通过算法在查找之前判断从那边开始查找更快,从而选择从头部节点或者尾部节点开始查找的方式即为折半查找。而LinkedList查找源码正是使用该种方法去进行查询。


总结

首先LinkedList是又链表中的双向链表实现,增删快的原理是只需要操作相邻两个数据即可。删除也需要先查找到当前节点。查询是通过类似Mysql的全表检索,虽进行了折半查找,但效率较ArrayList来说还是很低的。最终由于查询是一个一个遍历,导致查询速度过慢,所以日常使用的集合通常是ArrayList,而不是LinkedList。固LinkedList适合在特殊操作频繁场景可用来提高程序运行效率。

小讯
上一篇 2025-01-28 17:42
下一篇 2025-03-24 10:12

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131766.html