转载

走进 JDK 之 LinkedList

如果你了解链表的基本结构的话， LinkedList 的源码其实还是比较容易理解的。 LinkedList 是基于双向链表实现的，与 ArrayList 不同的是，它在内存中不占用连续的内存空间，相连元素之间通过 “链” 来链接。对于单链表，每个节点有一个 后继指针 指向下一个节点。对于双向链表来说，除了后继指针外，它还要一个 前驱指针 指向前一个节点。那么，双向链表有什么好处呢？既然有了前驱指针，在遍历的时候就可以向前遍历，在下面的源码分析中可以看到，这是单链表所不具备的功能。

前面介绍 ArrayList 的时候说过，数组具备随机访问能力，其根据下标随机访问的时间复杂度是 O(1) 。同样，为了保证内存的连续性，其 插入 和 删除 操作就相对低效的多。而链表正好与其相反，其不具备随机访问能力，但是 插入 和 删除 就相对高效，仅仅只需修改 后继指针 和 前驱指针 指向的节点即可。其插入和删除操作的时间复杂度均为 O(1) ，但这个 O(1) 其实也不是很严谨。删除指定节点，还是删除值等于给定值的节点，单链表还是双向链表，其实时间复杂度的表现都是不一样的，下面的源码解析中也会有所体现。好了，关于链表就说这么多了，下面来进入 LinkedList 的源码分析。

首先看一下 LinkedList 的 UML 图：

源码解析

类声明

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}
复制代码

继承了抽象类 AbstractSequentialList ，它提供了一些集合类型无关的基本方法的实现，如 get set add remove 等。通常实现它的集合类型不具备随机访问能力，这和 AbstractList 是相对立的。
实现了 List 接口
实现了 Deque 接口，说明也可以当做一个双端队列，源码中也实现了相关方法。
实现了 Cloneable 接口，提供克隆能力。和 ArrayList 一样，也是浅拷贝。
实现了 Serializable 接口，提供序列化能力

成员变量

transient int size = 0; // 表示链表大小
transient Node<E> first; // 头结点
transient Node<E> last; // 尾节点
private static final long serialVersionUID = 876323262645176354L;
复制代码

顺便看一下结点 Node 类的定义：

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;
    }
}
复制代码

每个结点都包含指向前一个结点的前驱指针 prev ，和指向后一个结点的后继指针 next 。一般头结点的前驱指针和尾节点的后继指针都指向 null。

构造函数

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

第一个是默认的无参构造，会构建一个空链表。第二个根据参数中的集合通过 addAll() 方法构造链表，链表中的元素顺序根据集合 c 的迭代器的迭代顺序。

方法

你可以翻一下 LinkedList 的 API 列表，提供了许许多多的方法，其实很多都是重复的。它实现了 Deque 接口中的方法，重写了 AbstractSequentialList 类的方法，总结一下就是各种增删改查操作，最后调用的都是自己的私有方法 linkxxx/unlinkxxx 等，很好的做到了隔离，也是一种值得学习的设计思想。下面就优先来看一下这些方法。

linkFirst(E e)

// 将 e 置为头结点
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) // 如果链表为空， e 节点就是尾节点
        last = newNode;
    else
        f.prev = newNode; // 链表不为空，插入 e 节点，并将原头结点的 prev 指向 e 节点
    size++;
    modCount++;
}
复制代码

链表为空的话，插入的 e 既是头结点也是尾节点。

链表不为空的话，就移动原头结点的前驱指针。

linkLast(E e)

// 将 e 置为尾结点
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; // 如果链表为空， e 节点就是头节点
    else
        l.next = newNode; // 链表不为空，插入 e 节点，并将原尾结点的 next 指向 e 节点
    size++;
    modCount++;
}
复制代码

链表为空的话，插入的 e 既是头结点也是尾节点。

链表不为空的话，就移动原尾结点的后继指针。

linkBefore(E e, Node succ)

// 在节点 succ 前插入元素
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ); // 构建新结点
    succ.prev = newNode; // 将 succ 的 prev 指针指向新结点
    if (pred == null) // pred 为 null，说明 succ 原来就是头结点，现在要更新头结点
        first = newNode;
    else
        pred.next = newNode; // 将 succ 的前一个结点的 next 指针指向新结点
    size++;
    modCount++;
}
复制代码

原理也很简单，你可以想象成打上结的绳子，你只需要把 succ 结点打开，然后把需要插入的结点系上去就可以了，时间复杂度为 O(1) 。当然，这是双向链表。对于单向链表还是 O(1) 吗？显然不是的，因为在单向链表中你没办法执行下面这行代码：

final Node<E> pred = succ.prev;
复制代码

也就是说你没办法直接拿到 succ 的前驱结点，也就没法直接将 succ 的前一个结点的 next 指针指向新结点。你只能通过遍历去获取前驱结点。所以，对于单链表来说，插入元素的时间复杂度还是 O(n) 。

unlinkFirst(Node f)

// 移除头结点 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 头结点置空以便 GC
    first = next;
    if (next == null) // next 为空，说明链表原来只有一个元素
        last = null;
    else
        next.prev = null; // 将 next 的 prev 置空，此时 next 是头结点
    size--;
    modCount++;
    return element;
}
复制代码

这里默认参数中的 f 结点就是头结点。如果链表中原本只有一个元素，那么头尾结点都要置空。如果多于一个元素，只要把头结点的下一个结点的前驱指针指向 null 就可以了。

unlinkLast(Node l)

// 移除尾节点 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 头结点置空以便 GC
    last = prev;
    if (prev == null) // prev 为空，说明链表原来只有一个元素
        first = null;
    else
        prev.next = null; // 将 prev 的 next 置空，此时 prev 是尾结点
    size--;
    modCount++;
    return element;
}
复制代码

和 unlinkfirst 基本一致，只要把尾结点的前一个结点的后继指针指向 null 就可以了。

unlink(Node x)

// 移除指定非空节点 x
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) { // x 是头结点
        first = next;
    } else {
        prev.next = next; // 将 x 的 next 指向 x 后面一个节点
        x.prev = null;
    }

    if (next == null) { // x 是尾节点
        last = prev;
    } else {
        next.prev = prev; // 将 x 的 prev 指向 x 前面一个节点
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}
复制代码

代码也比较简单，同时修改前一个结点的后继指针和后一个结点的前驱指针就可以了，要注意参数结点是头结点或者尾节点的特殊情况。时间复杂度也是 O(1) ，对于单链表是 O(n) 。

上面的插入和删除都是针对指定结点的，还有一种情况是针对指定值的。比如，对于一个存储 int 值的链表，我要删除值为 1 的结点，其时间复杂度还是 O(1) 吗？下面来看看 remove(Object o) 方法。

remove(Object o)

public boolean remove(Object o) {
    if (o == null) { // 删除 null 元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else { // 删除非 null 元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
复制代码

很显然，对于删除值等于指定值的结点，时间复杂度也是 O(n) 。循环遍历得到该结点之后再调用 unlink() 方法去删除。还要注意一点，该方法仅仅删除第一次出现的值等于指定值的结点，链表是允许重复元素的。

说完了插入和删除，我们再来看看查找。虽说链表的查找操作必然是 O(n) 的，但是 LinkedList 还是对查找操作做了相应的优化。下面来看一下 get() 方法。

get(int index)

// 返回指定位置的元素
public E get(int index) {
    checkElementIndex(index); // 边界检查
    return node(index).item; // 虽然时间复杂度仍然是 O(n)，但只需遍历一半的链表
}
复制代码

checkElementIndex 检测 index 是否越界。 node() 方法用来获取 index 处的指定结点。

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 根据下标是否小于 size/2，每次只遍历半个链表
    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;
    }
}
复制代码

得益于双向链表的特性， LinkedList 的查找每次只需遍历半个链表，虽然时间复杂度还是 O(n) ，但是是有实际上的性能提升的。

LinkedList 的方法就说这么多了，虽说大部分方法都没提到，但是剩下的方法基本都是依靠上面解析过的这些方法来实现的，也就没有单独拿出来说的必要了。我在源码文件中都进行了注释，感兴趣的可以到我的 Github 查看 LinkedList.java 。