Java Collections Framework 源码分析(3 - LinkedList)

228 阅读5分钟

Java Collections Framework 源码分析(3 - LinkedList)

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

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

AbstractSequentialList

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

从图上可以很清楚的看到 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 中各种数据结构的源码知识,就赶快关注我的公众号吧!