java LinkedList 源码分析（通俗易懂)

目录

一、前言

二、LinkedList类简介

三、LinkedList类的底层实现

四、LinkedList类的源码解读

        1.add方法解读 : 

                〇准备工作 。

                ①跳入无参构造。

                ②跳入add方法。

                ③跳入linkList方法。

                ④增加第一个元素成功。

                ⑤向链表中添加第二个元素。

        2.remove方法解读 : 

                〇准备工作 。

                ①关于LinkedList类的remove方法。                                

                ②跳入remove() 方法。

                ③跳入removeFirst() 方法。

                ④跳入unlinkFirst() 方法。

                ⑤第一个元素被除去。                

五、总结

---

一、前言

        大家好，今天给大家带来的是LinkedList类的内容分享。对于单列集合List的三个最常用的实现类——ArrayList, Vector, LinkedList，在前面的小节中，我们已经分析过了ArrayList类和Vector类的源码。但对于List接口的第三大实现类LinkedList，由于其底层涉及了较多数据结构的知识，而本篇博文属于《java基础》专栏，因此主要面向基础阶段，因此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，见名知意，它们分别指向双向链表的首结点和尾结点。

        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;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类的源码解读

        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源码分析的全部内容了。由于《java基础》是面向基础阶段系列博文，而LinkedList作为链表，已经属于数据结构的内容了。因此本篇博文中up也是尽量"避重就轻"，已不至于过于晦涩。当然，对于有些在学C语言的时候接触过链表的小伙伴儿们来说，应该还是没什么难度的。好的，至此我们的单列集合之List接口就算是全部搞定了。下一小节我们将开始进入set集合的内容，大家不见不散😆。感谢阅读！

        System.out.println("END----------------------------------------------------------");