集合—LinkedList底层结构

本次博客带领大家学习集合中的LinkedList底层结构。

LinkedList的全面说明

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

LinkedList的底层操作机制

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

• 简单了解双向链表的用法：

public class LinkedList01 {
    public static void main(String[] args) {
        // 模拟一个简单的双向链表
        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node ld = new Node("领导");

        //连接三个节点，形成双向链表
        //jack ->tom ->ld
        jack.next = tom;
        tom.next = ld;
        //ld ->tom ->jack
        ld.pre =tom;
        tom.pre = jack;

        Node first = jack;//让first引用指向jack，就是双向链表的头节点
        Node last = ld;//让last引用指向ld，就是双向链表的尾节点

        //演示：从头到尾进行遍历
        System.out.println("=======从头到尾进行遍历===");
        while (true){
            if(first == null){
                break;
            }
            //输出first 信息
            System.out.println(first);
            first = first.next;
        }

        //演示：从尾到头的遍历
        System.out.println("=======从尾到头的遍历===");
        while (true){
            if(last == null){
                break;
            }
            //输出first 信息
            System.out.println(last);
            last = last.pre;
        }
        //演示链表的添加对象/数据
        //要求，是在tom---领导直接插入一个对象 smith
        //1.先创建一个Node 节点，name 就是 smith
        Node smith = new Node("smith");
        //下面就把Smith加入到链表中
        smith.pre = tom;
        smith.next = ld;
        ld.pre = smith;
        tom.next = smith;

        first = jack;

        System.out.println("=======从头到尾进行遍历===");
        while (true){
            if(first == null){
                break;
            }
            //输出first 信息
            System.out.println(first);
            first = first.next;
        }

        last = ld;
        System.out.println("=======从尾到头的遍历===");
        while (true){
            if(last == null){
                break;
            }
            //输出first 信息
            System.out.println(last);
            last = last.pre;
        }
    }
}

//定义一个Node类，Node对象，表示双向链表的一个节点
class Node{
    public Object item;//真正存放数据
    public Node next; //指向后一个节点
    public Node pre; //指向前一个节点
    public Node(Object name){
        this.item = name;
    }
    public String toString(){
        return "Node name=" +item;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

LinkedList的源码分析

• LinkedList 添加的源码分析

1. LinkedList linkedList = new LinkedList();
 public LinkedList() {}
2. 这时 linkedList 的属性 first = null ,last = null
3. 执行 添加
    public boolean add(E e) {
         linkLast(e);
         return true;
     }
4. 将新的节点，加入到双向链表的最后
    void linkLast(E e) {
         final Node<E> l = last;
         final Node<E> newNode = new Node<>(l, e, null);
         last = newNode;
         if (l == null)
             first = newNode;
         else
             l.next = newNode;
         size++;
         modCount++;
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• LinkedList 删除的源码分析

linkedList.remove(); 这里默认删除的是第一个节点
1.执行
    public E remove() {
        return removeFirst();
    }
2.执行
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
 3.执行 unlinkFirst ，将 f 指向的双向链表的第一个节点拿掉
     private E unlinkFirst(Node<E> f) {
            // assert f == first && f != null;
            final E element = f.item;
            final Node<E> next = f.next;
            f.item = null;
            f.next = null; // help GC
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• 案例代码：

public class LinkedListCRUD {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println("linkedList="+linkedList);

        //演示一个删除节点的
        linkedList.remove();//这里默认删除的是第一个节点

        System.out.println("linkedList="+linkedList);

        //修改某个节点对象
        linkedList.set(1,999);
        System.out.println("linkedList="+linkedList);

        //得到某个节点
        //get(1)是得到双向链表的第二个对象
        Object o = linkedList.get(1);
        System.out.println(o);

        //因为LinkedList 是 实现了List接口，遍历方式
        System.out.println("====LinkedList遍历迭代器=====");
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println("next="+next);
        }
        System.out.println("====LinkedList遍历迭代器增强for=====");
        for (Object o1 :linkedList) {
            System.out.println("o1="+o1);
        }

        System.out.println("====LinkedList遍历迭代器普通for=====");
        for (int i = 0; i <linkedList.size() ; i++) {
            System.out.println(linkedList.get(i));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

ArrayList和LinkedList的比较

如何选择ArrayList和LinkedList：

1. 如果我们改查的操作多，选择ArrayList。
2. 如果我们增删的操作多，选择LinkedList。
3. 一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList。
4. 在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList，另一个模块是LinkedList，也就是说，要根据业务来选择。