java LinkedList 源码分析（通俗易懂)
目录
一、前言
大家好，今天给大家带来的是LinkedList类的内容分享。对于单列集合List的三个最常用的实现类——ArrayList, Vector, LinkedList，在前面的小节中，我们已经分析过了ArrayList类和Vector类的源码。但对于List接口的第三大实现类LinkedList，由于其底层涉及了较多数据结构的知识，而本篇博文主要面向过渡阶段，因此up准备简单给大家过一下就好，不会讲太深，大家可放心食用，更多内容up准备在将来的数据结构专栏再深度讲解。
注意 : ① 代码中的注释也很重要； ② 不要眼高手低，自己跟着过一遍才能知道怎么用。 ③ 点击侧边栏目录或者文章开头的目录可以跳转。良工不示人以朴，所有文章都会适时改进。大家如果有什么问题，都可以在评论区一块儿交流，或者私信up。 感谢阅读！
二、LinkedList类简介
1.LinkedList是一种常见的线性表，每一个结点中都存放了下一个结点的地址。LinkedList类属于java.base模块，java.util包下，如下图所示 :
我们再来看看LinkedList 类的类图，如下所示 :
2.链表又分为单向链表和双向链表。一个单向链表包含两个值——当前结点的值和下一个结点的地址值；一个双向链表包含三个值——前一个结点的地址值，当前结点的值和下一个结点的地址值。
3.LinkedList底层实现了双向链表和双端队列的特点。
4.同ArrayList类似，可以向LinkedList集合中添加任意元素，包括null，并且元素可以重复。
5.同ArrayList一样，LinkedList也没有实现线程同步，因此线程不安全。
三、LinkedList类的底层实现
1.LinkedList的底层维护了一个双向链表。在IDEA的类图中，我们查看LinkedList类的字段可以发现，LinkedList类中维护了两个属性first和last，见名知意，它们分别指向双向链表的首结点和尾结点。我们也可以在源码中找到first 和 last，如下图所示 :
2.每个结点（Node对象）中又维护了prev，next，item，三个属性，其中通过prev指向前一个结点，通过next指向后一个结点，从而实现双向链表。
3.LinkedList中元素的添加和删除，在底层不是通过数组来完成的，而是通过链表来完成的，因此LinkedList相对来说效率更高。
PS :
以上内容涉及到了数据结构基础中关于链表的部分知识（比如什么是首结点和尾结点），当然，仅仅是涉及到一些基础的概念性的知识。
双向链表的示意图如下 :
这里up用java来模拟一个简单的双向链表，现在我们想创建三个璃月人对象——刻晴，甘雨，钟离，并且让它们形成如下的双向链表关系：
以Link_Simulation类为例，代码如下 :
package csdn.knowledge.api_tools.gather.list;
import java.util.LinkedList;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class Link_Simulation {
public static void main(String[] args) {
//演示 : 用java模拟一个简单的双向链表。
//创建璃月人对象
Node keqing = new Node("刻晴"); //第一个结点
Node ganyu = new Node("甘雨"); //第二个结点
Node zhongli = new Node("钟离"); //第三个结点
//完成双向链表
//从左往右相连接
keqing.next = ganyu;
ganyu.next = zhongli;
//从右往左相连接
zhongli.pre = ganyu;
ganyu.pre = keqing;
//令first指向第一个结点，令last指向最后一个结点
Node first = keqing;
Node last = zhongli;
//遍历链表（头 ——> 尾）
while (true) {
if (first == null) {
break;
}
System.out.println(first); //输出当前对象的信息
first = first.next; //更改指向
}
System.out.println("=====================================");
//遍历链表（尾 ——> 头）
while (true) {
if (last == null) {
break;
}
System.out.println(last); //输出当前对象的信息
last = last.pre; //更改指向
}
}
}
class Node {
public Object item; //存放当前结点的数据。
public Node pre; //指向前一个结点
public Node next; //指向后一个结点
public Node(Object name) {
this.item = name;
}
public String toString() {
return "Node 's name = " + item;
}
}
运行结果 :
四、LinkedList VS ArrayList
1.如何抉择 :
①增删操作多，优先选择LinkedList；改查操作多，优先选择ArrayList。
②实际开发中，往往对集合的改查操作比较多，因此ArrayList一般用的较多。
③有时候一个项目的不同模块会使用不同的选择。（根据业务需求来实际选择）
④ArrayList与LinkedList 线程均不安全，建议单线程情况下使用。
2.比较图 :
五、LinkedList类的源码解读
1.add方法解读 :
〇准备工作 。
up以LinkedList_Demo1为演示类，代码如下 :（在创建对象那行代码设置断点）
package csdn.knowledge.api_tools.gather.list;
import java.util.LinkedList;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class LinkedList_Demo1 {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(11);
linkedList.add(141);
System.out.println(linkedList);
}
}
①跳入无参构造。
如下图所示 :
可以看到，LinkedList类的无参构造其实是什么也没有做，我们跳出无参构造。无参构造器执行完毕后，我们可以看到LinkedList对象已经初始化完毕，如下图所示 :
注意看，此时 first 和 last 均为null类型。所以，链表此时是这样一个效果 :
②跳入add方法。
如下图所示 :
因为我们要向链表中添加的元素为int类型，所以第一次跳入add方法是一个自动装箱的过程，我们不用管他，直接跳出。
再次跳入add方法，如下图所示 :
③跳入linkList方法。
形参列表的"E e"表示我们当前要添加的元素，所以此时e = 11。add方法中调用了linkLast方法，不用想也能猜到，这个linkLast方法里面完成了添加元素的操作，我们继续追进去看看，如下图所示 :
我们一步一步来看——
首先, Node是“结点”的意思。
其次，还记得我们上面提到说——first 和 last此时均为null。所以，linkLast方法内，第一步是定义了一个Node类型的常指针l，并为其赋初值为last（即null）；
接着，又定义了一个Node类型的常量newNode，见名知意，"newNode"就是我们要添加的新结点。那么，为newNode初始化的这个带参构造是怎么执行的呢？这三个实参分别是干嘛的？别急，我们这就通过Ctrl + b/B快捷键，追到其源码中看看，如下图所示 :
一看源码我们就明白了，这不就是上文中我们提到的——双向链表的三个值吗？所以，对应此处的三个实参，l就是prev，此时为null；e就是已经装箱好的11；null就是next的值。因此，newNode引用此时指向的就是一个前后均为空，值为11的新结点。并且，之后又令last指向了该新结点。
继续向下执行，是一个if-else的复合条件语句。判断条件"l == null"显然满足，令first也指向了该新结点；之后，又令size自增1（size表示当前链表中元素的个数），modCount也自增1（修改次数)。
④增加第一个元素成功。
好的，linkList方法执行完毕后，此时链表就长下面这样子 :
接下来，我们逐层跳出，直到演示类中。我们可以看到此时链表的状态，如下图所示 :
可以看到，first 和 last 都指向了同一个结点，并且该结点中prev和next均为null。
⑤向链表中添加第二个元素。
前面几个步骤都一样，我们就不再赘述了，直接从linkList方法开始说起，如下 :
还是一步一步来看——
首先，令Node类型的常指针l 指向了last所指向的结点(即我们刚刚添加的第一个结点）。
其次，第二个新结点进行初始化工作。注意，第一个实参l 代表的是新结点的prev，而l 此时又指向了第一个结点，因此，这一步实现了——第二个新节点的prev指向了第一个结点。
接着，又令last指向了第二个新结点（此时first仍指向第一个结点）。
然后，就是if-else的判断语句了，因为l 已经指向了第一个结点，不为空，所以执行ele中的语句，令第一个结点的next指向了第二个新结点。
最后，就是size和modCount的自增。
所以，第二次linkList方法执行完毕后，链表就应该长下面这个样子 :
2.remove方法解读 :
〇准备工作 。
up以LinkedList_Demo2为演示类，代码如下 :（在remove方法那行代码设置断点）
package csdn.knowledge.api_tools.gather.list;
import java.util.LinkedList;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class LinkedList_Demo2 {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(11);
linkedList.add(141);
linkedList.add(5);
System.out.println("添加三个元素后，当前链表 = " + linkedList);
linkedList.remove();
System.out.println("删除第一个元素后，当前链表 = " + linkedList);
}
}
运行结果 :
如代码所示，我们事先在链表中加入三个元素：11，141，5。则在删除元素之前，我们的双向链表应该长下面这样子 :
①关于LinkedList类的remove方法。
通过查看API文档，我们可得知LinkedList类的remove有三个重载方法，如下图所示 :
其中，形参列表为空的remove() 方法，其内部默认调用的是removeFrist方法，即默认删去链表中的第一个元素；形参列表需要传入一个索引的remove(int index) 方法，可以删去链表中指定索引位置的元素，较复杂；形参列表需要传入一个Object类型的值的remove(Object o)方法，是删去链表中与该值匹配的第一个元素。
up就以最简单的remove() 方法，通过Debug，来给大家分析一下。
②跳入remove() 方法。
我们直接在remove方法的调用行设置断点跳过去，并跳入remove方法，如下图所示 :
③跳入removeFirst() 方法。
可以看到，果然是调用了removeFirst() 方法，那它底层到底是如何把链表的第一个元素给干掉的？我们继续往里面追，如下图所示 :
removeFirst方法内部还是比较简洁的。首先，它令一个Node类型的常指针f 指向了首结点（即第一个存放有效数据的结点），然后判断首结点是否为空。由于我们一开始就在链表中添加了3个元素，所以此处f 肯定不为空。因此，if语句中的内容会跳过，return一个unlinkFirst() 方法的返回值。
④跳入unlinkFirst() 方法。
可以看到，removeFirst方法内部并没有执行删除操作的代码。我们继续追入unlinkFirst方法，如下图所示 :
哎呀我趣，看这一大串，显然删除操作是在这里面完成的。
老规矩，我们一步一步来看——
首先，第一条语句不用看。因为这只是在函数最后return的删除掉的元素的值，与删除过程本身无关。
其次，第二条语句，它令一个Node类型的常指针next指向了第一个结点的next属性所指向的值，即指向了第二个结点，如下图所示 :
接着，又依次置空了第一个结点的item和next，并且令first 指向了第二个结点，如下图所示 :
继续， 由于next现在指向的是第二个结点，不为空，所以接下里要进入else语句中。else语句中，令第二个结点的prev为null，如下图所示 :
⑤第一个元素被除去。
至此，第一个元素已经被干掉了。回忆一下案发现场，jvm先是破掉了第一个结点的"盾牌"（即first）；接着又切断了第一个结点的"逃跑路线"(即next），最后又斩断了第一个结点的"后援"（即第二个结点的prev）。那第一个结点手无寸铁，又成了单兵作战，留给它的命运只能是被gc垃圾回收器除去，哎，可悲。（bushi）
六、总结
🆗，以上就是关于LinkedList源码分析的全部内容了。由于LinkedList作为链表，已经属于数据结构的内容了。因此本篇博文中up也是尽量"避重就轻"，已不至于过于晦涩。当然，对于有些在学C语言的时候接触过链表的小伙伴儿们来说，应该还是没什么难度的。好的，至此我们的单列集合之List接口就算是全部搞定了。下一小节我们将开始进入set集合的内容，大家不见不散😆。感谢阅读！
System.out.println("END----------------------------------------------------------");
- 点赞
- 收藏
- 关注作者
评论（0）