# 问题

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

整个 LinkedList 通过 firstlast 指针维护链表的 头结点尾结点

transient Node<E> first; // 头结点
transient Node<E> last;  // 尾结点
1
2
  • 双向链表特点
    • 插入、删除操作 O(1),仅需调整指针,无需大规模数据移动。
    • 查找操作 O(n),需从 firstlast 依次遍历,无法像 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 头部插入:调整 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  • 只需修改 prevnext 指针,无需移动数据,避免 ArrayList 的大量 System.arraycopy() 调用。
  • 适用于 链表队列、缓存淘汰(LRU)、频繁删除的场景

# 3. LinkedList 的缺点

# (1)查询性能较差(O(n)
  • ArrayList 通过 数组索引 O(1) 访问 元素,而 LinkedList 需要 从头结点或尾结点遍历,平均时间复杂度 O(n)
  • 示例:查找第 5000 个元素时:
    • ArrayListlist.get(5000) 直接访问,O(1)。
    • LinkedList:需要从 firstlast 遍历,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. 为什么 LinkedListfor-each 迭代时比 ArrayList 慢?

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

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

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

# 相关面试题

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