技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

LinkedList底层结构和源码分析JDK1.8

 收录于 未分类
   约 3225 字   预计阅读 7 分钟 
https://bing.ee123.net/img/rand?artid=146259166

LinkedList底层结构和源码分析（JDK1.8）

参考视频：

特点

  • LinkedList 底层实现了 双向链表 和 双端队列 的特点。
  • 可以添加任意元素（元素可以重复），包括 null。
  • 线程不安全，没有实现同步。

LinkedList 底层结构

https://i-blog.csdnimg.cn/img_convert/2e1f5664943eff131fc5e13be3578b5f.png

  • LinkedList 底层维护了一个双向链表
  • LinkedList 中维护了两个属性 first 和 last 分别指向首节点和尾节点。
  • 每个节点（Node 对象）里面有维护了 prev 、 next 、 item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个节点。最终实现双向链表。
  • 所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

模拟一个简单的双向链表

  • 定义一个Node类，表示一个双向链表的节点：

    public class Node {  
    public Object item;  
    public Node prev;//指向后一个节点  
    public Node next;//指向后一个节点  

    public Node(Object name){  
        this.item = name;  
    }  

    @Override  
    public String toString() {  
        return "Node name="+item;  
    }  
}

  • 创建几个节点，并为其建立链表链接：

    //模拟一个简单的双向链表  
@Test  
public void test1(){  
    LinkedList list = new LinkedList();  
    Node node1 = new Node("Node1");  
    Node node2 = new Node("Node2");  
    Node node3 = new Node("Node3");  

    //链接三个节点，形成双向链表  
    //1->2->3  
    node1.next = node2;  
    node2.next = node3;  
    //3->2->1  
    node3.prev = node2;  
    node2.prev = node1;  

    //头节点  
    Node first = node1;  
    //尾节点  
    Node last = node3;
}

  • 简单的应用：从头到尾遍历、从尾到头遍历：

    System.out.println("=======从头到尾进行遍历======");  
//演示：从头到尾进行遍历  
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.prev;  
}

  • 简单的应用：在 node1 和 node2 之间插入 node 1.5

    Node node15 = new Node("node1.5");  
node15.prev = node1;  
node15.next = node2;  
node1.next = node15;  
node2.prev = node15;

  • 遍历一下验证插入结果

    • （但是注意，这里所展示的遍历的例子是依靠 first 和 last 指针的移动来实现的，所以如果我们要遍历一遍插入新元素后的链表，则需要将 first 和 last 进行一个重新指向。）
    //头和尾要重新进行指向  
first = node1;  
last = node3;  

System.out.println("=======从头到尾进行遍历======");  
//演示：从头到尾进行遍历  
while(true){  
    if(first == null)break;  
    System.out.println(first);  
    first = first.next;//头节点移动至下一个  
}

LinkedList 增删改查——源码示例

  • 源码：

    • 构造器创建 linkedList 的细节和流程
    • 第一次添加元素（节点 1）
    • 第二次添加元素（节点 2）
    • 删除第一个节点
    • 删除下标为 2 的节点
    @Test  
public void test2(){  
    LinkedList list = new LinkedList();  
    list.add(1);  
	list.add(2);
    System.out.println("linkedList = "+list);  
}

在 JDK 1.8 中，Node 的类是这样设计的：

https://i-blog.csdnimg.cn/img_convert/3680df4aa69edf26adb59b92a37e739c.png

与前面我们的简单实现相比，这里的 Node 中存放数据的 item 是使用泛型来约束的，这样在使用时可以定义其存储数据的类型。更加严谨一些。

构造器创建 LinkedList

  • 调用空参构造器创建了一个 size=0 的 linkedList。

  • 此时头和尾都为空， modCount 为修改次数

    https://i-blog.csdnimg.cn/img_convert/3a14f02b86ef8bbab21070144bf25911.png

第一次添加元素（节点 1）

  • 进入 add() 方法，将所添加的数据传递给 linkedLast() 中

    https://i-blog.csdnimg.cn/img_convert/c1603d49386b73f06e3d293283bbf28c.png

  • 注意此时链表为空，所以头节点和尾节点都为 null

    https://i-blog.csdnimg.cn/img_convert/cf921c7da436bbb9ed22977956e7db66.png

  • LinkedLast() 作用是将所添加的元素插在最后：

    https://i-blog.csdnimg.cn/img_convert/053c614823836ef071944a62290fd66f.png

  • var2=链表当前最后的元素。 （因为此时链表为空，所以 var2=null）

  • 新建一个 Node，将其中的 item 值设置为 var1，并设置前节点（var2）和后节点（null）。这就是 var3。 （此时 var2【null】➡var3【item=var1】➡null）

  • 让当前的尾节点指向 var3。 (此时last➡var3)

  • 判断前一个节点（ var2） 是否为空？

    • 如果 var2=null，也就代表原本是一个空链表，那么我们就需要将头结点指向新添加的节点 var3。 （此时first➡var3⬅️last）
    • 如果 var2 不为空，就将 var2 的下一个节点指向 var3。

  • 链表长度+1 （此时size=1）

  • 修改次数+1 （此时monCount=1）

  • 至此，添加操作完成，回到添加的主逻辑：返回 true，添加完成。

    https://i-blog.csdnimg.cn/img_convert/9fae989cbdc2e4aad8218071c4b58574.png

  • 可以看到数据已经放在了链表中，并且头节点和尾节点都指向该节点 （@861） 。

    https://i-blog.csdnimg.cn/img_convert/521465e6a77dd2782c8267e737f6e7a2.png

第二次添加元素（节点 2）

  • 进入 add() 方法，将所添加的数据传递给 linkedLast() 中：

    https://i-blog.csdnimg.cn/img_convert/a29e5dc6d78db70dd7027de4bc1f9660.png

  • LinkedLast() 作用是将所添加的元素插在最后：

    https://i-blog.csdnimg.cn/img_convert/abec1730da4eae57535ac9ae72797e3b.png

  • var2=链表当前最后的元素。 （此时 var2=节点 1）

  • 新建一个 Node，将其中的 item 值设置为 var1，并设置前节点（var2）和后节点（null）。这就是 var3。 （此时 var2【节点 1】➡var3【item=var1】➡null）

  • 让当前的尾节点指向 var3。 (此时last➡var3)

  • 判断前一个节点（ var2） 是否为空？

    • 如果 var2=null，也就代表原本是一个空链表，那么我们就需要将头结点指向新添加的节点 var3。
    • 如果 var2 不为空，就将 var2 的下一个节点指向 var3。 （此时 var2【节点 1】➡var3）

  • 链表长度+1 （此时size=2）

  • 修改次数+1 （此时monCount=2）

  • 至此，添加操作完成，回到添加的主逻辑：返回 true，添加完成。

    https://i-blog.csdnimg.cn/img_convert/d3317867da5a32e7af544af98728ebaa.png

  • 可以看到数据已经放在了链表中，并且头节点指向节点 1（@861），尾节点指向节点 2 （@867） 。

    https://i-blog.csdnimg.cn/img_convert/d2a3b53409a18980b23f8e2ae6531e2a.png

删除第一个节点（无参，默认删除第一个）

  • 进入 remove() 方法中，可以发现其中调用了 removeFirst() 方法：

    https://i-blog.csdnimg.cn/img_convert/3017103b4bbfb7ba15d3cb231772ea7e.png

  • removeFirst() 的作用就是删除链表的第一个元素。

  • var1=当前链表的头结点==（节点 1）==

  • 判断头结点是否为空，也就是判断链表是否为空

  • 为空则抛出异常；不为空则调用 unlinkFirst() 方法，将头节点传入：

    https://i-blog.csdnimg.cn/img_convert/726430498ace1e9672af96bc35d7e7eb.png

  • unlinkFirst() 的作用是删除链表的第一个节点：

  • var2=头节点中的数据 （本例中是 “1”）

  • var3=头节点的下一个节点 （本例中是节点 2）

  • 将头节点的数据清空

  • 将头节点的 next 置为 null；

  • 将头节点设置为下一个节点（var3）

  • 判断下一个节点是否为空（也就是判断该链表是否只有 var1 这一个节点）

    • 为空，则代表尾指针 last 也在 var1 这个要删除的节点上，所以需要将 last 也置为 null；
    • 不为空，则表示后续还有节点，把后节点的 prev 设置为 null。 （本例）

  • 链表的长度-1 （size=9-1=8）

  • 修改次数+1 （modCount=9+1=10）

    https://i-blog.csdnimg.cn/img_convert/9348afa8491eaf4d9943b8c40239a661.png

  • 可以看到第一个节点已被删除。

    https://i-blog.csdnimg.cn/img_convert/ae01019823d3a98400dd595e31d0cf65.png

删除索引为 2 的节点

此时链表中的元素有【2，3，4，5，6，7，8，9】，我们要删除的是 “4”。

  • 进入 remove() 方法，先进入 checkElementIndex() 方法检查一下索引是否合法

    https://i-blog.csdnimg.cn/img_convert/3fc7c509af93b56f37b51006dea9913c.png

  • checkElementIndex() ：检查索引是否合法 （目前链表 size=8，索引2 合法）

    https://i-blog.csdnimg.cn/img_convert/1411ba508e4125543a8ba956ac1a1731.png https://i-blog.csdnimg.cn/img_convert/d96b5f90b1e79f9617de652f26e13960.png

  • 回到 remove() 中，调用 unlink(node) 方法，其作用是删除一个节点 node。

    https://i-blog.csdnimg.cn/img_convert/6cf078634721415dfc85f4b0e451825d.png

  • 但由于我们传入的是索引，而不是节点本身，所以需要调用 node (index) 方法来查找并返回节点。

  • 观察 node 方法：它的查找方式是检查要查找的节点索引在前半部分还是后半部分。 （本例中我们查找索引 2，在前半部分，所以从头开始查找）

    • 如果是前半部分则从头开始查找；

    • 如果是后半部分，则从尾开始查找。

    • var2 是遍历用的节点

    • var3 遍历用的索引

      https://i-blog.csdnimg.cn/img_convert/4d6e444884fa219eab17a26c1bdc0da8.png

  • 最后将找到的节点返回给 unlink(node) 方法中。

    https://i-blog.csdnimg.cn/img_convert/7646b192d33c6cc62f6f8d06dc679819.png

  • 找到的节点作为参数 var1 传入该方法。

  • var2=该节点的数据 （本例中是 “4”）

  • var3=该节点的后节点

  • var4=该节点的前节点

  • 判断前节点（var4）是否为 null

    • 如果 var4 为 null，则表示该节点为头节点，需要将 first 指针指向其下一个节点（var3）；
    • 如果不为 null，说明其前面还有节点，就要将前节点（var4）的 next 指向其后节点（var3），并且将该节点的 prev 解除。 （本例）

  • 判断后节点（var3）是否为 null

    • 如果 var3 为 null，则表示该节点为尾节点，需要将 last 指针指向其上一个节点（var3）；
    • 如果不为 null，说明其后面还有节点，就要将后节点（var3）的 prev 指向其前节点（var4），并且将该节点的 next 解除。 （本例）

  • 这样一来就将要删除的元素 var1 彻底与链表解除了关系，成为了一个孤立的节点。最后要做的就是将其中的数据（item）也进行清空

  • 链表长度-1 （size=8-1=7）

  • 修改次数+1 （modCount=10+1=11）

    https://i-blog.csdnimg.cn/img_convert/ff7508229af0cf18db022bf002d63123.png

  • 至此，删除下标为 2 的节点完成。

改：set (int, Object) 和查：get(i) 的源码都比较简单，可以自己分析一下。

LinkedList 遍历

由于 LinkedList 实现了 List 接口，而 List 接口可以使用三种方式遍历：迭代器、增强 for 循环、普通 for 循环。所以 LinkedList 也是支持的。

//增强for遍历  
System.out.println("======增强遍历");  
for (Object o :list) {  
    System.out.println(o);  
}  
  
//迭代器遍历  
System.out.println("======迭代器遍历");  
Iterator iterator = list.iterator();  
while(iterator.hasNext()){  
    Object next = iterator.next();  
    System.out.println(next);  
}  
  
//普通for遍历  
System.out.println("======普通for遍历");  
for (int i = 0; i < list.size(); i++) {  
    System.out.println(list.get(i));  
}
更新于 2025-03-14
 笔记, 学习, Java
返回 | 主页