Collections(三)List下篇-LinkedList

[Sayi]

LinkedList实现了List接口，它使用链表方式实现了有序的序列结构。LinkedList又是一个有趣的存在，它还实现了Deque接口，而Deque接口是实现了Queue接口，所以LinkedList同时也实现了一个双向队列、队列或者栈结构。

本文将阐述LinkedList的实现原理，重点放在List接口方法实现上，关于Deque的方法使用，将在后续关于双向队列的章节中提及。

LinkedList实现原理

LinkedList是基于双向链表实现的，内部维护了首尾两个节点：Node<E> first和Node<E> last，其中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值为null，尾节点的next值为null，即first.prev == null, last.next == null，LinkedList的大小即是节点的个数，由于是链表结构，它没有初试容量的概念，也无需扩容。

正因为双向链表这样的结构，我们可以限定元素插入和删除的方式，从而支持FIFO或者LIFO方式。

除了JDK中的实现方式外，双向链表还有个实现方式，给两个虚的节点，一个代表首虚节点，一个是尾虚节点，所有的元素都会在虚节点之间，这样的好处是我们在首尾插入和删除元素时，两个虚节点是不用变的。

基础源码分析

增加元素

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

如果是在末尾插入元素，则时间复杂度会是O(1)，如果是在中间插入，则会通过node(index)方法先遍历找到指定位置的节点，再进行插入，这样时间复杂度就是O(n)。我们先来看看node方法：

Node<E> node(int 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;
    }
}

它对遍历作了一个简单的性能优化，当index大于list大小的二分之一时，就会从尾部向头部遍历，否则会从头部向尾部遍历。看到这里，可能有人会问，ArrayList的插入操作的时间复杂度是多少了？其实也是O(n)，但是它的开销浪费在数组的空间复制上，所以比LikedList代价大。

接下来我们再看看典型的引用操作代码，无非就是对节点的prev和next进行处理：

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++;
}
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;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

获取元素

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

前面已经说过，node是一个简单优化的顺序访问方法，获取一个元素的时间复杂度是O(n)。

更新元素

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

找到Node节点，重新设置节点item值。`

删除元素

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

删除元素，首先是找到元素，然后对节点的引用进行处理。

iterator源码实现和fail-fast设计

这里给出内部类ListItr的核心代码：

public boolean hasNext() {
    return nextIndex < size;
}

public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();

    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

它和ArrayList的Itr内部类的实现方式没有多大的区别，通过modCount机制实现fail-fast设计，获取下一个元素是获取节点的next引用。ListItr实现了ListIterator接口，所以它支持双向遍历和更多操作。

性能

LinkedList会以较低的代价进行插入和删除，在随机访问方面相对比较慢，但这也不是绝对的，如果我们能避免ArrayList去复制空间，比如只在末尾插入元素，那么由于随机访问特性，ArrayList在这样的场景下会是一个不错的选择。

总结

关于List，我们通过两篇文章详细介绍了ArrayList和LinkedList，它们都不是线程安全的。如果需要使用线程安全的List，我们可以通过java.util.Collections.synchronizedList(List<T>)获取包装后的线程同步的List对象。

在java.util.concurrent并发包下，还提供了 CopyOnWriteArrayList 类支持并发操作，它通过一个写时复制的数组实现。