本文是对 JDK1.8 中 LinkedList 的分析与总结，在阅读源码的同时加深对其提供的方法的使用，以便更好的理解。

总览

1
2
3


public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

通过源码可以看出，LinkedList 继承了 AbstractSequentialList，分别实现了 List、Deque、Cloneable 以及 Serializable 接口，而没有实现 RandomAccess 接口（这是 ListList 与 ArrayList 的区别）。其中，AbstractSequentialList 继承自 AbstractList，而上篇文章中提到的 ArrayList 是直接继承自 AbstractList 的。

从整体上看，LinkedList 属于双向链表，可以实现 Stack、Queue、Deque（双端队列）结构，由于继承了 AbstractSequentialList 类，所以 LinkedList 具有 get、set、add、remove、insert 等方法。

LinkedList

LinkedList 是一个双向链表，链表是肯定有节点的，而且还有指向下一节点的指针，而在双向链表中，节点还有指向前一节点的指针。

其中，Prev存储的是链表中的前一个元素，如果当前节点是第一个元素的话，那么Prev就是指向null的。Next指向链表中的后一个元素，对于最后一个元素来说，它的Next也是指向null的。

有几点需要注意的是：LinkedList 可以存储 null，也可以存储重复的数据，并且 LinkedList 中的节点是有序的，但是它不是线程安全的。

域

在 JDK1.8 中，LinkedList 的域有 3 个，其中 size 表示链表中元素的数量，first 表示指向第一个节点的指针，而 last 表示指向最后一个节点的指针。如下所示：

1
2
3
4
5


transient int size = 0;

transient Node<E> first;

transient Node<E> last;

Node

首先看一下 Node 节点的结构定义，其中，item 表示当前节点所包含的值，next 表示当前节点的下一个节点，prev 表示当前节点的上一个节点。如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

构造函数

LinkedList 中有两个构造函数，一个是默认无参的构造函数，另一个是参数为指定容器的构造函数，这个含参的构造函数通过调用第一个构造方法创建一个空的链表，然后调用 addAll() 方法将所有的元素添加到链表中。如下所示：

1
2
3
4
5
6
7
8


public LinkedList() {
}


public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

添加

单纯的 add 方法有两个，一个是接收一个元素，然后调用 linkLast 方法将该元素插入到链表尾部；另一个是接收一个索引和元素，用于在链表指定位置插入该元素。具体的插入方式有些不同，如下所示：

 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


// 将元素插入到链表尾部
public boolean add(E e) {
    linkLast(e);
    return true;
}


// 将元素插入到链表的指定位置
public void add(int index, E element) {
    // 判断索引是否合法
    checkPositionIndex(index);

    // 判断索引是不是链表的尾部，如果是，则直接将该元素插入到链表尾部
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}


// 将元素插入到链表尾部
void linkLast(E e) {
    final Node<E> l = last;
    // 创建一个新的节点，并指定新节点的 prev 为链表尾节点的 last，新节点的 next 为 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 将链表的 last 指向新的节点，此时这个新插入的节点就成为了链表的最后一个节点
    last = newNode;
    // 如果尾节点为空，则当前链表还没有节点
    if (l == null)
        first = newNode;
    // 如果尾节点不为空，则让原来的尾节点的 next 指向新插入的节点
    else
        l.next = newNode;
    size++;
    modCount++;
}


// 在非 null 节点 succ 之前插入元素 e
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    // 创建一个新节点，并将其前驱指向 succ 的前驱，后继指向 succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将 succ 的前驱指向新节点
    succ.prev = newNode;
    // 如果尾节点为空，则当前链表还没有节点
    if (pred == null)
        first = newNode;
    // 将 succ 前驱节点的后继指向新节点
    else
        pred.next = newNode;
    size++;
    modCount++;
}

查找

LinkedList 的查找过程需要从头节点（或尾节点）开始查找，时间复杂度为 O(N)，如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}


Node<E> node(int 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
 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 E remove(int index) {
    checkElementIndex(index);
    // 通过 node 方法定位 index 索引的元素，然后调用 unlink 方法断开与链表的连接
    return unlink(node(index));
}

// 直接将元素进行删除
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 在 o 不等于 null 的情况下，从头开始遍历链表，直到找到与 o 相等的元素，
        // 使用 unlink 方法将它们断开连接
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

再来看看将某一节点与链表进行断开的方法 unlink，如下所示：

 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


// 断开非空节点 x
E unlink(Node<E> x) {
    // 将待删除的节点保存下来，便于返回
    final E element = x.item;
    // 记录待删除节点的前驱和后继节点，后面有用
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 待删除的节点是头节点
    if (prev == null) {
        // 则 first 就来到待删除节点的后一个节点
        first = next;
    } else {
        // 将待删除节点的前一个节点的 next 指针指向待删除节点的后一个节点
        prev.next = next;
        // 将待删除节点的 prev 指针指向空，为了将待删除节点与前面的链表进行断开
        x.prev = null;
    }

    // 待删除节点是尾节点
    if (next == null) {
        // 则 last 就来到待删除节点的前一个节点
        last = prev;
    } else {
        // 将待删除节点的后一个节点的 prev 指针指向待删除节点的前一个节点
        next.prev = prev;
        // 将待删除节点的 next 指针指向空，为了将待删除节点与后面的链表进行断开
        x.next = null;
    }

    // 将待删除节点置为空，便于垃圾回收
    x.item = null;
    size--;
    modCount++;
    // 返回被删除的节点
    return element;
}

遍历

在遍历 LinkedList 的时候，最好使用 foreach 进行遍历，因为通过 javap 进行反编译后，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
37
38


public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    // 构造方法接收一个索引，将 next 的引用指向 index 位置的节点
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    // 如果 nextIndex 小于链表元素的大小，则说明还能够继续遍历
    public boolean hasNext() {
        return nextIndex < size;
    }

    // 获取下一个元素
    public E next() {
        checkForComodification();
        // 如果不能继续遍历了，则说明已经遍历完了
        if (!hasNext())
            throw new NoSuchElementException();

        // 设置最近一次访问的节点为 next 节点
        lastReturned = next;
        // next 指针后移
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
}

总结

一般会把 LinkedList 和 ArrayList 进行比较，此处的总结，也将它们之间异同进行整理。

ArrayList 底层基于数组，可以很快的通过索引进行查询操作，而 LinkedList 底层基于链表，通过一个一个的节点将元素连接在一起，节点除了保存元素值以外，还要维护一个指向前驱和后继的指针，所以 LinkedList 比 ArrayList 更加消耗内存。
到底谁的插入、删除效率高？一般情况下，你可能会认为 LinkedList 在进行插入、删除的时候，只需要找到它，然后更改一下指针就好了，所以你会认为 LinkedList 更快一些。
- 但是这里所谓的“快”，仅仅指的是指针的更改，而你要找到那个节点可能需要从头节点或尾节点一个一个的去遍历，才能找到。
- 所以，LinkedList 在进行插入、删除的时候，慢在寻址，快在更改前驱和后继的指向。
- 而 ArrayList 在进行插入、删除的时候，慢在数组的拷贝，快在寻址。
如果待插入、删除的元素在存储的时候是位于整体数据的前半段的话，那么使用 LinkedList 进行操作会快的多，因为 ArrayList 需要将该元素后面的所有数据进行大量的移动或拷贝，非常耗时。此外，如果插入数据过多，还得进行扩容操作。
如果待插入、删除的元素在存储的时候是位于整体数据的后半段的话，一般来说 ArrayList 的效率要高于 LinkedList，因为 ArrayList 复制元素的数量就少了。
在对 ArrayList 和 LinkedList 进行遍历的时候，也注意采用不同的方式。实现 RandomAccess 接口的 ArrayList 应该使用 for 循环遍历，而不是 foreach 进行遍历。也就是说，针对随机访问的结构，采用 for 循环的效率要高于 foreach 循环，而针对顺序访问的结构，采用 foreach 循环比 for 循环的效率要高，因为 foreach 的底层实现原理就是使用迭代器 Iterator 进行实现的。

参考

https://www.programiz.com/java-programming/linkedlist

https://www.cnblogs.com/xrq730/p/4865416.html

http://www.tianxiaobo.com/2018/01/31/LinkedList-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90-JDK-1-8/

JDK 源码之集合类 LinkedList

Contents

总览

LinkedList

域

Node

构造函数

添加

查找

删除

遍历

总结

参考