jdk8下LinkList源码分析实现原理

发布于:2021-06-11 11:10:05

1.LinkedList
继承:抽象类AbstractSequentialList
实现:接口List、接口Cloneable、接口Serializable

2.LinkedList的初始化
两个构造函数:


先看看无参构造函数

注释说的是:构建一个空的list,那么new LinkedList()得到的是一个怎么样的实例呢?


通过断点,发现这几个属性:size=0,first=null,last=null,也说明了各自的作用,那么怎么实现的呢
先看看者几个属性的定义:

size:顾名思义,就是LinkedList的存储的元素的个数
first:注释为:指向第一个node的指针
last注释为:指向最后一个node的指针


内存大概示意图:


那么node是什么呢?可以看到first和last都是Node类型,来看看Node
此类定义在LinkedList类中,被private和static修饰,说明只能在
LinkedList类中访问,跟着LinkedList类一起初始化。


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


2.LinkedList的add()方法
那么这种双向链表的数据结构具体怎么实现呢?来看看add()方法

可以看到有五种添加数据的方法
先看第一个add(E)

源码如下:

很简单,调用linkLast(e)方法,看看此方法:

可能看起来不太容易懂,没关系,懂结果就行,看看执行add()以后的内存:


内存大概示意图:

debug看看:

first和last指向的是同一个Node实例。


此时多添加一些数据:

内存结构:

此时双向链表结构就很明显了。


然后再来看看LinkedList的第二个构造方法:LinkedList(Collection)
源码如下:

可以看到此构造方法很简单,调用的第一个构造方法进行的实例化,然后在调用方法addAll(Collection),addAll(Collection)下面讲解


来看看第二个add方法:add(int, E):此方法将元素存放在指定下标位置
前面说了linkedList的存储方式为双向链表结构,并不能跟数组一样通过下标直接存取数据,那么这里指定下标存放数据怎么实现的呢?看看源码:

如果是追加到末尾,那跟add(E)方法一样,调用linkLast(element)
如果不是,调用linkBefore(element, node(index))
第二个参数调用了node(index)方法,此方法的作用为获取index位置的Node元素,源码:

注释为:返回指定index下标的Node元素数据,如果index为0,那就是第一个Node,如果为size-1那就是最后一个Node


看看linkBefore(element, node(index));方法,源码如下:

可以看到通过prev和next的指针修改,表明新元素会放到index元素的前面,如果新元素放在了第一位,那么还要修改LinkedList的first指针,指向新元素。

相关推荐

最新更新

猜你喜欢