Java教程

集合源码分析03——LinkedList源码分析

本文主要是介绍集合源码分析03——LinkedList源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

LinkedList源码分析

 

 

  

 

  • ArrayList和LinkedList比较

 

 ArrayList改查效率高是因为数组可以通过索引直接定位,LinkedList则需要从头遍历

另外这两个都是线程不安全的,在单线程的时候考虑使用

 

 

 

  •  模拟双向链表

为了便于理解这里我们先模拟一个简单的双向链表:

package collection.list.linkedlist;

/**
 * @author 紫英
 * @version 1.0
 * @discription 模拟一个双向链表
 */
public class LinkedList01 {
    public static void main(String[] args) {
        //先创建三个节点
        Node node01 = new Node("111");
        Node node02 = new Node("222");
        Node node03 = new Node("333");
        //将三个节点连接起来形成双向链表
        // node01 -> node02 -> ndoe03
        node01.next = node02;
        node02.next = node03;
        // node01 <- node02 <- ndoe03
        node02.pre = node01;
        node03.pre = node02;
        //头节点指向第一个
        Node first = node01;
        //尾节点指向最后一个
        Node last = node03;

        //正向遍历双向链表
        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.pre;
        }

        //在node01和node02之间添加一个新的node
        // 1.先创建一个新节点
        Node node = new Node("666");
        // 2.将其加入到双向链表中
        node01.next = node;
        node.next = node02;

        node.pre = node01;
        node02.pre = node;

        //重置first后再进行一次正向遍历
        first = node01;
        //添加数据后正向遍历双向链表
        System.out.println("===添加数据后正向遍历双向链表===");
        while (true) {
            if (first == null) {
                break;
            }
            System.out.println(first);
            first = first.next;
        }

        //重置last后再进行一次逆向遍历
        last = node03;
        //添加数据后逆向遍历双向链表
        System.out.println("===添加数据后逆向遍历双向链表===");
        while (true) {
            if (last == null) {
                break;
            }
            System.out.println(last);
            last = last.pre;
        }
    }
}

class Node {
    public Object item;//真正存放的数据
    public Node next;//指向下一个节点
    public Node pre;//指向前一个节点
    //构造器
    public Node(Object item) {
        this.item = item;
    }

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

结果如下:

 

 

 

  •  源码解读(索引依旧是从0开始)

  •  增加节点

 

public class LinkedListCRUD {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
    }
}

  1.构造器语句

此时 first=null,last=null

 

 

   2.add()方法

 

  3.linkLast(e)  将新节点加入到双向链表最后

 

 

 

 (1)先将last赋值给一个Node型的数据l,也就是说此时的l是指向null的(因为last指向null)

 (2)创建一个新的节点

 (3)将last指向新节点,此时的新节点前后都为null

 (4)判断 if (l == null) 根据(1)此时的l为null,所以将first也指向新节点

 

   4.加入第二个节点

 

 

(1)此时的l还是指向last也就是第一个节点

(2)创建一个新结点,并将新节点的pre指向l,也就是说此时新节点的pre指向了第一个节点

(3)将last指向新节点  

(4)判断 if (l == null) 根据(1)此时的l是指向第一个节点的不为null,所以执行l.next = newNode,将第一个节点的next指向新节点

(5)此时的first还是指向第一个节点而last则指向新节点

 

 

  • 删除节点
public class LinkedListCRUD {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.remove();//默认删除第一个

    }
}

 

 1.进去之后执行了removeFirst()方法

 

  

2.removeFirst()  先将f指向双向链表的first,并判断一下是否删除的是空链表

 

 

 

  3.unlinkFirst(f)

 

 

 (1)先将first中的item赋给element(最后作为返回值返回)

 (2)创建一个next指向f的下一个节点

 (3)将f中的内容置空

 (4)将f.next的指向置空(可以帮助GC垃圾回收机制判定为垃圾)

 (5)将first指向next,也就是指向了第二个节点

 (6)判断 if (next == null),这里next指向的是第二个节点并不为null,所以执行 next.prev = null,将 next.prev置空

 (7)此时之前的第一个节点变成孤零零的一个,会被GC判定为垃圾回收

 

  • 修改、查找节点

 

 

 

  • 链表遍历三种防守

 

 

这篇关于集合源码分析03——LinkedList源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!