LinkedList 与双向链表 | JavaSE

LinkedList 与双向链表

一、学习目标

完成本章学习后，你应该能够：

  • 能够解释 LinkedList 与 ArrayList 在底层数据结构上的核心区别。
  • 能够解释双向链表（Doubly Linked List）中结点、前驱引用和后继引用之间的关系。
  • 能够熟练使用 LinkedList 的常用 List API 和首尾操作 API。
  • 能够解释为什么 LinkedList 首尾增删效率较高，而按索引随机访问效率较低。
  • 能够根据查询、遍历、首尾操作、随机访问等业务特征选择 ArrayList 或 LinkedList。
  • 能够避免“LinkedList 增删永远比 ArrayList 快”这类过度简化的结论。

二、核心知识

2.1 LinkedList 是什么

LinkedList<E> 是 Java 集合框架中 List 接口的重要实现类。

LinkedList<String> list = new LinkedList<>();

从使用层面看，它仍然属于 List 家族，因此具有 List 的基本特点：

  • 有序：元素按照插入顺序保存。
  • 可重复：允许保存相同元素。
  • 有索引语义：可以通过 get(index)、set(index, element) 等方法按位置操作元素。

例如：

LinkedList<String> list = new LinkedList<>();

list.add("Java");
list.add("MySQL");
list.add("Java");

System.out.println(list);

集合中可以同时保存两个 "Java"。

但是，LinkedList 与上一章学习的 ArrayList 最大的区别，不在于 API，而在于底层数据结构。

2.2 LinkedList 的底层是双向链表

ArrayList 底层主要基于数组。

而 LinkedList 底层基于：

双向链表（Doubly Linked List）

可以先把一个链表结点抽象为：

┌────────┬─────────┬────────┐
│  prev  │  item   │  next  │
└────────┴─────────┴────────┘

一个结点主要需要保存三部分信息：

  • 当前结点保存的数据；
  • 指向前一个结点的引用；
  • 指向后一个结点的引用。

假设 LinkedList 中保存：

Java → MySQL → Spring

它在逻辑上更接近：

null
  ↑
[Java] ⇄ [MySQL] ⇄ [Spring]
                       ↓
                      null

更加完整地表示：

first
  ↓
┌────────┐    ┌────────┐    ┌────────┐
│ Java   │ ⇄ │ MySQL  │ ⇄ │ Spring │
└────────┘    └────────┘    └────────┘
                                  ↑
                                 last

前一个结点可以找到后一个结点，后一个结点也可以找到前一个结点，因此称为双向链表。

2.3 为什么叫“链表”

数组中的元素通常存放在连续的存储区域中，可以直接根据索引计算元素所在位置。

链表则不是依靠“连续位置”组织元素，而是依靠：

结点之间的引用关系

把一个个结点“串起来”。

例如：

结点A.next → 结点B
结点B.next → 结点C

双向链表进一步增加：

结点B.prev → 结点A
结点C.prev → 结点B

于是整个数据结构就像一条双向连接起来的链。

2.4 LinkedList 同时具有 List 与 Deque 能力

LinkedList 不仅实现了 List，还实现了 Deque。

Deque：

Double Ended Queue，双端队列。

因此 LinkedList 不仅可以像普通 List 一样操作：

list.add("Java");
list.get(0);
list.set(0, "JavaSE");
list.remove(0);

还特别擅长操作：

  • 第一个元素；
  • 最后一个元素。

例如：

list.addFirst("A");
list.addLast("B");

list.getFirst();
list.getLast();

list.removeFirst();
list.removeLast();

这也是 LinkedList 最有代表性的使用方式之一。

2.5 LinkedList 与 ArrayList 的核心区别

| 对比项 | ArrayList | LinkedList | | -------------------- | ------------------------ | ------------------ | | 底层结构 | 动态数组 | 双向链表 | | 按索引随机访问 | 快 | 较慢 | | 尾部添加 | 通常很快 | 很快 | | 首部添加 | 通常需要移动元素 | 很快 | | 首部删除 | 通常需要移动元素 | 很快 | | 中间插入删除 | 可能移动数组元素 | 找到结点后修改链接 | | 内存局部性 | 较好 | 较差 | | 每个元素额外引用开销 | 较少 | 较大 | | 典型场景 | 查询、遍历、普通业务列表 | 频繁首尾操作 |

因此不能简单记忆：

ArrayList：查询快，增删慢
LinkedList：查询慢，增删快

这句话只能作为入门阶段的粗略印象，不能作为最终结论。

真正需要分析的是：

在什么位置进行什么操作。

三、使用方法

3.1 创建 LinkedList

需要导入：

import java.util.LinkedList;

创建：

LinkedList<String> list = new LinkedList<>();

也可以使用多态：

List<String> list = new LinkedList<>();

但是存在一个重要区别。

如果声明为：

List<String> list = new LinkedList<>();

那么变量暴露的是 List 接口规定的能力。

如果你需要使用 LinkedList / Deque 特有的首尾 API：

addFirst()
addLast()
removeFirst()
removeLast()

通常直接声明：

LinkedList<String> list = new LinkedList<>();

或者：

Deque<String> deque = new LinkedList<>();

应根据程序真正需要的抽象能力选择变量类型。

3.2 LinkedList 可以使用 List 的所有常用 API

例如：

LinkedList<String> list = new LinkedList<>();

list.add("Java");
list.add("MySQL");
list.add("Spring");

System.out.println(list.get(0));

list.set(1, "Redis");

list.remove(2);

System.out.println(list);

LinkedList 仍然是 List，因此上一章学习的：

add()
add(index, element)
remove(index)
remove(Object)
set()
get()
size()
contains()

等 API 都可以继续使用。

3.3 LinkedList 的六个重要首尾操作

学习 LinkedList 时，下面六个 API 应重点掌握。

addFirst()

向链表头部添加元素。

list.addFirst("Java");

addLast()

向链表尾部添加元素。

list.addLast("Spring");

普通：

list.add("Spring");

对于 LinkedList 来说，本质上也是向尾部添加。

getFirst()

获取第一个元素，但不删除。

String first = list.getFirst();

getLast()

获取最后一个元素，但不删除。

String last = list.getLast();

removeFirst()

删除并返回第一个元素。

String first = list.removeFirst();

removeLast()

删除并返回最后一个元素。

String last = list.removeLast();

因此可以总结为：

| API | 作用 | | --------------- | ------------------ | | addFirst(E e) | 头部添加 | | addLast(E e) | 尾部添加 | | getFirst() | 获取头部元素 | | getLast() | 获取尾部元素 | | removeFirst() | 删除并返回头部元素 | | removeLast() | 删除并返回尾部元素 |

3.4 完整案例：任务队列

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> tasks = new LinkedList<>();

        tasks.addLast("写需求文档");
        tasks.addLast("编写代码");

        // 突然来了一个紧急任务
        tasks.addFirst("紧急修复 Bug");

        System.out.println(tasks);

        System.out.println("第一个任务：" + tasks.getFirst());
        System.out.println("最后一个任务：" + tasks.getLast());

        String finished = tasks.removeFirst();

        System.out.println("完成任务：" + finished);
        System.out.println("剩余任务：" + tasks);
    }
}

这个案例中：

addFirst()

非常适合表达：

紧急任务插入队首。

而：

addLast()

适合表达：

普通任务进入队尾。

这比直接使用索引：

add(0, element)

更容易表达代码真实意图。

3.5 空 LinkedList 的首尾操作

需要特别注意：

LinkedList<String> list = new LinkedList<>();

list.getFirst();

当集合为空时：

getFirst()
getLast()
removeFirst()
removeLast()

会抛出：

NoSuchElementException

LinkedList 还提供了一组 Deque 风格 API：

peekFirst()
peekLast()
pollFirst()
pollLast()

例如：

String value = list.peekFirst();

集合为空时：

peekFirst()
peekLast()
pollFirst()
pollLast()

通常返回 null，而不是抛出 NoSuchElementException。

因此在真正的队列代码中，需要理解这两组 API 的语义差异。

四、原理与进阶

4.1 LinkedList 内部结点结构

从实现思想看，一个 LinkedList 结点可以近似理解为：

class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

注意：

这只是帮助理解 LinkedList 底层结构的简化模型，不代表我们平时使用 LinkedList 时需要自己定义该类。

LinkedList 内部还维护类似：

first
last
size

这样的信息。

因此：

first → 第一个结点
last  → 最后一个结点
size  → 当前元素数量

首尾操作可以直接定位到对应结点。

4.2 为什么首部插入很快

假设原链表：

A ⇄ B ⇄ C

现在需要在最前面插入：

X

最终：

X ⇄ A ⇄ B ⇄ C

主要只需要调整几个引用关系：

X.next = A
A.prev = X
first = X

不需要像数组那样：

A → 后移
B → 后移
C → 后移

因此链表首部插入的结构修改非常直接。

4.3 为什么尾部增删也很快

LinkedList 内部保存对：

last

的引用。

因此添加到尾部时不需要从头遍历整个链表寻找尾结点。

例如：

A ⇄ B ⇄ C
        ↑
       last

添加：

D

主要修改：

C.next = D
D.prev = C
last = D

因此首尾操作非常适合 LinkedList。

4.4 为什么按索引查询较慢

考虑：

list.get(5000);

ArrayList 可以通过数组索引直接定位。

而 LinkedList 不能通过：

首地址 + index × 元素大小

直接找到第 5000 个结点。

它必须沿着结点引用不断移动。

LinkedList 会根据目标索引更靠近：

  • 头部；
  • 还是尾部；

选择较近的一端开始遍历。

例如链表有 100 个元素：

get(5)

更适合从头部开始。

而：

get(95)

更适合从尾部开始。

但从时间复杂度整体分析：

LinkedList.get(index)

仍然属于：

O(n)

级别的随机访问操作。

4.5 中间插入为什么不一定很快

这是 LinkedList 最容易被误解的地方。

很多初学者会说：

LinkedList 插入删除是 O(1)。

这个说法只有在：

已经拿到目标结点引用

时才比较接近真实情况。

例如想在第 5000 个位置插入：

list.add(5000, data);

必须先找到对应位置附近的结点。

这个寻找过程可能需要：

O(n)

之后真正修改：

prev
next

引用关系才是常数级操作。

因此：

定位结点 O(n)
+
修改链接 O(1)

整体仍然可能表现为：

O(n)

所以不能说：

LinkedList 任意位置插入删除都一定比 ArrayList 快。

4.6 为什么 ArrayList 在实际开发中更加常见

虽然 LinkedList 的链表结构非常经典，但在绝大多数普通业务列表场景中，ArrayList 往往更加常见。

原因包括：

第一，随机访问效率高

list.get(index);

ArrayList 非常适合。

第二，遍历性能通常更好

数组元素具有较好的：

内存局部性（Memory Locality）

CPU 缓存更容易有效利用连续数据。

第三，LinkedList 每个元素都需要额外保存链接引用

链表结点除了：

item

还需要：

prev
next

因此会产生额外的对象和引用开销。

所以集合选择不能只看理论上的某一个时间复杂度。

五、实践应用

5.1 适合 LinkedList 的场景

LinkedList 更适合：

  • 频繁操作头部元素；
  • 频繁操作尾部元素；
  • 需要双端队列语义；
  • 已经持有迭代器位置并进行局部插入删除。

例如：

任务等待队列
消息队列模型
历史记录
双端操作

5.2 ArrayList 与 LinkedList 怎么选

可以使用下面这套判断方式。

情况一：普通业务数据列表

例如：

用户列表
订单列表
商品列表
文章列表

通常优先：

ArrayList

情况二：大量按索引访问

例如：

list.get(i);

优先：

ArrayList

情况三：频繁首尾插入删除

可以考虑：

LinkedList

或者根据队列需求选择专门的 Deque 实现。

情况四：只是因为“可能增删比较多”

不能因此直接选择 LinkedList。

应该进一步分析：

在哪里增删？
是否需要先搜索？
是否大量随机访问？
是否大量遍历？
数据规模多大？

再做决定。

六、常见问题

6.1 LinkedList 是不是没有索引？

从 List 接口语义看，LinkedList 支持位置访问：

get(index)
set(index, element)
add(index, element)
remove(index)

因此可以按索引使用。

但是它不像数组一样真正支持高效随机访问。

所以更准确的说法是：

LinkedList 有 List 的索引语义，但其底层不是数组，按索引访问需要链表遍历。

6.2 LinkedList 查询是不是一定很慢？

不能简单说“所有查询都慢”。

例如：

getFirst()
getLast()

可以直接访问首尾结点。

真正需要重点注意的是：

get(index)

这样的随机位置访问。

6.3 LinkedList 增删是不是永远比 ArrayList 快？

不是。

例如：

list.add(50000, element);

LinkedList 首先需要定位相关结点。

这个过程本身可能就是线性的。

所以应该区分：

定位成本
+
修改数据结构成本

6.4 LinkedList 能不能保存 null？

可以。

例如：

LinkedList<String> list = new LinkedList<>();

list.add(null);
list.add("Java");

但是业务开发中是否应该使用 null，要根据具体设计决定，不能因为集合允许就随意保存。

6.5 LinkedList 可以当队列使用吗？

可以。

因为 LinkedList 实现了：

Deque

因此具备完整的双端队列能力。

例如：

offer()
poll()
peek()

以及：

offerFirst()
offerLast()
pollFirst()
pollLast()

本章重点理解 LinkedList 与双向链表即可，不需要一次性记忆全部 Deque API。

6.6 LinkedList 是线程安全的吗？

不是。

普通：

LinkedList
ArrayList
HashSet
HashMap

都不能因为属于 Java 集合框架，就自动认为线程安全。

多线程环境中的集合选择会在并发知识体系中进一步学习。

七、练习与验收

7.1 知识问答

  1. LinkedList 底层主要基于什么数据结构实现？
  2. 什么是双向链表？
  3. 一个双向链表结点通常需要保存哪些信息？
  4. LinkedList 为什么能够从头部和尾部两个方向进行遍历？
  5. first 与 last 分别可以理解为什么？
  6. 为什么 LinkedList 的首尾增删操作比较方便？
  7. 为什么 get(index) 不能像 ArrayList 一样直接定位元素？
  8. addFirst() 与 addLast() 分别完成什么操作？
  9. getFirst() 与 getLast() 分别完成什么操作？
  10. removeFirst() 与 removeLast() 分别完成什么操作？
  11. 为什么“LinkedList 增删一定比 ArrayList 快”是不准确的？
  12. ArrayList 与 LinkedList 应该从哪些因素综合选择？

7.2 代码阅读

阅读下面程序，不运行代码，写出每一步集合内容：

import java.util.LinkedList;

public class LinkedListRead {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        list.add("B");
        list.add("C");

        list.addFirst("A");
        list.addLast("D");

        String first = list.removeFirst();
        String last = list.getLast();

        System.out.println(first);
        System.out.println(last);
        System.out.println(list);
    }
}

回答：

  1. 每次操作后 LinkedList 中元素是什么？
  2. removeFirst() 与 getLast() 是否都会删除元素？
  3. 最终集合中有几个元素？
  4. 如果执行两次 removeLast()，集合会如何变化？

7.3 手写代码

任务一：首尾操作

创建：

LinkedList<String>

依次完成：

  1. 尾部加入三个元素；
  2. 头部加入一个元素；
  3. 获取第一个元素；
  4. 获取最后一个元素；
  5. 删除第一个元素；
  6. 删除最后一个元素；
  7. 遍历剩余元素。

任务二：任务列表

设计任务列表：

普通任务 → 放到尾部
紧急任务 → 放到头部

要求：

  • 使用 LinkedList；
  • 至少添加 5 个任务；
  • 取出任务时从队首开始；
  • 每完成一个任务输出剩余任务数量。

任务三：ArrayList 与 LinkedList 对比

分别使用：

ArrayList<String>
LinkedList<String>

实现一个需要不断在头部添加元素的程序。

记录：

  • 两者 API 的区别；
  • 两者底层操作思路的区别；
  • 为什么不能只根据一次小规模运行时间得出性能结论。

7.4 Debug

下面代码存在设计问题：

LinkedList<String> list = new LinkedList<>();

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

假设 list 中有大量元素。

回答：

  1. 代码语法是否正确？
  2. 为什么这种写法对 LinkedList 不够理想？
  3. get(i) 每一次执行可能发生什么？
  4. 应该考虑使用什么遍历方式？
  5. 为什么同样的索引遍历写法对 ArrayList 与 LinkedList 的性能含义不同？

7.5 综合训练

设计一个“浏览历史记录”模型。

需求：

  • 用户访问页面后添加一条历史记录；
  • 最新历史可以添加到头部；
  • 最多保存 10 条；
  • 超过 10 条后删除最旧记录；
  • 可以查看最新历史；
  • 可以查看最旧历史。

要求：

  1. 先说明为什么可以考虑 LinkedList；
  2. 写出核心数据结构；
  3. 写出添加历史记录逻辑；
  4. 写出超过容量后的处理逻辑；
  5. 写出完整测试代码。

7.6 本章验收

关闭资料和 AI 自动补全，完成以下验收：

  • [ ] 能画出双向链表结构。
  • [ ] 能解释 prev、item、next 的作用。
  • [ ] 能独立写出 LinkedList 的创建代码。
  • [ ] 能手写 addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()。
  • [ ] 能解释为什么随机索引访问较慢。
  • [ ] 能解释为什么首尾操作较快。
  • [ ] 能指出“LinkedList 增删永远比 ArrayList 快”的错误。
  • [ ] 能根据业务场景选择 ArrayList 或 LinkedList。