JTechVault

Appearance

LinkedList 性能分析：什么时候 LinkedList 最快 ​

一句话总结 ​

LinkedList 的核心优势是头尾操作 O(1) 和迭代器删除 O(1)，劣势是按索引访问 O(n)。

性能特点一览 ​

操作时间复杂度说明
头部操作 addFirst() / removeFirst()O(1)只需改头指针
尾部操作 addLast() / removeLast()O(1)只需改尾指针
按索引获取 get(i)O(n)需遍历链表
按索引插入 add(i, e)O(n)需先找到位置
按索引删除 remove(i)O(n)需先找到位置
迭代器删除 it.remove()O(1)已有节点引用
contains / indexOfO(n)需遍历查找

性能实测 ​

java
import java.util.*;

public class LinkedListPerformanceDemo {

    public static void main(String[] args) {
        int size = 100_000;

        // 1. 头部插入
        System.out.println("=== 头部插入 ===");
        System.out.println("LinkedList: " + measure(() -> {
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                list.addFirst(i);
            }
        }));
        System.out.println("ArrayList: " + measure(() -> {
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                list.add(0, i); // ArrayList 头部插入 O(n)
            }
        }));

        // 2. 尾部插入
        System.out.println("\n=== 尾部插入 ===");
        System.out.println("LinkedList: " + measure(() -> {
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                list.addLast(i);
            }
        }));
        System.out.println("ArrayList: " + measure(() -> {
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                list.add(i);
            }
        }));

        // 3. 中间插入（用迭代器）
        System.out.println("\n=== 中间插入（迭代器） ===");
        System.out.println("LinkedList: " + measure(() -> {
            LinkedList<Integer> list = new LinkedList<>();
            list.add(0); // 先加一个元素
            ListIterator<Integer> it = list.listIterator();
            for (int i = 0; i < size; i++) {
                it.next();
                it.add(i);
            }
        }));
    }

    static String measure(Runnable r) {
        long start = System.nanoTime();
        r.run();
        return (System.nanoTime() - start) / 1_000_000 + " ms";
    }
}

典型结果（10 万元素）：

=== 头部插入 ===
LinkedList: ~8 ms      ← 极快
ArrayList: ~3000 ms    ← 极慢（每次都要移动所有元素）

=== 尾部插入 ===
LinkedList: ~10 ms
ArrayList: ~12 ms     ← 两者差不多

=== 中间插入（迭代器）===
LinkedList: ~15 ms     ← 迭代器方式，O(1) 插入

真正的 O(1) 操作 ​

LinkedList 真正快的地方是头尾操作和迭代器增删：

头尾操作 ​

java
LinkedList<Integer> list = new LinkedList<>();

// 头部：O(1)
list.addFirst(1);
list.removeFirst();
list.getFirst();

// 尾部：O(1)
list.addLast(2);
list.removeLast();
list.getLast();

迭代器遍历 + O(1) 删除 ​

java
LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C", "D"));

// ❌ 按索引删除 O(n)
list.remove(2); // 需要先遍历到索引 2

// ✅ 迭代器删除 O(1)
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("B")) {
        it.remove(); // O(1) 删除
    }
}

致命弱点：按索引访问 ​

java
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);
}

// ❌ 极慢
int value = list.get(500_000); // O(n)，遍历 50 万元素

// ✅ 正确方式：用迭代器遍历
Iterator<Integer> it = list.iterator();
int value = 0;
for (int i = 0; i < 500_000; i++) {
    value = it.next();
}

LinkedList vs ArrayList 按索引访问对比 ​

ArrayList get(500000)：~0.0001 ms（一步到位）
LinkedList get(500000)：~25 ms（遍历 50 万元素）
差距：25 万倍！

CPU 缓存不友好 ​

LinkedList 的节点在内存中是分散存储的：

ArrayList：连续内存
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ F │ G │ H │
└───┴───┴───┴───┴───┴───┴───┴───┘
  │ ← CPU 读取 A 时，可能把 B C D E ... 都预加载到缓存

LinkedList：分散内存
┌────┐    ┌────┐    ┌────┐    ┌────┐
│Node│───▶│Node│───▶│Node│───▶│Node│
│  A │    │  B │    │  C │    │  D │
└────┘    └────┘    └────┘    └────┘
 ↑        ↑
每次都要去内存里找下一个节点

适用场景总结 ​

✅ LinkedList 擅长的 ​

java
// 场景1：双端队列（头尾操作）
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);   // O(1)
deque.addLast(2);     // O(1)

// 场景2：栈
Deque<String> stack = new LinkedList<>();
stack.push("task1");
stack.push("task2");
stack.pop(); // O(1)

// 场景3：迭代器遍历时频繁增删
Iterator<E> it = list.iterator();
while (it.hasNext()) {
    E e = it.next();
    if (shouldRemove(e)) {
        it.remove(); // O(1)
    }
}

❌ LinkedList 不擅长的 ​

java
// 场景1：按索引随机访问
list.get(5000); // ❌ O(n)

// 场景2：频繁的头部插入但不用迭代器
for (int i = 0; i < n; i++) {
    list.add(0, item); // ❌ 每次都要先遍历到位置 0

    // ✅ 改用 addFirst
    list.addFirst(item);
}

// 场景3：单纯的遍历
for (String s : linkedList) { // ❌ 慢
    process(s);
}
// ✅ 改用 ArrayList

ArrayDeque 替代 LinkedList 做队列/栈 ​

ArrayDeque 比 LinkedList 做队列和栈快 3-4 倍，内存占用也更少：

java
// ✅ ArrayDeque（推荐）：比 LinkedList 快
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);

// ✅ LinkedList：通用双端队列
Deque<Integer> linked = new LinkedList<>();

// ❌ Stack：已过时
Stack<Integer> old = new Stack<>();

性能对比（10 万元素尾部追加）：

ArrayDeque: ~5 ms
LinkedList: ~18 ms
Stack: ~20 ms

选型一句话 ​

LinkedList 适合用迭代器思考，ArrayList 适合用索引思考。队列/栈首选 ArrayDeque。

相关链接 ​

基于 VitePress 构建

Copyright © 2025-2026 JTechVault