温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何实现LinkedList源码解析

发布时间:2021-12-23 16:43:22 来源:亿速云 阅读:319 作者:柒染 栏目:大数据

这期内容当中小编将会给大家带来有关如何实现LinkedList源码解析,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。

我们主要介绍LinkedList集合类。它和ArrayList不同的是,LinkedList底层是通过双向链表的方式实现的。下面我们介绍一下双向链表的知识。ArrayList底层数组在处理业务有一个很大的性能问题,就是如果我们从数组的中间位置要删除一个元素要付出很大的代价,原因就是将元素删除之后,这个元素后面的元素都要向数组的前端移动,所以会造成性能的损失,同样,在数组的中间位置插入元素时,也会有上述等问题。于是Java的设计者们为了解决ArrayList的性能问题时,于是LinkedList诞生了。因为它底层是采用双向链表的方式实现的,所以不会出现上述等问题。下面我们详细了解一下链表这个数据结构。

数组的底层实现是在连续的内存上存储的对象的信息,而在链表中却不是这样的,它会将每一个对象都存储在不同的独立的节点中,并且每个节点中除了存储要保存的数据信息外,还将存储上一个节点的引用和下一个节点的引用信息。在Java中可以将它们叫做前驱节点和后继节点。如下图所示:

如何实现LinkedList源码解析

所以在我们使用LinkedList集合类时,从LinkedList删除一个元素是很方便的,并且性能是非常高的,因为它只需要把相应节点中的前驱节点和后继节点的引用删除就可以了,而不需要执行其它的额外操作。如下图所示:

如何实现LinkedList源码解析

所以,通过上面双向链表数据结构的特性,使我们知道在使用LinkedList集合类时,如果有频繁的插入和删除操作时,那么使用LinkedList集合类时效率会比较高。但LinkedList集合的检索速度与ArrayList集合相比性能却要低很多,原因就是双链表的存储方式并不一定是连续的内存,所以在检索时,必须从双链表的第一个节点一个一个的向后查找,所以会消耗大量的查询时间,降低程序的运行性能。下面我们来分析一下LinkedList集合类的源码来看看底层是怎么实现上述功能的。

如何实现LinkedList源码解析

LinkedList的构造方法,这里只是定义了一个空的构造方法,并没有其它的逻辑实现。可能有人想说,那我们完全可以不定义这个空的构造方法啊,反正虚拟机也会为我们自动创建,那为什么还要定义一个空的呢?虚拟机的确会为类自动创建一个空的构造方法,但这里有一个条件,那就是当前类中不能有其它的构造方法。如果虚拟机发现在当前类中已经有了其它的构造方法时,那么虚拟机在执行时是不会为我们自动创建新的构造方法的。在LinkedList中其实已经有了很多有参的构造方法,所以创建上述无参的构造方法,只是为了方便我们创建无参的LinkedList对象, 方便我们实例化用的。

如何实现LinkedList源码解析

LinkedList中的添加方法,方法比较简单主要就是调用了linkLast()方法,可见该方法就是实现整个add()方法逻辑的主要方法。下面我们看一下该方法的源码。

如何实现LinkedList源码解析

我们看到此方法中使用了一个Node这个类,那我们先看看这个类的定义。

如何实现LinkedList源码解析


现在我们知道了这个Node类是LinkedList集合中的一个内部类,它的功就相当于双链表中的节点,所以这个类中除了保存了当前元素外,还保存了这个元素的前驱节点,和后继节点。所以在linkLast()方法的前两句代码的意思就是将当前节点保存到一个新的节点中,然后在将链表中的最后一个元素设置为当前元素的前驱节点,然后在将当前元素的后继节点设置为null。这样就把数据添加到了当前节点中。所以LinkedList集合中的add()方法,每次都会把元素添加到链表的后端,这也是保证在LinkedList集合存储元素顺序的根本原因。将后继节点设置为null的目的是在双链表中此节点为最后一个节点。

通过上述的分析使我们知道LinkedList集合和ArrayList集合一样,也不是线程安全的,所以在多线程开发时也要额外添加同步代码,保证集合的线程安全。

上述就是小编为大家分享的如何实现LinkedList源码解析了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI