Java链表操作实战解析

Java中的LinkedList虽常被当作ArrayList的替代品，实则专为高频首尾增删场景而生——其addFirst()、removeLast()等双端操作均为O(1)，天然适配栈、队列及滚动缓存等需求；但若误用于随机访问（如循环中调用get(i)），性能将骤降至O(n²)，成为隐蔽的性能杀手；更需警惕的是，它作为List接口实现易被滥用，而官方更推荐ArrayDeque来实现队列/栈（除非需要null支持或List特有方法）；真正用好LinkedList，关键在于跳出“链表=通用列表”的思维定式，清醒识别其双端队列本质与迭代安全边界。

频繁在头部或尾部增删元素时用 LinkedList

LinkedList 底层是双向链表，addFirst()、addLast()、removeFirst()、removeLast() 都是 O(1) 时间复杂度。相比 ArrayList 在首尾插入/删除要移动大量元素，这里优势明显。

常见适用场景：

• 实现栈（用 push()/pop()，本质是 addFirst()/removeFirst()）
• 实现队列（用 offer()/poll()，底层调 addLast()/removeFirst()）
• 需要滚动缓存（如最近 N 条日志），持续 addLast() + removeFirst() 维护固定长度

随机访问下标操作要特别小心

get(int index) 在 LinkedList 中是 O(n) —— 它必须从头或尾开始遍历找到目标节点，不会像 ArrayList 那样直接数组寻址。哪怕只是写 list.get(0) 或 list.get(list.size()-1)，虽然实际很快，但语义上仍是遍历，JVM 不会优化成常量时间。

容易踩的坑：

• 循环里写 for (int i = 0; i → 实际变成 O(n²)，性能断崖式下跌
• 误以为 list.get(size/2) 是“中间访问”，结果触发近半链表遍历
• 和 ArrayList 混用习惯，没意识到 get() 成了性能瓶颈

作为 Deque 接口实现比作为 List 更典型

Java 官方文档明确建议：如果只用作队列或栈，优先用 ArrayDeque（性能更好、内存更省）；但如果确实需要双端队列行为且允许 null 元素、或需 List 接口的某些方法（如 listIterator()），才选 LinkedList。

关键差异点：

• ArrayDeque 不支持 null，LinkedList 支持
• ArrayDeque 的 addFirst()/addLast() 平均 O(1)，扩容时有摊还成本；LinkedList 每次新增都 new Node，对象分配开销略高
• LinkedList 实现了 List 和 Deque 双接口，能被当成 List 传参，但多数 List 场景它反而不是最优解

迭代器遍历时注意 modCount 失效风险

LinkedList 的迭代器是 fail-fast 的，但因为是链表结构，remove() 迭代中调用 iterator.remove() 是安全的；而直接调 list.remove(obj) 会导致 ConcurrentModificationException，哪怕单线程。

正确写法示例：

LinkedList list = new LinkedList<>(Arrays.asList("a", "b", "c"));
Iterator it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if ("b".equals(s)) {
        it.remove(); // ✅ 安全
    }
}

错误写法：

for (String s : list) {
    if ("b".equals(s)) {
        list.remove(s); // ❌ 抛 ConcurrentModificationException
    }
}

这点比 ArrayList 更容易误踩——因为 LinkedList 的 remove(Object) 要遍历查找，看起来“只是删一个”，却悄悄破坏了迭代器状态。

链表结构本身不难理解，难的是在 List 和 Deque 两种角色间做清醒选择；多数人用错，不是因为不会写，而是默认把它当成了“另一个 ArrayList”。

好了，本文到此结束，带大家了解了《Java链表操作实战解析》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！