Java Collections Framework 源码分析(

上一篇 Java Collections Framework 源码分析中我们浏览了 ArrayList 的一些细节，这次分析的是同样实现了 List 接口的 LinkedList。

一个老生常谈的问题是 ArrayList 和 LinkedList 的区别及应用场景，我相信看完本文你会对这个问题有更加深入的认识。

AbstractSequentialList

先来看一下 LinkedList 的类继承体系：

LinkedList.png

从图上可以很清楚的看到 LinkedList 同样实现了 List 接口，不同之处在于 LinkedList 继承的是 AbstractSequentialList 而不是 AbstractList 。

AbstractSequentialList 的注释中写明了这是一个与 AbstractList 有很大差异的类，最大的不同在于在底层它并不支持以 index 随机访问元素。具体看一下 get() 方法：

public E get(int index) {
    try {
        return listIterator(index).next();
    } catch (NoSuchElementException exc) {
        throw new IndexOutOfBoundsException("Index: "+index);
    }
}

可以看到 get() 方法是用 ListIterator 的 next() 方法实现的，其中 listIterator 方法是个抽象方法，需要子类来实现，即由 LinkedList 来实现。所以在这里的时间复杂度是 O(n)，回忆一下 ArrayList 的 get 方法，它的时间复杂度是常量，请确保自己理解差异是如何产生的。

另一个值得注意的是 LinkedList 同时实现了 Deque 接口，而该接口继承与 Queue 接口。很容易理解 Queue 接口定义了 FIFO(First-In-First-Out) 队列数据结构的接口，Deque 在此基础提供了双向队列的操作接口，以后的文章中可以看到使用 Deque 来实现「栈」的源码分析。

从接口而言，LinkedList 可以认为是双向队列的一种实现，你可以用 LinkedList 来模拟「队列」或是「栈」的操作。

LinkedList

现在可以看一下 LinkedList 的代码了。

LinkedList 不同于基于数组的 ArrayList，它是基于「链表」的，确切的说是「双向链表」。看一下它的成员变量：

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

Size 是当前 LinkedList 所拥有的元素数量，first 和 last 分别是链表中的第一个和最后一个元素。Node 则是实际存放元素的类，代表了链表上的每个节点。接着就看一下 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;
    }
}

Node 类的定义简明易懂，是个典型的双向链表的定义。item 是节点上实际的数据，next 和 prev 分别代表了和当前节点紧邻的下一个节点和上一个节点。而 first 节点的 prev 是 null，而 last 节点的 next 也为 null。

看一下几个核心方法的代码，例如 add，remove 都是把具体实现放在了几个以 link 和 unlink 开头的方法中。明白了这几个方法的逻辑，就了解了 LinkedList 新增，移除元素的逻辑。我们先来看一个 add 的 实现。

public boolean add(E e) {
    linkLast(e);
    return true;
}

很简单，直接调用了 linkLast 方法，从方法的注释来看，这个方法是把元素增加到链表的最后，所以继续看 linkLast 方法。

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++;
}

方法的实现简单明了。使用临时变量 l 保存当前的 last 节点，然后构造一个新的链表节点。接着把 last 节点指向这个新节点。之后判断一下之前的 last 节点是否为 null，如果为 null，则说明之前的 LinkedList 是没有元素的空链表，就会把 first 节点也指向新构造的节点。反之则把之前 last 节点(即 l)的 next 指向新节点。

最后 size++ 更新当前链表的大小，modCount++ 的用途与 ArrayList 中的一样，保证不被多线程同时修改造成数据的不一致性，因此 LinkedList 也不是一个线程安全的容器。

再看 remove 方法:

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 {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

这个方法会遍历链表，如果某个元素和方法参数的相等(即 equals 返回 true)，则会移除该元素。for 循环的逻辑也很简单，会从链表的 first 节点开始，依次向后移动，每到一个节点，会判断当前节点的 item 是否相同(或者与 o 一样都为 null)，如果一致则调用 unlink 方法移除这个节点。所以具体移除的逻辑可以看 unlink 方法。

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;
}

unlink 方法写的很工整，没有什么特别的地方，我们依次来看一下。

首先判断要移除节点的 prev 节点是为 null，如果是则说明当前节点为 first 节点，所以直接把 first 节点置为当前节点的 next 节点。否则把 prev 的 next 节点置为当前节点的 next 节点，同时把当前节点的 prev 节点设为 null，便于 GC 回收当前节点的内存。

之后判断 next 是否为 null 的逻辑也类似，就不再赘述了。最后同样是更新 size 的大小和 modCount。

结语

LinkedList 是一个比较简单的数据结构，与 ArrayList 相比是使用双向链表来保存数据，大部分的操作都需要依次访问每个节点，因此需要随机访问，或者在中间插入，移除数据的时间复杂度为 O(n)，效率较差。但是根据双向链表的特性可以在需要队列或是栈的场合使用。

下一篇我们会解析另一种无序数据结构 Set 的源码，如果你想了解 Java Collections Framework 中各种数据结构的源码知识，就赶快关注我的公众号吧！

13688092-1d0f5f4dcf0ba004.png