《数据结构》第十三篇、java中LinkedList源码解析

天才雷普利.jpg

引言

今天要给大家介绍java的中的LinkedList的源码，跟第九篇讲解的ArrayList一样，我们今天同样是通过Android的环境下来看LinkedList源码。

同样的，可能我们看到的源码和你在java环境下看到的源码是不一致的，因为android系统对java的这些源码做了适当的更改，但是大致原理是一致的，看懂了本篇文章，那么java下方的LinkedList也就能看懂了。

我们先来预览一下

我先贴张图，大家来感受一下

LinkedList源码.png

我们看到，本LinkedList的源码总行数也是1262行左右的样子，也不是很多，所以大家在学习的时候应该没有什么压力。

我们的任务是

对，我们现在制定一些任务，我们需要分析下LinkedList的几个主要的方法：

创建

增

删

改

查

转成数组

获取集合长度

清空集合

恩，基本就这么几项吧。

ok,那么我们现在开始我们的旅程吧

首先提一句，LinkedList内部结构其实是链表中的“双向链表”，所以我们在进行上方方法源码的分析时，需要考虑到这一点。

“双向链表”的特点是：链表中的结点拥有前指针、中间值、后指针

而java中是没有”指针“这样的形式的东西的，但是java中有”引用“这样的含义，所以LinkedList源码中是用到了“对象的引用”这样的关系，实现了前指针、后指针的对象的指向关系。

1、创建（LinkedList的构造方法）

我们先来看下LinkedList的构造方法有几种：

LInkedList的构造方法.png

如上图，有两个构造方法，一个空参的，一个有参的

那么，我们先看下空参的构造方法

1.1空参构造方法

LinkedList无参的构造方法.png

我们发现，这里面啥也没做，于是我猜想，该构造方法应该在添加元素的时候，做了一个集合初始化的操作。

所以说，本方法，我们就跳过了。

1.2有参的构造方法

LinkedList有参构造方法.png

先来解释下注释:

构建一个包含着 "按照既定顺序排列" 的所有指定元素的集合

大致意思就是：

构造一个集合，并且将传入参数的那个集合的所有元素按照顺序都存储进这个集合中

而这个构造方法中的第一行“this()”，由于无参构造方法啥也没做，所以主要的功能还是在“addAll()”这个逻辑里面，所以我们来看下addAll()方法

addAll()方法.png

来解释下注释：

将参数中的集合中的所有元素，都按照原来的顺序依次添加到被添加集合的后边，且这个参数集合不能为空

我们看到里面调用了两个参数的addAll(size,c)方法

那么我们来看一下这个两个参数的构造方法

addAll()方法的注释.png

addAll()方法的主体.png

解释下注释：

从指定的位置开始，按照传入集合中元素的顺序，依次将元素插入，并且将之前插入元素位置之后的元素，往后平移

大致意思是

跟一个参数的构造方法类似，只不过，这个两个参数的构造方法会从指定位置（即第一个元素指定的位置）开始按照集合的顺序依次插入元素。

我对这些代码的逻辑做了一个注释

addAll()方法注释.png

为了能一页截下来图，我把字体弄小了...

每一行都有注释，如果还是看不懂，直接留言哈。

这样这个两个参数的addAll()方法执行完后，就完成了LinkedList的构造方法了。

逻辑稍微有点乱，我画了张流程图，大家体会一下哈

带参构造方法.png

ok，构造方法就先到这里，接下来，我们来看下”增“的方法

2、增

下面我们来现在add方法

add方法.png

只有一个，我们往里看

add详细方法.png

好，我们解释下注释

将指定元素添加到集合的最后边

我们看到，add方法里面实际上调用了

linkLast方法

linkLast

我们看一下

linkLast.png

我们来看下代码，我做了个注释，这个不难

linkLast加注释.png

看到了linkLast，我又看了一眼LinkedList的结构，里面还有这些方法，看一下

link其他方法.png

我们看到，除了linkLast还有一个linkBefore 、linkFirst两个方法，我们依次看一下

linkFirst

linkFirst.png

注释的意思是

将元素添加为集合的第一个元素

ok，代码也不难，解释一下

linkfirst注释.png

好，我们再来看下linkBefore

linkBefore

linkBefore.png

注释的意思是：

将元素插入到一个指定的非空元素前

同样，也不难

linkBefore注释.png

ok，增的方法，我们大致做一个总结，大体思路就是先找到要添加新元素的位置，然后创建新的元素，然后将新的元素的指针关系做好连接，然后对集合进行增长，就ok了

好，我们来看下删除的操作

3、删

remove.png

两个删除的方法 在结构显示中距离的好远啊~~

好我们先看第一个

3.1、remove(Object)

先看方法的定义

remove(Object).png

先看注释：

如果集合中存在与指定的元素的值相同的元素，则将第一次出现的该元素进行删除，如果集合中不存在这个元素，那么这个集合就不会改变

我对代码做了注释，来看一下

remove(Object)注释.png

unlink

我们看到，里面引用了unlink方法，我们来看一下

unlink方法.png

注释的意思是：

断开传入的非空结点的连接关系

我们来看下注释

unlink方法注释.png

代码的意思就是断开要删除结点和其前后结点之间的关系，然后再将前后结点先关联，最终返回删除的元素的值

ok，既然后unlink方法，那么linkedList还为我们提供了另外两个方法

我们来看一下

unlink的其他两个方法.png

ok，我们先看unlinkFirst方法

unlinkFirst

unlinkFirst.png

注释的意思是

断开非空头结点

那么我们已经看过了unlink方法了，其实这个方法就更简单了，因为头结点还少一个前指针的处理，只需要处理下后指针就可以了

我们来看一下注释

unlinkFirst注释.png

ok，注释很明白了，大家好好看哦

那么接下来，我们看一下unlinkLast

unlinkLast

unlinkLast.png

注释就是

断开非空尾节点

那么其实这个方法与上方的断开头结点类似，即大致操作就是将尾节点的前指针关系断开，然后将新的尾节点进行判断，重新给first 和last这两个集合中的头 尾标识做一个替换即可，

我们来看一下注释吧

unlinkLast注释.png

ok,到这里，linkedList的删除的方法就告一段落了，接下来，我们先看下查

4、查

get方法.png

查的方法有三个，即上图所表示的

getFirst():拿到头结点

getLast():拿到尾节点

get(int):拿到指定索引上的元素

ok,我们先从最难的开始看起：

get(int)根据索引开始看起

前边我们提到了ArrayList的查询方法，他的内部实现是比较简单的，因为ArrayList内部是数组来实现的，而数组里面的元素是内存地址连续的，而且自带索引，所以根据索引值能很快的定位到我们想要的元素

而linkedList他的内存地址由于是不连续的，所以他的查询方法就要比ArrayList复杂的多

我们开看下源代码

get方法.png

先来看下注释呢

从集合中得到指定位置的元素

我们看到代码就两行，第一行是对传入的位置做了一个安全校验

里面的意思就是判断你要查询的元素的位置是否合法：如果传入的位置小于0，或者大于集合的长度，那么就会报异常，如果传入的位置合法就会调用

node(index)方法

所以我们来看一下node(index)方法

node(index).png

他的注释和get(index)的注释是一致的，我们直接给他注释一下吧

node(index)注释.png

这个node(index)里面有一个小小的技巧，即先判断要查询的元素位置是否小于或者大于集合长度的一半，如果小于一半，那么就从头部开始找起，如果大于一半，就从尾部开始找起，这样对查找速率大大提高，当然了这个算法的前提是，linkedList的实现是双向链表的原因。

ok,通过node(index)拿到结点，然后再通过node.item拿到该结点的值，返回回去，这样linkedList的get(index)方法就结束了。

难的方法看完了，我们再看看简单的

getFirst()

getFirst.png

返回集合的头结点，如果集合为空，则会报出NoSuchElementException的错误

ok，代码很简单了，因为first就是集合的头结点 所以直接返回就好了，后边又做了一个为空判断，如果为空就报异常

那么看完getFirst()那么getLast我们也就容易想到了，我贴出来，感受一下啦

getLast()

getLast.png

恩 就是把全局的指向尾结点的last赋值给了新的l结点，然后做了非空判断，然后返回了新结点L的值

也是很简单撒~~

总结一下，其实get(index)的方法还是略复杂一点点啦，其余的getFirst getLast都是很简单的。

下边，我们来看一下，改的方法

5、改

改.png

注释的意思是：

将集合中的指定的位置的元素用指定的元素替换掉

方法的用意很简单，我们还是直接看代码吧

首先 对要替换元素的索引做了一个校验，然后再通过

node(index)方法（这个方法就是上边get(index)方法中调用的方法）

进行结点的查找，然后拿出被替换结点中的值 并且赋值给 E oldVal 这个值稍后当做返回值返回

然后把被替换结点中的值置为 新的 值

所以，这个替换的方法其实更简单，即

1、先找到这个要替换的结点

2、然后再将结点中的值替换成新的值

完工~

好了，我们接着看Linkedlist另外的方法

6、转成数组

转成数组是集合的一个共有的方法，我们来看一下linkedList是怎么实现的

转成数组.png

转成数组这个方法，linkedList同ArrayList一样，也提供了两个方法，即一个无参的，一个需要传入一个数组的

我们先来看一下无参的

6.1无参转数组方法

无参转数组方法.png

注释的意思是

返回一个包含着集合中所有元素的数组，且这些元素的顺序和集合中元素的顺序是一致的

我们直接给代码加注释吧

toArray注释.png

很简单，就是从头结点开始依次向后遍历，逐个将结点中的值赋值给新的数组元素

接下来，我们看看有参的转数组方法

6.2有参转数组方法

有参转数组方法.png

注释很长，我这就缩短点翻一下

返回一个包含着集合中的所有元素的数组，且这些元素的顺序和集合中的顺序是一致的，这个返回的数组是一个指定好的数组，如果这个指定好的数组和集合相匹配（主要是size），那么就返回这个指定好的数组，如果不匹配,那么将会创建一个新的匹配的数组，并将元素存入，并返回

好，接下来看下代码注释

toArray有参转数组方法注释.png

恩这个有参的转数组方法就是在无参的基础上，做了一个传入数组的长度的校验，如果长度不够，则创建一个和集合长度一致的数组，然后再一一赋值即可

好，接下来，我们看看如何获取linkedList的长度，其实看到这里，应该不需要细讲了，因为linkedList中的全局变量size就是集合的长度啊，不过出于文章的严谨，我们还是写下来吧

7、获取LinkedList的长度

size方法.png

恩。。。好吧不需要说了，我们接着看如何清空LinkedList吧

8、清空LinkedList

clear方法.png

清空集合的方法是clear方法

我们看看方法原型

clear原型.png

注释的意思是

清空这个集合中的所有元素，这个方法执行完后，集合就成为空集合了

我们看看方法里做了什么操作

clear方法注释.png

恩，很简单，就是依次遍历所有结点，然后把前指针，后指针、值 全都置为空即可，最后让size置为0，全局变量first last结点都指向null即可

恩 ，到这儿这个LinkedList中的主要方法就聊的差不多了，我们纵观全文，发现其实linkedList的

增

删

方法其实耗费的时间并不多，只需要调整下结点之间的指向（引用）关系就行了，但是

查

改

这两个操作，还需要从头开始遍历（不过linkedList由于是双向链表，所以也可以从尾开始遍历）找到指定结点，然后再做操作，比ArrayList费时一些，所以如果后续我们用到的集合查询的比较多的话，要多使用ArrayList，若是增删比较多的话，还是选择一下LinkedList吧