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

发布于:2025-03-15 ⋅ 阅读:(18) ⋅ 点赞:(0)

参考视频:韩顺平Java集合

特点

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

LinkedList 底层结构

image.png|425

  • LinkedList 底层维护了一个双向链表
  • LinkedList 中维护了两个属性 firstlast 分别指向首节点和尾节点。
  • 每个节点(Node 对象)里面有维护了 prevnextitem 三个属性,其中通过 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 的类是这样设计的:
image.png|425
与前面我们的简单实现相比,这里的 Node 中存放数据的 item 是使用泛型来约束的,这样在使用时可以定义其存储数据的类型。更加严谨一些。

构造器创建 LinkedList

  • 调用空参构造器创建了一个 size=0 的 linkedList。
  • 此时头和尾都为空,modCount 为修改次数
    image.png

第一次添加元素(节点 1)

  • 进入 add() 方法,将所添加的数据传递给 linkedLast()
    image.png|75
  • 注意此时链表为空,所以头节点和尾节点都为 null
    image.png
  • LinkedLast() 作用是将所添加的元素插在最后:
    image.png|450
  • 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,添加完成。
    image.png
  • 可以看到数据已经放在了链表中,并且头节点和尾节点都指向该节点 (@861)
    image.png|425

第二次添加元素(节点 2)

  • 进入 add() 方法,将所添加的数据传递给 linkedLast() 中:
    image.png
  • LinkedLast() 作用是将所添加的元素插在最后:
    image.png|475
  • 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,添加完成。
    image.png
  • 可以看到数据已经放在了链表中,并且头节点指向节点 1(@861),尾节点指向节点 2 (@867)
    image.png|400

删除第一个节点(无参,默认删除第一个)

  • 进入 remove() 方法中,可以发现其中调用了 removeFirst() 方法:
    image.png
  • removeFirst() 的作用就是删除链表的第一个元素。
  • var1=当前链表的头结点==(节点 1)==
  • 判断头结点是否为空,也就是判断链表是否为空
  • 为空则抛出异常;不为空则调用 unlinkFirst() 方法,将头节点传入:
    image.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)
    image.png|500
  • 可以看到第一个节点已被删除。
    image.png|425

删除索引为 2 的节点

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

  • 进入 remove() 方法,先进入 checkElementIndex() 方法检查一下索引是否合法
    image.png|425
  • checkElementIndex() :检查索引是否合法 (目前链表 size=8,索引2 合法)
    image.pngimage.png|500
  • 回到 remove() 中,调用 unlink(node) 方法,其作用是删除一个节点 node。
    image.png|500
  • 但由于我们传入的是索引,而不是节点本身,所以需要调用 node (index) 方法来查找并返回节点。
  • 观察 node 方法:它的查找方式是检查要查找的节点索引在前半部分还是后半部分。(本例中我们查找索引 2,在前半部分,所以从头开始查找)
    • 如果是前半部分则从头开始查找;
    • 如果是后半部分,则从尾开始查找。
    • var2 是遍历用的节点
    • var3 遍历用的索引
      image.png|475
  • 最后将找到的节点返回给 unlink(node) 方法中。
    image.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)
    image.png|425
  • 至此,删除下标为 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));  
}