注：源码系列文章主要是对某付费专栏的总结记录。如有侵权，请联系删除。

LinkedList 适用于集合元素先入先出和先入后出的场景，在队列源码中被频繁使用，面试也经常被问到。

1 整体架构

LinkedList 底层数据结构是一个双向链表，整体结构如下图所示：

LinkedList 底层数据结构

上图代表了一个双向链表结构，链表中的每个节点都可以向前或向后追溯，几个概念如下：

• 链表每个节点叫做 Node，Node 有 prev 代表前一个节点，next 代表后一个节点；
• first 是双向链表的头节点，它的前一个节点是 null；
• last 是双向链表的尾节点，它的后一个节点是 null；
• 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
• 因为是个双向链表，只要机器内存足够强大，是没有大小限制的。

链表中的元素叫做 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;
    }
}

2 源码解析

2.1 新增

追加节点时，我们可以选择追加到链表头部，还是追加到链表尾部，add 方法默认是从尾部开始追加，addFirst 方法是从头部开始追加，我们分别来看下两种不同的追加方式：

2.1.1 从尾部增加（add/addLast）

/**
 * Links e as last element.
 */
void linkLast(E e) {
    // 将尾节点暂存
    final Node<E> l = last;
    // 初始化新的节点。l: 新节点的前一个节点。e: 当前新增节点值。null: 当前新增节点的下一个节点是 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 为尾节点赋值为当前新增的节点
    last = newNode;
    // 如果尾节点为空(即链表为空)
    if (l == null)
        // 则为头节点赋值为当前新增节点也就是尾节点
        first = newNode;
    // 否则把原尾节点 l 的下一个节点指向当前新增节点
    else
        l.next = newNode;
    // 大小和版本增加
    size++;
    modCount++;
}

2.1.2 从头部追加（addFirst）

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    // 将头节点暂存
    final Node<E> f = first;
    // 初始化新的节点
    final Node<E> newNode = new Node<>(null, e, f);
    // 为头节点赋值为当前新增节点
    first = newNode;
    // 如果原头节点 f 为空(即链表为空)
    if (f == null)
        // 则为尾节点赋值为当前新增节点也就是头节点
        last = newNode;
    // 否则把原头节点的前一个节点指向当前新增节点
    else
        f.prev = newNode;
    // 大小和版本增加
    size++;
    modCount++;
}

头部追加节点和尾部追加节点非常类似，只是前者是移动头部节点的 prev 指向，后者是移动尾部节点的 next 指向。

2.2 节点删除

节点删除和节点追加类似，我们可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指向节点都置为 null，帮助 GC 进行回收。

2.2.1 从头部删除

// 从头部删除节点 f 是链表头部

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 拿出头节点的值
    final E element = f.item;
    // 拿出头节点的下一个节点
    final Node<E> next = f.next;
    // 赋值头节点的值和头节点的下一个节点为 null，帮助 GC 回收
    f.item = null;
    f.next = null; // help GC
    // 原头节点的下一个节点 next 为新的头节点
    first = next;
    // 如果 next 为 null，表明链表为空
    if (next == null)
        last = null;
    else
        // 链表不为空，设置新的头节点的前一个节点为 null
        next.prev = null;
    // 大小和版本更改
    size--;
    modCount++;
    // 返回被删除节点的值
    return element;
}

2.2.2 从尾部删除

// 从尾部删除节点 l 是链表尾部

/**
 * Unlinks non-null last node l.
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 拿出尾节点的值
    final E element = l.item;
    // 拿出尾节点的前一个节点
    final Node<E> prev = l.prev;
    // 赋值尾节点的值和尾节点的前一个节点为 null，帮助 GC 回收
    l.item = null;
    l.prev = null; // help GC
    // 原尾节点的前一个节点 prev 为新的尾节点
    last = prev;
    // 如果 prev 为 null，表明链表为空
    if (prev == null)
        first = null;
    else
        // 链表为不空，设置新的尾节点的下一个节点为 null
        prev.next = null;
    // 大小和版本更改
    size--;
    modCount++;
    // 返回被删除节点的值
    return element;
}

从源码中我们可以了解到，链表结构的节点新增、删除都非常简单，仅仅把前后节点的指向修改而已，所以 LinkedList 新增和删除速度很快。

2.3 节点查询

链表查询某一个节点是比较慢的，需要挨个循环查找才行，源码如下：

// 根据链表索引位置查询节点

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 如果 index 处于队列的前半部分，则从头开始查找，size >> 1 是 size 除以 2 的意思
    if (index < (size >> 1)) {
        Node<E> x = first;
        // for 循环到 index 的前一个 node 停止
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } 
    // 如果 index 处于队列的后半部分，则从尾部开始查找
    else {
        Node<E> x = last;
        // for 循环到 index 的后一个 node 停止
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

从源码中我们发现，LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能，这种思想值得我们借鉴。

2.4 方法对比

LinkedList 实现了 Queue 接口，在新增、删除、查询等方面增加了很多新的方法，这些方法平时特别容易混淆，在链表为空的情况下，返回值也不太一样，如下：

|方法含义|返回异常|返回特殊值|底层实现|
|----|----|----|----|----|
|新增(尾部)|add(e)|offer(e)|底层实现相同|
|删除(头节点)|remove()|poll()|链表为空时，remove 会抛出异常，poll 返回 null|
|查找(头节点)|element()|peek()|链表为空时，element 会抛出异常，peek 返回 null|

PS：Queue 接口注释建议 add 方法操作失败时抛出异常，但 LinkedList 实现的 add 方法一直返回 true。
LinkedList 也实现 Deque 接口，对新增、删除和查找都提供从头开始，还是从尾开始两种方向的方法，比如 remove 方法，Deque 提供了 removeFirst 和 removeLast 两种方向的使用方法，但当链表为空时的表现都和 remove 方法一样，都会抛出异常。

2.5 迭代器

因为 LinkedList 要实现双向的迭代访问，所以我们使用 Iterator 接口肯定不行，因为 Iterator 只支持从头到尾的访问。Java 新增了一个迭代接口，叫做：ListIterator，这个接口提供了向前和向后的迭代方法，如下：

迭代顺序	相关方法
从头到尾迭代	hasNext, next, nextIndex
从尾到头迭代	hasProvious, previous, previousIndex

LinkedList 实现了 ListIterator 接口，源码如图：

// 双向迭代器
private class ListItr implements ListIterator<E> {
    // 按照命名，意思为上一次执行 next() 或者 previous() 方法返回的节点
    private Node<E> lastReturned;
    // 下一个节点
    private Node<E> next;
    // 下一个节点的位置
    private int nextIndex;
    // 期望版本号
    private int expectedModCount = modCount;
    ........
}

从头到尾方向的迭代

// 判断有没有下一个元素
public boolean hasNext() {
    // 下一个节点的索引小于链表的大小，就有
    return nextIndex < size;
}

// 取下一个元素
public E next() {
    // 检查版本号有无变化
    checkForComodification();
    // 再次检查是否还有下一个元素
    if (!hasNext())
        throw new NoSuchElementException();

    // 赋值 lastReturned，首次执行 next() 方法时 赋值为 null
    lastReturned = next;
    // next 是下一个节点，
    next = next.next;
    // 索引变化
    nextIndex++;
    return lastReturned.item;
}

从尾到头方向的迭代

// 判断是否还有上一个节点，我们知道最小索引为 0, 如果 nextIndex 大于0则表示还有上一个元素
public boolean hasPrevious() {
    return nextIndex > 0;
}

public E previous() {
    // 检查版本号有无变化
    checkForComodification();
    // 再次检查是否还有上一个元素
    if (!hasPrevious())
        throw new NoSuchElementException();

    // 如果 next 为null， 则表示当前是从尾到头的第一次迭代，则赋值 next 为 last，
    // 否则赋值 next 为 next 的前一个元素 prev
    lastReturned = next = (next == null) ? last : next.prev;
    // 索引变化
    nextIndex--;
    return lastReturned.item;
}

迭代器删除

LinkedList 在删除元素时，也推荐通过迭代器进行删除，源码如下：

public void remove() {
    // 检查版本号有无变化
    checkForComodification();
    // 首先 lastReturned 是本次迭代的值
    // 如果 lastReturned 为 null，表示未执行 next() 或 pervious() 方法，那删除直接报错
    // 如果 lastReturned 不为 null 则继续执行
    if (lastReturned == null)
        throw new IllegalStateException();

    // 将本次迭代要删除的元素 lastReturned 的下一个元素缓存
    Node<E> lastNext = lastReturned.next;
    // 删除 lastReturned
    unlink(lastReturned);
    // 如果是从尾到头的第一次迭代，则 lastReturned = next = last. 参考上面方法 previous()
    if (next == lastReturned)
        // 这个时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在执行 previous() 方法判断 next 是否为null 时，发现 next 是null，就会把尾结点 last 赋值给 next
        next = lastNext;
    else
        // 反之索引递减
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

总结

LinkedList 适用于要求有顺序、并且会按照顺序进行迭代的场景，主要是依赖于底层的链表结构。

------------------------------------- END -------------------------------------