15. LinkedList 如何优化插入删除操作的指针操作？

标准答案

LinkedList 作为双向链表，在插入和删除时主要依赖指针操作。为了提高效率，它会在头尾快速插入（O(1)），并在中间插入时根据 index 判断从头还是尾遍历，尽量减少遍历次数（O(n)）。此外，JDK 采用 懒删除策略，即删除节点时，仅调整前后指针，而不立刻清除对象引用，交由 GC 处理，从而降低操作开销。

答案解析

1. LinkedList 的指针结构

LinkedList 是双向链表，每个节点 (Node<E>) 由 item（存储数据）、next（指向下一个节点）、prev（指向前一个节点）组成。

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

• 插入时：只需改变前后节点的 next 和 prev 指针，不涉及大规模数据移动。
• 删除时：仅调整指针，不真正清理数据，降低 GC 压力（懒删除）。

2. 插入操作的优化

（1）尾部 / 头部插入（O(1)）

• 直接修改 first 或 last 指针，无需遍历。
• 代码示例（addFirst()）：

  private void linkFirst(E e) {
      final Node<E> f = first;
      final Node<E> newNode = new Node<>(null, e, f);
      first = newNode;
      if (f == null)
          last = newNode;
      else
          f.prev = newNode;
      size++;
  }
  

（2）中间插入（O(n)）

• 先根据 index 判断从头遍历还是从尾遍历，减少遍历次数：

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

• 减少遍历时间：如果 size = 1000，查询 index = 900，从尾部遍历只需 100 次，比从头遍历（900 次）快 9 倍。

（3）插入新节点

• 常规链表插入：

  private void linkBefore(E e, Node<E> succ) {
      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++;
  }
  

• 优化点：
  • 只操作局部指针，无需像 ArrayList 那样移动整个数组，提升性能。
  • 若 index 过大，可调整存储策略（如 Skip List 提高索引效率）。

3. 删除操作的优化

（1）懒删除策略

• LinkedList 删除时，不立即释放对象，而是仅调整指针，等待 GC 处理：

  private 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;
      if (next == null) 
          last = prev;
      else 
          next.prev = prev;
      size--;
  }
  

• 为什么不立即清除 x.item ？
  • 立即清除会增加 GC 负担，短时间内可能触发频繁回收。
  • 延迟到 GC 触发时，批量清理，减少 Stop-The-World 影响。

（2）头部 / 尾部删除（O(1)）

• 直接调整 first / last 指针，效率极高：

  private void unlinkFirst(Node<E> f) {
      final Node<E> next = f.next;
      first = next;
      if (next == null) 
          last = null;
      else 
          next.prev = null;
      size--;
  }
  

4. 进一步优化

1. 减少 index 访问开销

   • 改进策略：使用 TreeMap + LinkedList 组合（如 LRU 缓存），提升查询速度。
   • 示例：

     private Map<Integer, Node<E>> indexMap = new TreeMap<>();
     

   • 这样可以在 O(log n) 时间复杂度内获取 index 对应的 Node，避免 O(n) 遍历。

2. 合并多个删除请求

   • 批量删除：减少链表操作次数，提高吞吐量。
   • 示例：对于大量删除操作，采用 ArrayList 记录要删除的节点，统一处理：

     List<Node<E>> toDelete = new ArrayList<>();
     for (Node<E> node : list) {
         if (shouldDelete(node)) {
             toDelete.add(node);
         }
     }
     for (Node<E> node : toDelete) {
         list.remove(node);
     }
     

   • 优势：
     • 减少频繁 GC：避免删除后立即回收，提高 GC 效率。
     • 提高吞吐量：批量操作指针，降低 CPU 负担。

3. 结合 Skip List 结构

   • 在高并发环境，可以用 ConcurrentSkipListMap 替代 LinkedList，提升随机访问效率。
   • 例如 消息队列 或 缓存淘汰 场景。

常见错误

1. 误解 LinkedList 的删除是 O(1)
   • 正确： 头部、尾部删除是 O(1)，但中间删除仍然需要 O(n) 遍历。
2. 误认为 LinkedList 适用于所有插入场景
   • 正确： 仅在大量随机插入 / 删除时比 ArrayList 具有优势，但查询性能较低。

最佳实践

• 批量操作时，提前计算 index，减少遍历次数。
• 尽量避免 get(index)，用 Iterator 遍历，减少 O(n) 遍历消耗。
• 高并发场景下，避免 LinkedList，使用 ConcurrentLinkedDeque。

深入追问

• LinkedList 在 JVM 内存管理上的表现如何？
• ArrayDeque 为什么比 LinkedList 更适合作为队列？
• ConcurrentLinkedQueue 如何实现无锁链表？

相关面试题

• 为什么 LinkedList 适用于频繁插入删除，而 ArrayList 适用于随机访问？
• LinkedList 和 ConcurrentLinkedDeque 的区别是什么？