LinkedList 的 API 与数据结构

LinkedList 是 List 接口和 Deque 接口的双向链表实现，它所有的 API 调用都是基于对双向链表的操作。本文将介绍 LinkedList 的数据结构和分析 API 中的算法。

数据结构

LinkedList 的数据结构是一个双向链表，它有两个成员变量：first 和 last，分别指向双向队列的头和尾。

.st1 {fill:#191919;font-family:Times New Roman;font-size:9pt}
prevnext'A'prevnext'B'prevnext'C'firstlast

Node<E> first;

Node<E> last;

这里“双向”的含义是相对单链表而言的，双向链表的节点不仅有后继，还有前驱。LinkedList 中双向链表的节点是一个个的 Node，它是 LinkedList 的一个静态内部类。其定义如下。Node 是一个泛型类，泛型参数是存放在 LinkedList 中的值的类型。

    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 如下图所示。

LinkedList 的 API 都是基于双端队列的操作来实现的，这些操作被封装成了一系列的 private 方法。下面对这些私有方法进行分析。

插入操作：linkFirst(e) 与 linkLast(e)

LinkedList 通过 linkFirst(e) 与 linkLast(e) 分别往双向链表的头部和尾部插入元素。插入元素时需要考虑两种情况：1）双向链表中不包含元素；2）双向链表中已经包含了元素。插入元素属于修改操作，因此操作数 modCount 需要进行自增。更多关于 modCount 的说明可以参考这篇：(ArrayList 源码分析)[https://www.cnblogs.com/robothy/p/13969448.html]。linkFirst(e) 源码如下，linkLast(e) 源码与前者类似。

    private void linkFirst(E e) {

        final Node<E> f = first;

        final Node<E> newNode = new Node<>(null, e, f); // 创建一个 Node 对象 e，在构造方法中，e 的后继已经指向了旧的 first。

        first = newNode;

        if (f == null) // 处理边界情况：双向链表中没有元素

            last = newNode;

        else

            f.prev = newNode;

        size++; // size 用于统计 LinkedList 中的元素个数

        modCount++; // 统计操作数，用于支持迭代时 fail-fast 机制

    }

在指定元素前面插入：linkBefore(e, succ)

linkBefore(e, succ) 在元素 succ 前面插入元素 e，它需要考虑两种情况：1）succ 的前驱为空；2）succ 的前驱不为空。在指定元素前面插入操作时间复杂度为 O(1)，相对 ArrayList 时间复杂度为 O(n) 插入来说，效率极高。（n 为 List 中已有元素的个数）

    void linkBefore(E e, Node<E> succ) {

        // 这里没有对 succ 为空进行检查，因为是 private 方法，在外层确保输入不为空即可

        final Node<E> pred = succ.prev; // 获取 succ 的前驱

        final Node<E> newNode = new Node<>(pred, e, succ); // 构造一个新的节点，此时新节点的前驱指向 succ 的前驱，新节点的后继指向 succ

        succ.prev = newNode; // 更新 succ 的前驱指向

        if (pred == null) // succ 前驱原来所指元素为空的情况

            first = newNode; // 更新 first 指针

        else

            pred.next = newNode; // 否则更新 succ 原来前驱所指即可

        size++;

        modCount++;

    }

移除头部和尾部元素：unlinkFirst(f) 和 unlinkLast(l)

unlinkFirst(f) 操作将移除头部节点，它需要考虑两种情况：1）链表中只有 1 个元素；2）链表中有超过 1 个元素。

    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;  // 这两个 null 赋值操作斩断了引用链，让 GC 能够回收对象。

        f.next = null; // help GC

        first = next;

        if (next == null) // 只有 1 个元素的情况，last, first 指向同一个元素，因此移除了 first 所指向的元素之后，last 也要更新

            last = null;

        else // 含有多个元素的情况

            next.prev = null;

        size--;

        modCount++;

        return element;

    }

移除指定元素：unlink(x)

unlink(x) 在移除指定元素时也是小心翼翼。这个方法在功能上可以替代 unlinkFirst(f) 和 unlinkLast(f)，不过因为 LinkedList 对头和尾的操作及其频繁，因此用单独的更高效的函数进行处理可以在一定程度上提升性能。

    E unlink(Node<E> x) {

        // assert x != null;

        final E element = x.item; // 取出要返回的值

        // 拿到 x 的前驱和后继

        final Node<E> next = x.next;

        final Node<E> prev = x.prev;

        // 处理前驱指针

        if (prev == null) { // 前驱所指为空，表示 x 为头部元素

            first = next;

        } else { // 前驱不为空

            prev.next = next;

            x.prev = null; // 帮助 GC

        }

        // 处理后继指针

        if (next == null) {

            last = prev;

        } else {

            next.prev = prev;

            x.next = null; // 帮助 GC

        }

        x.item = null; // 帮助 GC

        size--;

        modCount++;

        return element;

    }

根据索引获取指定节点： node(index)

因为是链表结构，要根据位置获取节点只能以迭代的方式进行，时间复杂度为 O(n)，这里的 node(index) 方法做了一点优化：若索引号 index 在前半部分，则从头节点开始遍历；若索引好 index 在后半部分，则从尾节点开始遍历。

    Node<E> node(int index) {

        // assert isElementIndex(index);

        if (index < (size >> 1)) { // 如果 index 小于 size 的一半，则从头部开始遍历

            Node<E> x = first;

            for (int i = 0; i < index; i++)

                x = x.next;

            return x;

        } else { // 如果 index 大于等于 size 的一半，则从尾部开始遍历

            Node<E> x = last;

            for (int i = size - 1; i > index; i--)

                x = x.prev;

            return x;

        }

    }

以上部分就是 LinkedList 中双端队列的操作了，不过这些方法都被 private 修饰，因此开发人员无法直接调用它们，不过 LinkedList 所暴露出来的 API 几乎都是调用这些 private 方法来完成操作的。下面介绍 LinkedList 的相关 API。

构造方法

LinkedList 的构造方法有两个，一个是无参构造方法，另一个构造方法可以传入一个集合。

LinkedList() ：构造一个空的列表；
LinkedList(Collection<? extends E> c) ：构造一个列表，并将集合中的元素插入到列表中，插入顺序与集合的迭代器返回元素的顺序一致。

LinkedList 作为 List 接口的实现类

size()

LinkedList 内部维护了一个成员变量 size，每次插入或者删除元素时都会更新该变量的值。size() 方法仅仅是返回了该变量的值。

isEmpty()

通过 size 的值来判断，size 为 0 即表示 LinkedList 为空。

indexOf(o)

indexOf(o) 将返回指定元素 o 在 LinkedList 中首次出现的位置（头节点到尾节点方向），它需要从头节点开始遍历双向链表。如果元素不存在，则返回 -1。传入的 o 可以为 null，源码中专门分了两个分支来处理传入的 o 为 null 和非 null 的问题。时间复杂度为 O(n)，其中 n 为 LinkedList 中元素的数量。

    public int indexOf(Object o) {

        int index = 0;

        if (o == null) { // 处理 o 为 null 的情况

            for (Node<E> x = first; x != null; x = x.next) {

                if (x.item == null)

                    return index;

                index++;

            }

        } else { // 处理 o 不为 null 的情况

            for (Node<E> x = first; x != null; x = x.next) {

                if (o.equals(x.item))

                    return index;

                index++;

            }

        }

        return -1;

    }

lastIndexOf(o)

lastIndexOf(o) 与 indexOf(o) 相反，它从双向链表的尾部开始遍历，返回元素 o 在 LinkedList 中最后出现的位置。返回 -1 表示不包含元素 o。

contains(o)

contains(o) 方法调用了 indexOf(o)，通过检查返回值是否为 -1 来判断 LinkedList 中是否包含了 o。

add(e)

add(e) 将元素 e 添加到双向链表的末尾，此方法直接调用了 linkLast(e) 方法完成了操作。

    public boolean add(E e) {

        linkLast(e);

        return true;

    }

add(index, element)

此方法将元素添加到指定的索引位置，它分了两种情况：一种是 index == size，直接添加到双向链表尾部即可；另一种是非添加到尾部，需要先迭代找到索引位置为 index 的元素，然后将新元素插入到它前面。时间复杂度为 O(n)。

    public void add(int index, E element) {

        checkPositionIndex(index); // 暴露给用户的 API，需要对用户的输入进行检查

        if (index == size)

            linkLast(element);

        else

            linkBefore(element, node(index));

    }

set(index, element)

此方法调用了 node(index) 获取 element 所在的 Node，然后将 element 挂到了 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;

    }

remove(index)

remove(index) 移除索引为 index 的元素，先根据索引获取节点，然后调用 unlink(e) 移除节点。

    public E remove(int index) {

        checkElementIndex(index);

        return unlink(node(index));

    }

remove(o)

remove(o) 将查找元素 o 在 LinkedList 中第一次所在的节点，然后移除该节点。这一操作需要遍历双向链表。需要注意的是 remove(o) 并不会移除所有的 o ，只会移除第 1 个。

    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;

    }

listIterator()

LinkedList 没有单独的内部类实现 Iterator 接口，调用 iterator() 方法返回的本质是一个 ListItr，和 listIterator() 返回的是一样的迭代器。

ListItr 允许从指定下标位置开始迭代，下标位置通过构造方法的参数传入。

        ListItr(int index) {

            // assert isPositionIndex(index);

            next = (index == size) ? null : node(index);

            nextIndex = index;

        }

LinkedList 有两个获取 ListItr 的 API，分别是 listIterator() 与 listIterator(index)，二者本质一样。

    public ListIterator<E> listIterator() {

        return listIterator(0);

    }

    public ListIterator<E> listIterator(int index) {

        checkPositionIndex(index);

        return new ListItr(index);

    }

ListItr 在迭代的过程中 LinkedList 不能够被其它的线程改变，否则可能抛出 ConcurrentModificationException。这是一种 fail-fast 策略，通过修改数 modCount 来实现，前面可以看到，凡是会改变链表结构的操作都会更新 modCount 的值。在迭代的过程中不断检查 modCount 是否和期望的值一致，如果不一致，则说明有其它的线程修改了双向链表的结构。此时 LinkedList 中的数据可能出现错误，但如果没有 fail-fast 机制，这种错误可能不会立即暴露出来，系统可能需要运行很长时间才暴露，到那时可能已经产生严重后果了，后面再来排查错误原因也及其困难。

通过 modCount 机制来探测这类难以错误，一旦探测到，立即报告，这就是 fail-fast 机制。不过由于多线程操作本身存在着不确定性，modCount 也并非一定能够探测到这种错误。为了避免这种错误，在多线程访问同一个 LinkedList 对象时应该进行线程同步，最好就时不让多线程访问同一个 LinkedList。

不过 ListItr 允许迭代器自身修改 LinkedList，它在修改之后会更新 modCount，支持的修改操作包括：

remove() 移除刚刚返回的元素
set(e) 将刚刚返回的元素所在 Node 节点的值修改为 e
add(e) 在刚刚返回的元素后面插入 e

LinkedList 作为 Deque 接口的实现类

双端队列接口 Deque 提供了一组在线性集合头部和尾部进行操作的 API，LinkedList 在通过操作双端队列的头部和尾部实现这些抽象方法。

新增头（尾）部元素：addFirst(e), addLast(e), offer(e), offerFirst(e), offerLast(e), push(e)

    public void addFirst(E e) {

        linkFirst(e); // LinkedList 支持存放 null

    }

获取头（尾）部元素：getFirst(), getLast(), peek(), peekFirst(), peekLast()

    public E getFirst() {

        final Node<E> f = first;

        if (f == null) // getXXX() 抛出遗产,peekXXX() 使用特殊值 null 来表示没有元素

            throw new NoSuchElementException();

        return f.item;

    }

删除头（尾）部元素：removeFirst(), removeLast(), poll(), pollFirst(), pollLast(), pop()

    public E removeFirst() {

        final Node<E> f = first;

        if (f == null)

            throw new NoSuchElementException();

        return unlinkFirst(f);

    }

小结

LinkedList 内部是双向链表结构，新增，删除元素很方便，支持存放 null 元素。

LinkedList 实现了 List 和 Deque 接口。作为 List，LinkedList 适用于数量未知且需要大量增删操作情形，若需要随机访问或者大量查询，应该使用 ArrayList；作为 Deque，LinkedList 适用于容量未知的情形，如果容量已知，则使用 ArrayDeque 效率会更高一些。

LinkedList 是非线程安全的，多个线程同时访问一个 LinkedList 可能破坏其内部结构。

巴特西