# 8. LinkedList 随机访问分析

# 标准答案

LinkedList 底层是 双向链表,不支持数组的 随机访问,获取元素时必须从头(或尾)开始遍历,直到找到目标索引。因此,get(index) 的时间复杂度是 O(n),相比 ArrayList 的 O(1) 随机访问,性能较差。如果 index 接近 头部或尾部LinkedList 会选择从 较近的一端 遍历,优化访问性能,但仍然是线性复杂度。

# 答案解析

# JDK 18 源码解析

public E get(int index) {
    checkElementIndex(index); // 检查索引是否越界
    return node(index).item;
}

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
14
15
16
17
18

LinkedList 采用 双向链表 结构,每个节点包含 prevnext 指针,没有索引映射关系,因此 无法 O(1) 访问任意位置元素,而是必须通过遍历找到对应节点。

# 时间复杂度分析

  1. 最佳情况:O(1),索引靠近 firstlast 时直接返回。
  2. 最坏情况:O(n),索引接近 size / 2 时,需要遍历 n/2 个节点。
  3. 平均情况:O(n),查询 get(index) 平均遍历 n/2 步。

示例:

LinkedList<Integer> list = new LinkedList<>(List.of(1, 2, 3, 4, 5));
list.get(3); // 从尾部遍历更快
1
2

链表结构如下:

[1] <-> [2] <-> [3] <-> [4] <-> [5]
1
  • get(0):O(1),直接返回 first.item
  • get(3):O(2),索引 3 > size/2=2.5,从 last 向前遍历两步。
  • get(2):O(2),索引 2 < size/2=2.5,从 first 向后遍历两步。

# 为什么 LinkedList.get(index) 不能做到 O(1)?

  1. 底层是链表,无法直接索引
    ArrayList 通过 array[index] 直接访问元素,而 LinkedList 只能 遍历链表 逐个访问节点。
  2. 不适合缓存索引
    LinkedList 设计为 动态插入删除 友好,若增加索引缓存,会增加插入删除成本。
  3. 没有哈希索引优化
    例如 TreeMap 通过 红黑树 结构加速查询,但 LinkedList 只提供顺序访问。

# 如何优化 LinkedList.get(index) 性能?

  1. 避免 LinkedList 频繁 get(index),若需频繁查询,使用 ArrayList 替代。
  2. 使用 ListIterator,可减少重复遍历:
    ListIterator<Integer> it = linkedList.listIterator();
    for (int i = 0; i < targetIndex; i++) {
        it.next();
    }
    Integer value = it.next(); // 仅遍历一次
    
    1
    2
    3
    4
    5
  3. 转换为 ArrayList 进行查询,若数据量较大,查询密集,可转为 ArrayList
    List<Integer> list = new ArrayList<>(linkedList);
    Integer value = list.get(index); // O(1)
    
    1
    2
    转换成本 O(n),但后续查询 O(1)。

# 适用场景对比

场景 ArrayList LinkedList
随机访问 (get(index)) ✅ O(1) ❌ O(n)
头部插入删除 ❌ O(n) ✅ O(1)
尾部插入删除 ✅ O(1) ✅ O(1)
大量插入删除 ❌ 需要移动元素 ✅ 只需修改指针
迭代遍历 ✅ 快,CPU 缓存友好 ❌ 需频繁跳指针

# 深入追问

  1. 为什么 LinkedList.get(index) 不能使用哈希表加速?
    LinkedList有序结构,不支持哈希索引。如果维护哈希索引,会导致 插入删除操作额外维护索引,影响插入性能。
  2. LinkedList.get(index) 为何不缓存中间结果?
    LinkedList 设计为 流式(stream-like)数据结构,没有 索引缓存,但 ListIterator 能减少重复遍历,建议替代 get(index)
  3. 为什么 LinkedListfirstlast 遍历?
    • 降低平均遍历步数:从 firstlast 遍历 最多 O(n/2) 次,而不是 O(n)
    • 如果总是从 first 遍历get(size-1) 变为 O(n),效率更低。

# 相关面试题

  • 为什么 ArrayList.get(index) 是 O(1),LinkedList.get(index) 是 O(n)?
  • LinkedList.get(index) 能优化到 O(1) 吗?为什么?
  • 什么时候应当使用 LinkedList 而不是 ArrayList
  • LinkedList 为什么不适用于频繁 get(index) 访问?
  • LinkedListiteratorget(index) 有何区别?