LinkedList 笔记整理

发表于 | 分类于 |

LinkedList

 实现了List接口，底层基于双向链表结构，数据量较大时随机访问数据时效率很低，但由于时链表结构；删除、插入数据效率很高。与ArrayList特性刚好相反。开发过程中对于不同的业务场景应该选择合适的实现方法。

链表结构

 链表结构常用的有三类：单向链表、双向链表、循环链表(单向循环，双向循环)。区别于数组结构，虽然同为线性数据结构，数组结构物理存储与逻辑存储上都呈线性关系；而链表只是在逻辑上呈线性关系。
单向链表结构图(自己画的，大致意思>.<)：
mfCF3T.png

1.数据Item + Next 指针(持有了下一个数据Item的引用，区别于C语言中指针)
2.从链头到链尾，链尾的Next指向Null
3.与双向链表不同，单链表只能头依次遍历，也说明了，查询效率低的特点

双向链表结构(图片来自网络，侵删)：
mfCiCV.jpg

1.与单向链表不同双向链表中多了一个Prev指针，即数据Item + Next + Prev，Next指向向一个数据Item，而Prev指向前一个数据。Head数据的Prev指向Null，而链尾的Next同样指向Null。
2双向链表的遍历是双向的，LinkedList底层使用了双向链表，当查找对应Index下的数据Item时，会判断Index处于链表的前半段还是后半段(index >> 1)，从而选择遍历方向。

单向循环链表(图片来自网络，侵删)：
mfCC40.jpg

1.单向循环链表没有链头与链尾的区分，相当于链尾的Next指针指向了Head。
2.因为是闭环的，没有单链表那样有链头与链尾的严格区分，每一个Item都可以充当链头与链尾。

LinkedList 继承关系(图片来自网络，不知道具体作者，侵删)：

mf9zHs.jpg

LinkedList的底层实现，已经由原来的 循环双向链表 改为 双向链表 (具体是从1.6之后还是1.7之后，没有具体去查看)。

LinkedList 结构与常量

 JDK1.8中的源码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //元素的个数
    transient int size = 0;
    //头部指针(持有引用，不同于C语言中指针概念)
    transient Node<E> first;
    //尾部指针
    transient Node<E> last;

    //构造函数
    public LinkedList() {
       }
}

 既然LinkedList是基于双向链表实现的，就不得不提到，源码中定义元素的内部类：

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
private static class Node<E> {
        E item;//元素本身
        Node<E> next;//后继指针，持有后一个Item的引用
        Node<E> prev;//前驱指针，持有前一个Item的引用

        //可以看出Node包含了前后元素的信息，这是实现双向链表的重要组成
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
```  

#### 增加元素操作
```java
public boolean add(E e) {
  //普通增加元素，直接添加到链表的尾部
       linkLast(e);
       return true;
   }

   /**
    * Links e as last element.
    */
   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.因为增加的元素是到链表的尾部，那么这个元素作为最后一个元素 Next必然指向Null
final Node<E> newNode = new Node<>(l, e, null);

2.判断是否为空链表，如果是，则新增的这个元素变为头部，如果不是，则原先的last后继指针Next指向这个元素Item，Item的Next指向空。代码中很容易理解

指定Index插入元素：

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
/**
  * Inserts the specified element at the specified position in this list.
  * Shifts the element currently at that position (if any) and any
  * subsequent elements to the right (adds one to their indices).
  */
//将指定的元素插入此列表中的指定位置
//将当前位置（如果有）和任何位置的元素移位
//右侧的后续元素（在其索引中增加一个）(源码中解释)
public void add(int index, E element) {
    //检查是否越界
    checkPositionIndex(index);

    //判断要插入的位置是否恰好为链表的尾部(index == size)
    //如果是，则相(add())方法
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

private void checkPositionIndex(int index) {
    //检查越界的方法，抛出异常
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    //很简单的判断方法，写法值得借鉴
    return index >= 0 && index <= size;
}

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    //借助了pred作为过渡，将对应index的元素(非空)的前驱暂存
    //结合Node的实现方法可以看出，被插入的Item的Next指向了succ，而Item的前驱指向了pred(也即succ的前驱)
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    //pred为空，即succ的前驱指向为空，则succ为链头节点(first)
    if (pred == null)
    //判断插入的位置是不是链头
        first = newNode;
    else
    //原本succ前驱指向的数据Item的后继Next指向新插入的Item(newNode)(有点绕)，至此新的联系就建立起来了
        pred.next = newNode;
        //size自增，插入完成
    size++;
    modCount++;
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    //双向链表可以从双向遍历，判断了index处于整个链表的位置(前半部、后半部)，效率上考虑
    //从而决定遍历的方向(遍历所有元素，效率较低0(N))
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

总结：

1.添加元素时(非空)，直接添加到链表的尾部，修改原来链尾元素的后继(Next)指向为所添加的元素Item，Item的Next指向为null，并且Item的前驱(Prev)指向原本为链尾的元素。

2.指定Index的位置插入元素涉及到链表的遍历，判断Index位于整个链表的前半部还是后半部(index >> 1)，选择遍历的方向，效率上有一定的缇升。考虑到最坏的情况，至少要遍历半张链表(对应index插入时)，相比于ArrayList效率低很多。

3.元素的插入，就是旧节点的断开与新节点创建的过程。借助pred暂时保存将要插入的位置index对应的元数据succ(非空)的前驱指向succ.prev。创建的新节点newNode，final Node<E> newNode = new Node<>(pred, e, succ);；可以看出实例化时，将原数据succ的前驱指向succ.prev作为新节点的前驱prev，succ作为新节点newNode的后继next的指向。对pred判空，如果不为空，则pred.next = newNode;(修改原本succ前驱指向的数据Item的后继Next指向新插入的Item(newNode))。size++自增，至此新的节点与关系生成。如下示意图(来源网络，侵删)：
mfC9Nq.jpg

删除操作

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//删除链头
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

//删除链尾
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //删出链头(非空)
    final E element = f.item;
    //获取链头的后继指向的元素Next
    final Node<E> next = f.next;
    //元素置空
    f.item = null;
    f.next = null; // help GC
    //将链头重新赋值，即原先链头的后继Next作为新的链头
    first = next;
    //表明表中只有一个元素，删除后表为空
    if (next == null)
        last = null;
    else
    //不为空，next = f.next; 被删除元素的后继Next变为链头，next.prev = null;链头的前驱置null，新的关系创建完成
        next.prev = null;
    size--;
    modCount++;
    return element;
}

/**
 * Unlinks non-null last node l.
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}


E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    //指定位置的插入操作，还是会遍历元素，只是双向链表可以选择合适遍历方向提高效率
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

总结：

1.删除操作，同插入操作类似，原先节点前驱Prev与后继Next的指向断开，将需要删除的元素置空。重新建立联系。

2.对比于ArrayList的随机访问快，而频繁的插入和删除较慢。LinkedList的插入删除较快，随机访问较慢；这种说法其实不太准确，通过源码可以看出，LinkedList在指定位置插入和删除元素同样需要遍历元素，只不过由于底层使用的双向链表，可以通过index判断遍历的顺序(从链头或者链尾)。但是ArrayList会有扩容，数据copy的过程，因此LinkedList的插入删除是相对于ArrayList的操作效率高，至于高多少，在数据量很大的时候会有体现。(没有具体测试)

获取元素

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
//获取链头元素
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

//获取链尾
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
//获取指定index对应的元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
    //指定元素的获取，需要遍历链表，通过判断index的属于链表的前半部还是后半部选择遍历方向。
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

总结：

1.对于指定元素的获取，可以看出，要遍历链表，虽然判断了元素属于链表的前部还是后半部，当元素量大时，频繁的获取效率会受到影响，不同于ArrayList的数组，通过下标可以直接返回数据。这也是为什么，LinkedList随机访问元素效率不高的原因(数据量大时)

2.日常的开发选择中，可以根据具体的业务来选择LinkedList或是ArrayList。要求随机访问频繁选用ArrayList而需要频繁的插入删除则LinkedList，(数据量大时对于指定位置的插入和删除，效率是要高于ArrayList的，但也会存在遍历的情况，所以仅仅的是相对的，笼统的说LinkedList的插入于删除效率高，个人认为说法并不是很严谨。。。)。

思考

 LinkedList由于底层的双向链表，除了不在指定index的位置上插入和删除元素，效率是很高的，没有了ArrayList的扩容与，数据的copy过程。对照源码可以了解，插入与删除的操作到底经历了哪些过程，有利于理解为什么说LinkedList的插入与删除效率高(相对的概念)，当然也要看到，指定位置的元素操作，也存在遍历的耗时过程。往下看一点，也许能收获的更多。。。(水平有限，仅仅记录一下个人的理解)

这个功能是摆设，看看就好～～～