面试官：说下 LinkedList 的实现原理

前边我们通过源码分析的方式介绍了 ArrayList，相信大家对 ArrayList 的底层实现机制应该是有了一定的了解。那么，本篇我们再通过源码分析的方式，继续探究一下开发中另一个常用的集合——LinkedList。

LinkedList 概览

LinkedList 是 Java 集合框架众多集合类型中一个比较灵活的数据结构，也是 List 接口的一种实现方式。它底层基于双向链表实现，允许存储包括 null 在内的任何元素，适用于需要频繁插入和删除元素的场景。

关键特点

双向链表存储有序：LinkedList 是基于双向链表实现的，它不同于 ArrayList 使用的连续内存块。在 LinkedList 中，每个元素（Node）不仅包含自身存储的数据，还包含了两个引用（指针），分别指向链表中的前一个和后一个节点。说其使用比较灵活，也是因为双向链表这种结构允许 LinkedList 在遍历、插入或删除元素时不需要像数组那样移动其他元素的位置，只需改变引用指向即可。
高效增删操作：与 ArrayList 不同，LinkedList 在链表头部或尾部进行添加或删除操作的时间复杂度为 O(1)，这是因为这些操作只需改变几个引用（指针）。然而，在链表中间位置进行查找、插入或删除操作时，时间复杂度为 O(n)，因为需要从链表的一端开始遍历到目标位置。因此，LinkedList 对于频繁的插入和删除操作非常高效，尤其是在列表的两端时。
非线程安全：与 ArrayList 一样，LinkedList 也不是线程安全的。如果多个线程同时访问同一个 LinkedList 实例，并且至少有一个线程修改了列表结构（如添加或删除元素），那么必须通过外部同步来保证操作的安全性。可以使用 Collections.synchronizedList() 方法将 LinkedList 包装成线程安全的版本。
额外的内存消耗：相较于 ArrayList，LinkedList 每个元素都需要额外的空间来存储前后节点的引用。因此，在处理大量数据时，LinkedList 可能会占用更多的内存空间。不过，对于频繁的插入和删除操作，这点额外的内存消耗通常是可以接受的代价。

继承与实现

继承 AbstractSequentialList：该类实现了 List 接口并提供了部分实现。它与 AbstractList 不同，AbstractList 更适合于支持随机访问的数据结构（如数组），而它是针对那些底层数据结构更适合顺序访问的（比如链表）而不是随机访问的数据结构提供了一些默认实现，减少了实现一个基于顺序访问（如链表）的 List 接口所需的工作量。
实现 List 接口：提供线性列表集合框架的基础行为，支持按索引访问、添加和移除元素等基本功能。
实现 Deque 接口：表明可以作为双端队列使用，允许在两端插入和移除元素。实现该接口使其支持栈和队列的行为。
实现 Cloneable 和 Serializable 接口：允许创建对象副本并支持序列化，方便在网络上传输或持久化存储。实现这两个接口的作用可以参照
你真的了解 ArrayList 吗？（上）

LinkedList 源码分析

数据结构（重点）

LinkedList 的底层数据结构是双向链表，双向链表的每个节点实现是由 LinkedList 的静态内部类 Node<E> 来表示的，下面我们先看下 Node<E> 的源码实现：

private static class Node<E> { // 使用了泛型，传入的类型代表存储元素的类型
    E item; // 这是存储在节点中的实际数据元素
    Node<E> next; // 指向链表中当前节点的前一个节点。对于头节点，它的 prev 为 null
    Node<E> prev; // 指向链表中当前节点的下一个节点。对于尾节点，它的 next 为 null

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList 的数据存储结构（双向链表）图示如下：

LinkedList 本身没有索引的概念，从源码实现上看也很简单，每个节点都只包含三个属性（前节点引用，存储的元素，后节点引用），但这并不代表它是无序的，因为每个节点都存储了相邻节点的引用，使它成为了一个有序队列。

双向链表的工作原理：

插入操作：当在一个位置插入新元素时，会创建一个新的 Node 实例，并更新相邻节点的 prev 和 next 引用。例如，在链表头部插入元素时，新的头节点的 prev 会设置为 null，其 next 指向原来的头节点；同时，原来的头节点的 prev 会更新为新的头节点。
删除操作：删除节点时，需要调整被删除节点的前后节点的引用。具体来说，就是让前一个节点的 next 指向被删除节点的 next，并且让后一个节点的 prev 指向被删除节点的 prev。如果删除的是头节点或尾节点，则还需要更新链表的头指针或尾指针。
遍历操作：由于每个节点都有对前后节点的引用，所以可以从任一方向遍历整个链表。从头到尾遍历时，使用 next 引用来访问下一个节点；从尾到头遍历时，使用 prev 引用来访问前一个节点。
查找操作：查找特定元素时，通常是从链表的一端开始遍历，直到找到目标元素或到达链表末尾。这与单向链表类似，但在某些情况下（如已知目标接近链表尾部），可以反向遍历以提高效率。

成员变量

LinkedList 的成员变量很简单，只有 3 个，如下：

// 当前链表中元素的数量
transient int size = 0;
// 链表的头节点
transient Node<E> first;
// 链表的尾节点
transient Node<E> last;

可以看到这 3 个成员变量都被 transient 关键字所修饰，我们知道，当一个变量被 transient 关键字修饰时，表示这个变量在序列化时是不参与到序列化过程当中的。LinkedList 之所以这样，是因为 LinkedList 与 ArrayList 一样，它的序列化机制是自定义的，并没有依赖于默认的序列化过程。

LinkedList 的序列化和反序列化过程也是由类内部的 writeObject 和 readObject 方法控制的。这些方法确保了只有实际的数据元素（即 Node 节点中的 item 字段）被序列化，而不是整个链表结构（包括 size、first 和 last 引用）。这样做可以减少序列化的数据量，提高效率，并且避免了复杂引用关系带来的问题。

在反序列化过程中，LinkedList 会根据序列化流中的元素重新构建链表结构，包括创建新的节点和更新 size、first 和 last 引用。因此，在序列化之后，这三个字段即使不参与序列化也可以通过读取序列化的元素来正确地恢复。

构造方法

LinkedList 提供了两种构造方法：

无参构造函数：初始化了一个新的空的 LinkedList 实例，即 size=0，并且 first 和 last 均为 null。

public LinkedList() {
}

带参数构造函数：接受一个 Collection<? extends E> 类型的集合作为参数，通过调用 addAll() 方法将集合中的所有元素添加到新的 LinkedList 实例中。

// 接受一个集合作为参数，创建一个新的 LinkedList 并添加该集合的所有元素。
public LinkedList(Collection<? extends E> c) {
    // 调用无参构造，初始化一个新的空链表
    this();
    // 将给定集合中的所有元素添加到新创建的链表中
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    // 调用重载版本的 addAll 方法，在索引为 size 的位置（即链表末尾）插入所有元素
    return addAll(size, c);
}

// 在指定索引位置插入指定集合的所有元素
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查提供的索引是否有效，确保它在合法范围内，否则抛出索引越界异常
    checkPositionIndex(index);

    // 将集合转换成数组，方便后续遍历
    Object[] a = c.toArray();
    // 获取将要插入的新元素数量
    int numNew = a.length;
    if (numNew == 0)
        // 如果没有元素需要插入，则直接返回 false
        returnfalse;

    // 定义两个节点引用，用于定位插入点前后的节点
    Node<E> pred, succ;
    if (index == size) { // 如果插入位置是在链表末尾
        // 插入位置之后没有节点，所以设置 succ 为 null
        succ = null;
        // pred 指向当前链表的最后一个节点
        pred = last;
    } else { // 如果插入位置不是在链表末尾
        // 找到插入位置处的节点，并将其赋值给 succ
        succ = node(index);
        // pred 指向插入位置之前的节点
        pred = succ.prev;
    }

    // 遍历待插入的元素数组
    for (Object o : a) {
        // 强制类型转换，将 Object 类型转换为目标类型 E
        @SuppressWarnings("unchecked") E e = (E) o;
        // 创建新的节点，它的 prev 指向前一个节点，next 指向 null
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null) // 如果插入的是第一个元素
            // 更新链表的头指针指向新创建的第一个节点
            first = newNode;
        else
            // 否则，更新前一个节点的 next 指针指向新创建的节点
            pred.next = newNode;
        // 更新 pred 为新创建的节点，以便下一次迭代时使用
        pred = newNode;
    }

    if (succ == null) { // 如果插入位置是在链表末尾
        // 更新链表的尾指针指向新创建的最后一个节点
        last = pred;
    } else { // 如果插入位置不在链表末尾
        // 新创建的最后一个节点的 next 指针指向原来的后继节点
        pred.next = succ;
        // 更新原来的后继节点的 prev 指针指向新创建的最后一个节点
        succ.prev = pred;
    }

    // 更新链表大小，增加新插入的元素数量
    size += numNew;
    // 记录链表结构修改次数
    modCount++;
    returntrue;
}

注意：

如果传入的集合为空，则生成的 LinkedList 也将为空。

该构造函数不会对传入集合中的元素进行深拷贝，也就是说，如果原始集合中的对象发生变更，LinkedList 中对应的元素也会受到影响（除非这些对象本身是不可变的）。

核心方法

LinkedList 的核心方法大约有以下几个，其它更高级的操作（如栈操作、队列操作等）通常都是调用这些基本方法来完成的。

linkFirst(E e)，将元素插入到链表头部

private void linkFirst(E e) {
    // 定义一个节点 f，指向头节点，在元素插入完成之后，f 表示第二个节点
    final Node<E> f = first;
    /**
     * 根据 Node 的构造函数 Node(Node<E> prev, E element, Node<E> next) 可以看出：
     * 创建了一个新的节点，这个节点的前节点引用为 null，后节点引用指向原来的头节点 f
     * 所以这个节点是一个新的头结点
     */
    final Node<E> newNode = new Node<>(null, e, f);
    // 更新链表的头指针指向新创建的节点
    first = newNode;
    if (f == null) // 如果原来的头节点为空（即链表为空）
        // 更新链表的尾指针也指向新创建的节点（链表中只有这一个元素，头尾节点都指向它）
        last = newNode;
    else
        // 否则，更新原来的头节点的前引用指针指向新创建的节点
        f.prev = newNode;
    // 增加链表元素计数
    size++;
    // 记录链表结构修改次数
    modCount++;
}

linkLast(E e)，将元素插入到链表尾部

// 这个方法的逻辑与头插时的逻辑相似
void linkLast(E e) {
    // 定义一个节点 l，指向尾节点，在元素插入完成之后，l 表示倒数第二个节点
    final Node<E> l = last;
    // 创建一个新的节点作为新的尾节点，前驱为原来的尾节点，后继为 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 更新链表的尾指针指向新创建的节点
    last = newNode;
    if (l == null) // 更新链表的尾指针指向新创建的节点
        // 更新链表的头指针也指向新创建的节点
        first = newNode;
    else
        // 否则，更新原来的尾节点的后继指针指向新创建的节点
        l.next = newNode;
    // 增加链表元素计数
    size++;
    // 记录链表结构修改次数
    modCount++;
}

linkBefore(E e, Node<E> succ)，在指定节点之前插入一个元素

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

E unlinkFirst(Node<E> f)，移除头节点

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;
    // 断开与后续节点的引用链接，帮助垃圾回收
    f.next = null; // help GC
    // 更新链表的头指针指向下一个节点
    first = next;
    if (next == null) // 如果下一个节点为空（即链表现在为空）
        // 更新链表的尾指针也为 null
        last = null;
    else
        // 否则，更新下一个节点的前驱指针为 null
        next.prev = null;
    // 减少链表元素计数
    size--;
    // 记录链表结构修改次数
    modCount++;
    // 返回被移除的元素
    return element;
}

E unlinkLast(Node<E> l)，移除尾节点

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 获取要移除的节点的数据项
    final E element = l.item;
    // 获取要移除节点的前一个节点
    final Node<E> prev = l.prev;
    // 清空要移除节点的数据项
    l.item = null;
    // 断开与前一个节点的引用链接，帮助垃圾回收
    l.prev = null; // help GC
    // 更新链表的尾指针指向前一个节点
    last = prev;
    if (prev == null) // 如果前一个节点为空（即链表现在为空）
        // 更新链表的头指针也为 null
        first = null;
    else
        // 否则，更新前一个节点的后继指针为 null
        prev.next = null;
    // 减少链表元素计数
    size--;
    // 记录链表结构修改次数
    modCount++;
    // 返回被移除的元素
    return element;
}

E unlink(Node<E> x)，移除指定的某个节点

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

Node<E> node(int index)，根据下标找到对应的节点（重点）。

虽然 LinkedList 是基于双向链表实现的，并不像数组那样直接支持通过下标快速访问元素，但是为了符合 List 接口规范，提供与 List 接口一致的行为，LinkedList 提供了支持按索引访问元素的功能。

Node<E> node(int index) {
    // assert isElementIndex(index);

    // 如果索引小于链表长度的一半，size >> 1 表示 size 的一半，也就是 size/2
    if (index < (size >> 1)) {
        // 从头节点开始遍历，每遍历一次把节点引用后移一位
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 下标大于或者等于 size 的一半，就从尾结点开始遍历，每遍历一次把节点引用前移一位
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

在 node(int index) 方法中，首先会检查 index 是否小于链表长度的一半 (size >> 1)。这样做是为了优化查找过程，因为在双向链表中，我们既可以从头开始向后遍历，也可以从尾部开始向前遍历。当 index 较小时，说明目标节点更靠近链表头部；而当 index 较大时，则说明目标节点更接近链表尾部。因此，通过比较 index 是否小于链表长度的一半，可以选择更短的路径来找到目标节点，从而减少不必要的遍历次数，提高效率。

到这里，LinkedList 核心方法的源码就介绍完毕了，每个方法的代码不是很长且逻辑清晰，本质都是在对链表的 Node 节点进行操作。

在 ArrayList 中，每当向集合中添加元素时，都会 check 一下当前数组是否能够存储新加入的元素，不能够存储的话就会触发扩容。而 LinkedList 没有扩容的概念，原因是它是基于节点实现的双向链表，所以每次添加元素的时候直接 new 一个节点即可。理论上，只要内存足够大，可以无限添加元素。

Fail-Fast

Fail-Fast 是 Java 集合框架中的一种错误检测机制，目的是帮助开发者尽早发现并发修改的问题。当一个集合对象被多个线程同时访问，并且至少有一个线程正在对该集合进行结构性修改（如添加或删除元素）时，如果此时有其他线程试图通过迭代器遍历该集合，则会触发 Fail-Fast 机制，通常是抛出 ConcurrentModificationException 异常。

对于 LinkedList 而言，它的 Fail-Fast 机制与 ArrayList 类似。每当创建一个新的迭代器实例时，迭代器都会记录下当前集合的修改次数（通过 modCount 变量跟踪）。之后，在每次调用 next() 或 previous() 等方法之前，迭代器都会检查集合的实际修改次数是否与预期值（expectedModCount）一致。如果不一致，即意味着自迭代器创建以来发生了未预期的结构性修改，迭代器就会立即抛出 ConcurrentModificationException，从而避免了潜在的数据不一致性问题。

因为在
你真的了解 ArrayList 吗？（下）中，对集合框架的 Fail-Fast 机制已经进行过详细介绍，这里不再赘述，感兴趣的小伙伴可以去看下之前的文章。

LinkedList 与 ArrayList 对比

LinkedList 和 ArrayList 是 Java 集合框架中两个非常重要的列表实现，也是我们开发中最常用的。通过对源码进行分析后，我们来看下它们两者之间的异同点。

数据结构

ArrayList：基于动态数组的数据存储结构，它的元素存储在一个连续的内存块中。当数组容量不足以容纳新增加的元素时，会触发扩容操作，创建一个新的更大的数组，并将原有元素复制过去。
LinkedList：实现了双向链表结构，每个节点包含前驱和后继指针以及一个实际存储的数据项。这种设计使 LinkedList 不需要像 ArrayList 那样管理固定大小的数组，因此它更适合于频繁插入和删除操作的场景。

性能特征

随机访问（get/set）：由于 ArrayList 底层基于动态数组，有索引机制，所以它可以提供 O(1) 的时间复杂度来进行随机访问；而 LinkedList 则需要从头或尾开始遍历链表以定位到指定位置，平均情况下为 O(n)，ArrayList 在这方面表现更优。
插入/删除（add/remove）：对于位于列表中间位置的操作，LinkedList 通常比 ArrayList 更有效率，因为前者只需要调整相邻节点之间的链接关系，而后者则可能涉及大量元素的移动。特别是在头部或尾部进行插入或删除时，LinkedList 的优势更加明显。

内存消耗

额外开销：ArrayList 在数组尾部预留了一定数量的闲置位置用于未来的增长，而 LinkedList 每个节点都需要额外的空间来保存前后两个方向上的引用信息。因此，在相同数量级下，LinkedList 的总体内存占用可能会高于 ArrayList。

使用场景

ArrayList：适用于需要频繁执行随机访问且较少发生插入或删除操作的应用程序。例如，数据缓存、数据展示等场合往往会选择 ArrayList 来保证高效的查询性能。
LinkedList：更适合那些对插入和删除操作有较高要求但不太关心随机访问速度的情况。比如实现队列、栈或者其他类型的缓冲区时，LinkedList 可以提供更好的灵活性。

LinkedList 作者 Joshua Bloch 指出，尽管 LinkedList 在理论上适合元素增删的场景，但在实际应用中，除非确实需要利用其双端队列特性，否则 ArrayList 通常是更好的选择，因为后者在大多数情况下提供了更优的整体性能，并且更加符合现代编程实践的需求。此外，LinkedList 并不支持快速随机访问，这意味着如果应用程序需要频繁通过索引访问元素，则应优先考虑 ArrayList 或其他更适合的数据结构。