在Java里LinkedList底层如何实现_Java双向链表原理说明

P粉602998670 2026-01-25 00:00:00 次阅读

LinkedList的Node含item、next、prev三个字段，无哨兵节点；add(E)等价于addLast(E)，时间复杂度O(1)；add(int,E)需O(n)查找位置，故频繁中间增删性能远低于ArrayList。

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

这里容易踩的坑：