12. LinkedList 为什么在插入删除时性能更优，但在大规模数据下查询性能较差？

标准答案

LinkedList 采用双向链表结构，每个节点存储数据和前后指针，因此插入和删除操作的时间复杂度为 O(1)，不涉及大规模数据迁移。但由于链表不支持随机访问，查询必须从头或尾部开始遍历，时间复杂度为 O(n)，在大规模数据下查询性能较差。

答案解析

1. LinkedList 的数据结构

LinkedList 采用 双向链表（Doubly Linked List） 作为底层存储结构：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

• 每个 Node 存储一个数据元素 item，并包含指向**前驱节点（prev）和后继节点（next）**的指针。
• LinkedList 只存储节点引用，不使用连续内存，避免了数组扩容带来的拷贝成本。

2. 插入和删除的时间复杂度为何是 O(1)？

在 ArrayList 中，中间插入或删除需要移动大量元素，而 LinkedList 仅修改前后节点的 next 和 prev 指针即可完成操作：

// 插入节点（示意代码）
newNode.prev = current;
newNode.next = current.next;
current.next.prev = newNode;
current.next = newNode;

因此，插入和删除操作的时间复杂度始终为 O(1)。

3. 为什么查询性能较差？

LinkedList 不支持随机访问，执行 get(index) 需要遍历链表：

public E get(int index) {
    if (index < (size >> 1)) { // 从头开始找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
    } else { // 从尾部开始找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
    }
}

为什么 get() 复杂度是 O(n)？

• 如果 index 靠近 head，从头开始遍历。
• 如果 index 靠近 tail，从尾部开始遍历。
• 平均查找复杂度 O(n/2) ≈ O(n)，远逊于 ArrayList 的 O(1)。

常见错误

1. 误以为 LinkedList 适合所有插入操作

   • 仅头部和尾部插入性能优异（O(1)），但中间插入仍需要 O(n) 遍历。

2. 误用 LinkedList 进行频繁查询

   • get(index) 在大规模数据下非常低效，应考虑 ArrayList 或 HashMap。

最佳实践

1. 适用于频繁插入删除的场景（如队列、缓存淘汰）：

   • Deque<Integer> deque = new LinkedList<>();
   • Queue<Integer> queue = new LinkedList<>();

2. 避免频繁查询，如果必须查询：

   • 方案 1：转换为 ArrayList

     List<Integer> arrayList = new ArrayList<>(linkedList);
     arrayList.get(index); // O(1) 查询
     

   • 方案 2：使用 HashMap 存储索引，提高查询速度。

深入追问

• 在 JVM 内存管理层面，LinkedList 会导致哪些额外开销？
• 为什么 Java 8 之后 ArrayDeque 更推荐用于队列，而非 LinkedList？

相关面试题

• 为什么 ArrayList 查询快但删除慢？
• LinkedList 如何基于 Deque 实现 LRU 缓存？