首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >JDK8中LinkedList的工作原理剖析

JDK8中LinkedList的工作原理剖析

作者头像
我是攻城师
发布2018-05-15 10:36:11
6870
发布2018-05-15 10:36:11
举报
文章被收录于专栏:我是攻城师我是攻城师

LinkedList虽然在日常开发中使用频率并不是很多,但作为一种和数组有别的数据结构,了解它的底层实现还是很有必要的。

在这之前我们先来复习下ArrayList的优缺点,ArrayList基于数组的动态管理实现的,数组在内存中是一块连续的存储地址并且数组的查询和遍历是非常快的;缺点在于在添加和删除元素时,需要大幅度拷贝和移动数据,还要考虑是否需要扩容操作,所以效率比较低。

正是由于上面的不足,才出现了链表的这种数据结构,首先链表在内存中并不是连续的,而是通过引用来关联所有元素的,所以链表的优点在于添加和删除元素比较快,因为只是移动指针,并且不需要判断是否扩容,缺点是查询和遍历效率比较低下。

首先,我们先看下LinkedList的继承结构:

从上面的源码里面可以看到:

LinkedList继承了AbstractSequentialList是一个双向链表,可以当做队列,堆栈,或者是双端队列。

实现了List接口可以有队列操作。

实现了Deque接口可以有双端队列操作

实现了Cloneable接口既可以用来做浅克隆

实现了Serializable接口可以用来做网络传输和持久化,同时可以使用序列化来做深度克隆。

下面我们先来看下LinkedList的核心数据结构:

然后在看下其成员变量和构造方法:

从上面可以看到LinkedList有两个构造函数,一个无参,一个有参,有参的构造函数的功能是通过一个集合参数并把它里面所有的元素给插入到LinkedList中,注意这里为什么说是插入,而不是说初始化添加,因为LinkedList并非线程安全,完全有可能在this()方法调用之后,已经有其他的线程向里面插入数据了。

(一)addAll方法分析

下面我们看下addAll方法的调用链:

这里面我们看到主要方法有两个:

首先是addAll(int index, Collection c)方法,这里面先判断了是否会出现索引越界的可能,然后分别初始化了两个临时节点pred和succ,分别作为index节点的前置节点和后置节点,如果不是在第一次初始化插入的情况下,这段代码的工作原理,大家可以理解为一个木棒一刀两断之后,第一段的末尾处就是前置节点,而第二段木棒的开始处就是后置节点,我们插入的数据就类似于放在两个木棒之间,然后在依次追加进来,最后把前置节点连接上和后置节点连接上,就相当于插入完成,变成了一根更长的木棒,这个过程大家用笔画一下,还是比较容易理解的。

然后大家看到还有一个方法node(int index),这个方法的主要功能是找到index个数上的Node节点,虽然源码里面已经做过遍历优化,折半查询,如果index小于size的一半,就从头开始向后遍历查询,否则就从后向前遍历查询,即使这样,遍历和查询仍然是链表的缺点,可以看成是O(n)操作。

(二)add方法分析

add方法无疑是操作链表经常用的方法,它的源码如下:

从上面我们看到add方法每次都会把新增节点放在链表的最后的一位,正是因为放在链表的末位,所以链表的添加性能可以看成O(1)操作。

(三)remove方法分析

移除方法有常用的有两个,一个是根据index移除,另外一个根据Object移除,源码如下:

从上面的源码里可以看到移除根据index移除里面调用了node(index)方法来查找需要移除的节点,而根据Object移除的时候,则是进行了整个链表的遍历,然后再卸载节点。

除此之外链表还有没有任何参数的remove,removeFirst,removeLast方法,其中remove方法本质是调用了removeFirst方法。

这里能够总结出来链表基于首尾节点的删除可以看成是O(1)操作,而非首尾的删除最坏的情况下能够达到O(n)操作,因为要遍历查询指定节点,所以性能较差。

(四)get方法分析

get系方法有三个,分别是get(index),getFirst(),getLast(),其中get(index)方法如下:

我们看到get(index)方法本质调用了node(index)方法,这个方法在前面分析过了性能一半,其他的getFirst和getLast不用多说了O(1)操作。

(五)set方法分析

源码如下:

set方法依旧是调用的node方法,所以链表在指定位置更新数据,性能也一般。

(六)clear方法分析

clear方法比较简单,就是所有的节点的数据置位null,方便垃圾回收

(七)toArray方法分析

声明一个长度一样的数组,依次遍历所有数据放入数组。

(八)序列化和反序列方法分析

这里我们看到链表中也自定义了序列化和反序列化的方法,在序列化时只写入x.item而并不是整个Node,这样做避免java自带的序列化机制会把整个Node的数据给写入序列化,并且如果Node还是双端链表的数据结构,那么无疑会导致重复两倍的空间浪费。

在反序列化时我们看到先读取size,然后根据size依次循环读取item,并重新生成双端链表的数据结构,依次追加到链表的尾部。

(九)关于操作队列或者堆栈的方法

文章开头说了LinkedList可以当双端队列或者堆栈使用,这里面有一系列的方法,这里只简单列举几个常用的方法,因为原理比较简单所以不在叙述:

总结:

本文介绍了JDK8中LinkedList的工作原理,并对其常用的方法进行了分析,LinkedList底层是一个链表,链表在内存中不是一块连续的地址,而是用多少就会申请多少,所以它比ArrayList更加节省空间, 此外它的添加方法和首末位的删除操作非常快,但是查询和遍历操作比较耗时。最后LinkedList还可以用来当做双端队列和堆栈容器,需要特别注意的是LinkedList也并非是线程安全的,如果需要请使用其他并发工具包下提供的类。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-03-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 我是攻城师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档