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

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

时间复杂度分析

1. 最佳情况：O(1)，索引靠近 first 或 last 时直接返回。
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] <-> [3] <-> [4] <-> [5]

• 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(); // 仅遍历一次
   

3. 转换为 ArrayList 进行查询，若数据量较大，查询密集，可转为 ArrayList：

   List<Integer> list = new ArrayList<>(linkedList);
   Integer value = list.get(index); // O(1)
   

   转换成本 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. 为什么 LinkedList 从 first 或 last 遍历？
   • 降低平均遍历步数：从 first 或 last 遍历 最多 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) 访问？
• LinkedList 的 iterator 和 get(index) 有何区别？