Java LinkedList双向链表实现原理详解

Java LinkedList底层基于无哨兵节点的双向链表实现，每个Node包含item、next和prev三个字段，通过first和last引用直接指向首尾节点；其add()和addLast()等首尾操作均为O(1)，但按索引插入或随机访问（如get(int)、add(int, E)、remove(int)）需O(n)遍历查找，性能远逊于ArrayList；常见误用如用get()遍历、取末尾元素或删除对象时未注意null处理与equals逻辑，极易引发严重性能陷阱——理解这一“首尾快、中间慢”的本质特性，才能避免在实际开发中踩坑。

LinkedList 的 Node 结构长什么样

Java 的 LinkedList 底层是双向链表，每个节点由内部静态类 Node 表示，它包含三个字段：item（存储元素）、next（指向后继节点）、prev（指向前驱节点）。没有额外的“头结点”或“哨兵节点”，但 first 和 last 两个引用分别指向链表首尾。

这意味着：空链表时 first == null && last == null；只有一个元素时 first == last，且它的 next == null、prev == null。

add() 和 addLast() 的实际行为差异

add(E e) 是 List 接口定义的方法，在 LinkedList 中它等价于 addLast(e) —— 即总是追加到尾部。这不是约定俗成，而是源码里直接调用的：

public boolean add(E e) {
    linkLast(e);
    return true;
}

而 addFirst(E e) 则调用 linkFirst(e)，会修改 first 引用并调整新节点的 next 指针。两者时间复杂度都是 O(1)，但如果你误以为 add() 是随机位置插入（像 ArrayList.add(int, E) 那样），就会出错。

• add(int index, E element) 才是按索引插入，它会先调用 node(int index) 查找目标位置 —— 这个查找是 O(n) 的，从头或尾开始遍历取决于 index 更靠近哪一端
• 频繁在中间位置 add(int, E) 或 remove(int)，性能远不如 ArrayList

为什么 get(int index) 比 ArrayList 慢得多

LinkedList.get(int index) 必须从 first 或 last 出发逐个跳转，无法像数组那样通过下标直接计算地址。源码中 node(int index) 会判断：if (index > 1)) 就从前向后找，否则从后向前找 —— 这只是把最坏情况从 n 降到 n/2，仍是 O(n)。

常见误用场景：

• 写 for (int i = 0; i 遍历 LinkedList
• 用 list.get(list.size() - 1) 取最后一个元素（应改用 list.getLast()）

这些操作本可以是 O(1)，却因用了 get() 变成 O(n)。

remove(Object o) 的遍历逻辑和 null 处理

remove(Object o) 会从头开始遍历，对每个节点的 item 调用 equals()。特别注意：当 o == null 时，它匹配的是 item == null 的节点，而不是跳过 null —— 这符合 Collection.remove() 规范。

源码关键片段：

for (Node x = first; x != null; x = x.next) {
    if (o == null ? x.item == null : o.equals(x.item)) {
        unlink(x);
        return true;
    }
}

这里容易踩的坑：

• 如果链表里有多个相同元素，只删第一个匹配项
• 如果元素类型没重写 equals()，默认用 == 比较引用，可能删不掉预期对象
• removeFirst() 和 removeLast() 是 O(1)，但 remove(Object) 是 O(n)，别混淆

双向链表的优势（O(1) 插入/删除首尾）和劣势（O(n) 随机访问）都源于同一个设计：每个节点只存前后引用，没有索引映射。用错场景时，性能落差比想象中更剧烈。

理论要掌握，实操不能落！以上关于《Java LinkedList双向链表实现原理详解》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！