问题

3. LinkedList 的数据结构是什么？为什么它适用于插入操作频繁的场景？

标准答案

LinkedList 是 双向链表（Doubly Linked List），底层由 Node<E> 结点组成，每个结点包含 数据（item）、前驱指针（prev）、后继指针（next）。由于链表插入和删除元素时只需修改指针，不需要移动大量元素，因此在 插入和删除操作频繁 的场景下，比 ArrayList 更高效。但由于 链表不支持随机访问（O(n) 查找），访问远距离元素性能较差，所以不适用于频繁查找的场景。

答案解析

1. LinkedList 的底层数据结构

LinkedList 采用 双向链表 结构，每个元素封装在 Node<E> 结点中，结点定义如下（JDK 1.8）：

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 通过 first 和 last 指针维护链表的 头结点 和 尾结点：

transient Node<E> first; // 头结点
transient Node<E> last;  // 尾结点

• 双向链表特点：
  • 插入、删除操作 O(1)，仅需调整指针，无需大规模数据移动。
  • 查找操作 O(n)，需从 first 或 last 依次遍历，无法像 ArrayList 一样通过 O(1) 索引访问。

2. 为什么 LinkedList 适用于插入操作频繁的场景？

（1）插入元素的性能优势

• 在 ArrayList 中，插入元素时如果发生 数组扩容或中间插入，需要 O(n) 级别的元素移动，性能较差。
• LinkedList 只需 修改前后指针，插入 O(1)，适合 频繁插入 的场景。

插入操作示例（add(E e) 方法）：

public boolean add(E e) {
    linkLast(e); // 插入到链表尾部
    return true;
}

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

• 头部插入：调整 first 指针。
• 尾部插入：调整 last 指针。
• 中间插入：修改前后 prev/next 指针，避免 ArrayList 的数据搬移。

（2）删除元素的性能优势

• ArrayList 删除元素需要 O(n) 级别的移动，影响性能。
• LinkedList 删除仅需 修改前后指针，时间复杂度为 O(1)。

删除操作示例（remove(E e) 方法）：

void unlink(Node<E> x) {
    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;
}

• 只需修改 prev 和 next 指针，无需移动数据，避免 ArrayList 的大量 System.arraycopy() 调用。
• 适用于 链表队列、缓存淘汰（LRU）、频繁删除的场景。

3. LinkedList 的缺点

（1）查询性能较差（O(n）

• ArrayList 通过 数组索引 O(1) 访问 元素，而 LinkedList 需要 从头结点或尾结点遍历，平均时间复杂度 O(n)。
• 示例：查找第 5000 个元素时：
  • ArrayList：list.get(5000) 直接访问，O(1)。
  • LinkedList：需要从 first 或 last 遍历，O(n) 级别，查询性能远低于 ArrayList。

（2）空间开销大

• LinkedList 需要额外存储 prev / next 指针，每个结点的存储成本比 ArrayList 高。
• 示例：存储 100w 个 Integer 数据：
  • ArrayList：只需 100w * 4B = 4MB（连续存储）。
  • LinkedList：需要额外指针，空间开销 至少 2-3 倍。

（3）CPU 缓存命中率低

• ArrayList 元素存储在连续内存地址，CPU 预读取数据块，缓存利用率高。
• LinkedList 元素分散存储，导致 Cache Miss（缓存未命中），CPU 读取数据变慢。

最佳实践

• 适用于插入/删除频繁的场景

  • 消息队列（如 LinkedBlockingQueue）
  • 缓存淘汰策略（LRU）（如 LinkedHashMap）
  • 链表结构的 HashMap 桶（JDK 1.7 以前）

• 避免在索引访问频繁的场景使用

  • 避免 get(int index) 访问远距离元素
  • 若需要 频繁随机访问，请使用 ArrayList。

深入追问

1. 为什么 LinkedList 适用于 LRU 缓存？

• LinkedHashMap 继承自 HashMap，但维护了一个 双向链表，结合 removeEldestEntry() 方法，可以高效淘汰最近最少使用的数据（LRU 机制）。

2. 为什么 LinkedList 在 for-each 迭代时比 ArrayList 慢？

• for-each 本质上会调用 iterator.next()，而 LinkedList 需要 从前驱结点依次遍历，远比 ArrayList 直接索引访问慢。

3. LinkedList 为什么不适合作为 ArrayList 的底层？

• ArrayList 需要随机访问元素，而 LinkedList 只能顺序遍历，这与 ArrayList 设计理念不符。

相关面试题

• LinkedList 和 ArrayList 的性能对比？
• LinkedList 在 JVM 内存管理上的影响？
• LinkedList 适合哪些实际业务场景？
• LinkedList 和 ConcurrentLinkedQueue 的区别？