jdk8下LinkList源码分析实现原理

末蓝、 2022-11-05 13:51 152阅读 0赞

1.LinkedList  
继承：抽象类AbstractSequentialList  
实现：接口List、接口Cloneable、接口Serializable  
![在这里插入图片描述][20210306205046378.png]  
2.LinkedList的初始化  
两个构造函数：  
![在这里插入图片描述][20210306205152294.png]

先看看无参构造函数  
![在这里插入图片描述][20210306205235455.png]  
注释说的是：构建一个空的list，那么new LinkedList()得到的是一个怎么样的实例呢？  
![在这里插入图片描述][20210306205448887.png]  
![在这里插入图片描述][20210306205913138.png]  
通过断点，发现这几个属性：size=0，first=null，last=null，也说明了各自的作用，那么怎么实现的呢  
先看看者几个属性的定义：  
![在这里插入图片描述][2021030621031582.png]  
**size**:顾名思义，就是LinkedList的存储的元素的个数  
**first**:注释为：指向第一个node的指针  
**last**注释为：指向最后一个node的指针

内存大概示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70]

那么node是什么呢？可以看到first和last都是Node类型，来看看Node![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 1]  
此类定义在LinkedList类中，被private和static修饰，说明只能在  
LinkedList类中访问，跟着LinkedList类一起初始化。

看到Node的结构，有没有似曾相识的感觉，没错，这种结构是现双向链表的结构。也就是说LinkedList的数据结构为**双向链表**，可以理解为一个Node实例就是LinkedList中的一个数据，分别有指向上一个数据和下一个数据的指针。

2.LinkedList的add()方法  
那么这种双向链表的数据结构具体怎么实现呢？来看看add()方法  
![在这里插入图片描述][20210306212453384.png]  
可以看到有五种添加数据的方法  
先看第一个add(E)  
![在这里插入图片描述][20210306212738317.png]  
源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 2]  
很简单，调用linkLast(e)方法，看看此方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 3]  
可能看起来不太容易懂，没关系，懂结果就行，看看执行add()以后的内存：

内存大概示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 4]  
debug看看：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 5]  
first和last指向的是同一个Node实例。

此时多添加一些数据：  
![在这里插入图片描述][20210307122149724.png]  
内存结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 6]  
此时双向链表结构就很明显了。

然后再来看看LinkedList的第二个构造方法：LinkedList(Collection<? extends E>)  
源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 7]  
可以看到此构造方法很简单，调用的第一个构造方法进行的实例化，然后在调用方法addAll(Collection<? extends E>)，addAll(Collection<? extends E>)下面讲解

来看看第二个add方法：add(int, E)：此方法将元素存放在指定下标位置  
前面说了linkedList的存储方式为**双向链表**结构，并不能跟**数组**一样通过**下标**直接存取数据，那么这里指定下标存放数据怎么实现的呢？看看源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 8]  
如果是追加到末尾，那跟add(E)方法一样，调用linkLast(element)  
如果不是，调用linkBefore(element, node(index))  
第二个参数调用了node(index)方法，此方法的作用为获取index位置的Node元素，源码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 9]  
注释为：返回指定index下标的Node元素数据，如果index为0，那就是第一个Node，如果为size-1那就是最后一个Node

看看linkBefore(element, node(index));方法，源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 10]  
可以看到通过prev和next的指针修改，表明新元素会放到index元素的前面，如果新元素放在了第一位，那么还要修改LinkedList的first指针，指向新元素。

[20210306205046378.png]: /images/20221023/970c7b1c1f264dbe885f244f10eef638.png
[20210306205152294.png]: /images/20221023/ef83aad69e5c40a5a887189a08fbbebf.png
[20210306205235455.png]: /images/20221023/fc60718181ef4b4ebb1e8cde67bcd6e6.png
[20210306205448887.png]: /images/20221023/29fcf01a3e19455bb39b99aa784d26a9.png
[20210306205913138.png]: /images/20221023/3f4b8b6a830b4ae6add3e7e793558fde.png
[2021030621031582.png]: /images/20221023/e96df33da90f4f06a9873ba07e7cb3b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70]: /images/20221023/0eaca438ef844ba5a504aaf506799684.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/531d8e9a218740c7a89ee75b87f79d09.png
[20210306212453384.png]: /images/20221023/106c010d12df4f31accd38a3e9ad5941.png
[20210306212738317.png]: /images/20221023/e332a28e0fd04d24b70ac035927e56df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/bdba1dc90cbc4864a79b2c14344f98f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 3]: /images/20221023/23be2d2ecc164352b343fc231b2e2ead.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 4]: /images/20221023/a13dcf383f6149538d90a6cd8e03a320.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 5]: /images/20221023/07d589b2c3254d52a88f710622717132.png
[20210307122149724.png]: /images/20221023/28d89a9234344142a1f4c8f54d992ebd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 6]: /images/20221023/5c0c060320f642bab1f2450c34b4d3b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 7]: /images/20221023/b0c662829680457fae3493eda3bd5967.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 8]: /images/20221023/c02359a662c4469da5b8051065270cfd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 9]: /images/20221023/f58b8baef3504d72b2c6176e9bffb330.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 10]: /images/20221023/e1104b40feb04c539b65599d590c40af.png