# 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;
    }
}
1
2
3
4
5
6
7
8
9
10
  • 插入时:只需改变前后节点的 nextprev 指针,不涉及大规模数据移动。
  • 删除时:仅调整指针,不真正清理数据,降低 GC 压力(懒删除)。

# 2. 插入操作的优化

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

  • 直接修改 firstlast 指针,无需遍历。
  • 代码示例(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++;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10

(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;
        }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
  • 减少遍历时间:如果 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++;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
  • 优化点
    • 只操作局部指针,无需像 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--;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
  • 为什么不立即清除 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--;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9

# 4. 进一步优化

  1. 减少 index 访问开销

    • 改进策略:使用 TreeMap + LinkedList 组合(如 LRU 缓存),提升查询速度。
    • 示例
      private Map<Integer, Node<E>> indexMap = new TreeMap<>();
      
      1
    • 这样可以在 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);
      }
      
      1
      2
      3
      4
      5
      6
      7
      8
      9
    • 优势
      • 减少频繁 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 适用于随机访问?
  • LinkedListConcurrentLinkedDeque 的区别是什么?