LinkedList源码 双向链表 ArrayList和LinkedList区别 Java集合选型

基础不牢，地动山摇。

上一期我们彻底搞懂了 ArrayList 底层数组：

查询快、中间增删慢、需要扩容、底层连续内存。

那既然数组有增删慢的短板，Java靠什么弥补？

答案就是今天的主角：LinkedList 双向链表。

很多时候我们在工作中最大的问题：永远凭感觉乱选集合。

看完这篇，你彻底弄懂：

✅ 为什么 LinkedList 增删快？

✅ 为什么 LinkedList 查询慢？

✅ 业务场景到底该用 ArrayList 还是 LinkedList？

全程大白话 + 极简源码 + 精准对比，零基础也能彻底通透。

一、一句话看懂 LinkedList 底层

ArrayList：底层是「数组」

LinkedList：底层是「双向链表」

不用连续内存，每一个元素都是一个独立节点。

每个节点只记录三件事：

• 自己的元素数据
• 上一个节点地址
• 下一个节点地址

通俗比喻：

ArrayList 像一排紧密连坐的座位，中间走人，后面所有人都要往前挪。

LinkedList 像一串珍珠项链，拆掉中间一颗、插入一颗，只需要断开两边绳子，其他珍珠完全不用动。

二、 先看家谱：LinkedList 到底是个啥？

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

重点看两个：

它有几个特点：

• 底层是双向链表，不是数组。
• 允许 null。
• 非线程安全。
• 没有容量概念，不需要扩容。
• 每个元素都会被包装成一个 Node 节点。

你可以把它想象成一群手拉手的小朋友：

null <- A <-> B <-> C -> null
first last

每个小朋友都知道：

• 我前面是谁：prev
• 我后面是谁：next
• 我自己手里拿的是什么：item

三、底层节点源码（极简核心： 三个成员 + 一个 Node）

LinkedList 最核心的成员只有三个：

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

• size：链表里有多少个元素。
• first：头节点。
• last：尾节点。

每个节点长这样（LinkedList 所有元素，都是下面这个 Node 节点）：

// 双向链表节点
private static class Node<E> {
E item; // 当前元素
Node<E> next; // 下一个节点
Node<E> prev; // 上一个节点
}

翻译成人话：

Node = 当前元素 + 前一个节点 + 后一个节点

所以 LinkedList 的每个元素，都要额外维护两个引用：prev 和 next。

这也是它内存开销大的原因。

这就是双向链表的精髓：前后互通。

所以它可以从头遍历、也可以从尾遍历，增删只需要改引用，不需要移动大量元素。

四、添加元素源码：改指针的艺术（增加为什么比 ArrayList 快）

1. 尾部添加：add(E e)

平时我们最常用的：

list.add("A");

源码最终会走到：

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

linkLast 是尾部插入核心：

void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;

if (l == null)
first = newNode;
else
l.next = newNode;

size++;
modCount++;
}

步骤拆解：

所以尾部添加是 O(1) ，因为不用遍历，直接改尾巴。

2. 头部添加：addFirst(E e)

public void addFirst(E e) {
linkFirst(e);
}

核心：

private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;

if (f == null)
last = newNode;
else
f.prev = newNode;

size++;
modCount++;
}

逻辑和尾部插入对称：

• 新节点的 next 指向原来的头。
• 原来的头 prev 指向新节点。
• first 变成新节点。

所以头部添加也是 O(1) 。

3. 指定位置插入：add(int index, E element)

public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}

注意这里有个关键点：

• 如果 index == size，直接在尾部插入，O(1)。
• 否则，先调用 node(index) 找到这个位置的节点，再在它前面插入。

node(index) 是 LinkedList 慢的根源之一。

五、查询源码：node(index) 是灵魂

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

size >> 1 就是 size / 2。

意思很简单：

• 如果下标在前半段，从 first 往后找。
• 如果下标在后半段，从 last 往前找。

这是一个小优化，但改变不了本质：

LinkedList 随机访问仍然是 O(n)。

比如找第 5000 个元素，即使从中间开始，也要走几千步。

所以：

public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

get(index) 是 O(n)。

set(index, element) 也一样：

public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}

先找到节点，再改值。

没有连续下标，想找第 n 个元素：只能从头节点/尾节点挨个遍历，直到找到目标，速度极慢 O(n)

六、删除源码：unlink 断链（删除为什么比 ArrayList 快）

1. 按下标删除

public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

先 node(index) 找到节点，再 unlink 删除。

unlink 是删除的核心：

E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size–;
modCount++;
return element;
}

翻译一下：

• 如果删除的是头节点，first 往后移。
• 如果删除的是尾节点，last 往前移。
• 如果是中间节点，让前一个的 next 指向后一个，后一个的 prev 指向前一个。
• 把被删除节点的 item、prev、next 置空，帮助 GC 回收。

所以：

• 删除头尾：O(1)。
• 按下标删除：先 node(index)，O(n)，再改指针 O(1)，总体 O(n)。

2. 删除对象

public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}

从头遍历，找到就删。所以也是 O(n)。

七、LinkedList 还能当队列和栈

因为它实现了 Deque，所以有很多方法：

比如当队列：

LinkedList<String> queue = new LinkedList<>();
queue.offer("A"); // 入队
queue.offer("B");
String head = queue.poll(); // 出队

当栈：

LinkedList<String> stack = new LinkedList<>();
stack.push("A");
stack.push("B");
String top = stack.pop();

不过实战里，如果只是当队列或栈，ArrayDeque 通常比 LinkedList 更快、更省内存。LinkedList 的优势是它同时实现了 List 和 Deque。

八、遍历 LinkedList 的正确姿势

这是 LinkedList 最大的坑。

错误写法：

for (int i = 0; i < list.size(); i++) {
E e = list.get(i); // 每次 get 都 O(n)
}

这样总复杂度是 O(n²) ，数据一多就慢到怀疑人生。

正确写法：

for (E e : list) {
// 底层用迭代器，O(n)
}

或者：

Iterator<E> it = list.iterator();
while (it.hasNext()) {
E e = it.next();
if (要删除) {
it.remove(); // LinkedList 迭代器删除是 O(1)
}
}

LinkedList 的迭代器 ListItr 内部持有 next 指针，每次 next() 只是往后走一步，所以遍历是 O(n)。

而且迭代器删除只需要改指针，不需要像 ArrayList 那样移动数组。

九、新增/删除为什么比 ArrayList 快？查询为什么比ArrayList慢？

ArrayList 增删（中间位置）

底层数组连续内存：

一旦中间删除/插入元素，后面所有元素必须批量移位。

LinkedList 增删

这就是链表增删快的核心原因！

很多人会疑惑：既然链表增删快，为什么不全部用 LinkedList？

因为它有致命短板：不支持随机访问。

ArrayList 查询

数组有下标，get(index) 直接定位内存地址，一步到位 O(1)

LinkedList 查询

没有连续下标，想找第 n 个元素：

只能从头节点/尾节点挨个遍历，直到找到目标，速度极慢 O(n)

十、终极对比：ArrayList VS LinkedList

1. 底层结构

ArrayList：动态数组、连续内存

LinkedList：双向链表、分散节点内存

2. 查询速度

ArrayList：极快（支持下标随机访问）

LinkedList：慢（必须遍历查找）

3. 中间增删速度

ArrayList：慢（大量元素移位+扩容拷贝）

LinkedList：快（只改引用指向）

4. 内存占用

ArrayList：节省内存（只存数据）

LinkedList：占用高（每个节点多两个指针地址）

5. 线程安全

两者都是：非线程安全

十一、业务场景选型（万能公式）

✅ 优先用 ArrayList

• 大部分业务场景：列表展示、数据查询、遍历
• 查询多、增删少
• 日常开发 95% 的场景都用它

✅ 优先用 LinkedList

• 频繁中间插入、频繁删除数据
• 做队列、栈结构、频繁头尾操作

十二、超级大坑（90%人踩过）

很多教程说：增删多用 LinkedList

⚠️ 注意：末尾新增不算！

ArrayList 末尾 add 几乎不用移位，速度非常快。

只有中间位置高频增删，才需要 LinkedList。

盲目替换集合，反而会让代码性能更差。

十三、专栏总结

欢迎点赞收藏关注，下一期继续更新：HashMap 零基础入门，看懂哈希表底层，新手最容易忽略的异常知识点。