JDK8中LinkedList的工作原理剖析

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也并非是线程安全的,如果需要请使用其他并发工具包下提供的类。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-03-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏上善若水

0x15Java引用赋值,是原子操作吗? 线程安全吗?

所谓原子操作,就是该操作绝不会在执行完毕前被任何其他任务或事件打断,也就说,它的最小的执行单位,不可能有比它更小的执行单位,因此这里的原子实际是使用了物理学里的...

3272
来自专栏mathor

二分查找与二分答案(1)

2015
来自专栏专注 Java 基础分享

虚拟机字节码执行引擎

所谓的「虚拟机字节码执行引擎」其实就是 JVM 根据 Class 文件中给出的字节码指令,基于栈解释器的一种执行机制。通俗点来说,也就是 JVM 解析字节码指令...

2634
来自专栏csxiaoyao

LESS 学习demo

3657
来自专栏mathor

LeetCode90. 子集 II

 升级版子集问题,最简单的办法,先把所有元素存储到set中去重,然后再重新赋值给数组,再dfs,但这样做太简单了,没什么难度,于是换了一种做法,不去重,直...

2252
来自专栏专注 Java 基础分享

虚拟机字节码执行引擎

所谓的「虚拟机字节码执行引擎」其实就是 JVM 根据 Class 文件中给出的字节码指令,基于栈解释器的一种执行机制。通俗点来说,也就是 JVM 解析字节码指令...

4258
来自专栏前端进阶之路

从0到1实现Promise前言正文结束

Promise大家一定都不陌生了,JavaScript异步流程从最初的Callback,到Promise,到Generator,再到目前使用最多的Async/A...

1303
来自专栏小灰灰

JDK容器学习之CopyOnWriteArrayList:线程安全保障机制

JDK容器学习之CopyOnWriteArrayList 列表容器常见的有 ArrayList和LinkedList,然而两者都是非线程安全的,若应用场景对线...

29310
来自专栏软件开发 -- 分享 互助 成长

访问者模式

一、简介 1、访问者模式表示一个作用于某对象结构中各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。 2、模式中的成员角色 访问者(...

1845
来自专栏xingoo, 一个梦想做发明家的程序员

套接口编程

1 struct in_addr{ 2 in_addr_t s_addr; 3 }; 4 struct sockaddr_in{ 5 ...

2068

扫码关注云+社区

领取腾讯云代金券