【Java】LinkedList 详解：从底层原理到实战应用
大家好，我是 YunYang～ 上一篇给大家详解了 ArrayList 的核心用法与源码实现，今天咱们继续深挖 Java 集合框架，聊聊另一个高频使用的 List 实现类 ——LinkedList。作为 ArrayList 的 “同门兄弟”，LinkedList 基于完全不同的底层结构，在特定场景下能发挥出压倒性的性能优势。这篇文章咱们就从原理到实战，把 LinkedList 彻底吃透！
一、为什么选择 LinkedList？—— 链表结构的天生优势
在聊 LinkedList 之前，先思考一个问题：既然有了 ArrayList，为什么还需要 LinkedList？答案藏在底层数据结构里 ——LinkedList 基于双向链表实现，而 ArrayList 基于动态数组。这种结构差异让 LinkedList 在以下场景中脱颖而出：
- 动态扩容无压力：链表不需要预先分配固定内存，元素添加时直接创建节点即可，完全避免了数组扩容时的拷贝开销。
- 插入删除效率极高：无论是在链表头部、尾部还是中间位置操作元素，只需调整相邻节点的指针（prev/next），时间复杂度仅为 O (1)；而 ArrayList 则需要移动大量元素，时间复杂度为 O (n)。
这里补充下链表的常见类型，帮大家理解 LinkedList 的设计：
- 单向链表：每个节点只有 next 指针，只能单向遍历；
- 双向链表：每个节点同时拥有 prev 和 next 指针，支持双向遍历（LinkedList 采用此结构）；
- 循环链表：首尾节点相连，适用于环形场景（如约瑟夫问题）。
二、LinkedList 核心结构揭秘
1. 节点类（Node）
LinkedList 的底层核心是 Node 静态内部类，每个节点包含三个部分：元素本身、前驱节点指针、后继节点指针。源码如下（简化版）：
private static class Node {
E item; // 存储的元素
Node next// 下一个节点指针
Node prev; // 上一个节点指针
// 构造方法：初始化节点
Node(Node E element, Node next) {
this.prev = prev;
this.item = element;
this.next = next;
}
}
2. 链表结构图示
LinkedList 的链表关系非常清晰：
- 首节点（first）：prev 指针为 null；
- 尾节点（last）：next 指针为 null；
- 中间节点：prev 指向前驱节点，next 指向后继节点；
- 空链表：first 和 last 均为 null。
示意图如下：
first last
↓ ↓
[null] ← [A] ↔ [B] ↔ [C]↔ [D] → [null]
三、LinkedList 核心操作实战（附代码）
1. 初始化
LinkedList 无需指定初始容量，创建时直接初始化即可，添加第一个元素时会自动创建首节点：
// 方式1：无参构造（推荐）
LinkedList<String> list = new LinkedList<>();
// 方式2：通过集合初始化
List<String> initList = Arrays.asList("a", "b", "c", "d");
LinkedList<String> list2 = new LinkedList<>(initList);
2. 新增元素（增）
LinkedList 提供了丰富的添加方法，覆盖不同场景：
// 尾部添加（默认，等价于 addLast ()）
LinkedList<String> list = new LinkedList<>();
list.add("张三");
list.addLast("李四");
// 2. 头部添加
list.addFirst("王五");
// 3. 指定索引添加（注意：索引查找需遍历，时间复杂度 O(n)）
list.add(1, "赵六"); // 在索引1位置插入"赵六"
// 输出结果：[王五, 赵六, 张三, 李四]
System.out.println(list);
3. 删除元素（删）
支持按索引、按元素、首尾删除等多种方式：
LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c", "b", "d"));
// 1. 删除首节点（两种方式等价）
list.removeFirst();
list.remove(); // 无参remove()默认删除首节点
// 2. 删除尾节点
list.removeLast();
// 3. 按索引删除
list.remove(0); // 删除索引0的元素
// 4. 按元素删除（删除第一个匹配的元素）
list.remove("b");
// 输出结果：[]（上述操作后链表为空）
System.out.println(list);
4. 修改元素（改）
通过 set () 方法按索引修改元素，需注意索引越界问题：
LinkedList<String> list = new LinkedList<>(Arrays.asList("苹果","香蕉", "橘子"));
// 将索引1的元素改为"葡萄"
list.set(1, "葡萄");
// 输出结果：[苹果, 葡萄, 橘子]
System.out.println(list);
5. 查找元素（查）
提供了按索引、按元素、首尾查询等方法，注意索引查询的时间复杂度为 O (n)：
LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c", "d"));
// 1. 按索引查询
String elem = list.get(2); // 结果："c"
// 2. 查找元素位置（返回第一个匹配的索引，未找到返回-1）
int index = list.indexOf("d"); // 结果：3
// 3. 获取首尾元素（无索引遍历，效率O(1)）
String first = list.getFirst(); // 结果："a"
String last = list.getLast(); // 结果："d"
// 4. 弹出元素（删除并返回，队列常用）
String polled = list.poll(); // 删除并返回"a"，链表变为["b","c","d"]
四、LinkedList vs ArrayList：核心差异与应用场景
很多同学会纠结什么时候用 LinkedList，什么时候用 ArrayList。这里直接上对比表，一目了然：
| 操作类型 | LinkedList | ArrayList |
|---|---|---|
| 随机访问（get） | O(n) | O(1) |
| 尾部添加（add） | O(1) | O(1) |
| 中间插入 / 删除 | O(1) | O(n) |
| 内存占用 | 较高（节点开销） | 较低（连续存储） |
最佳实践场景：
- 优先用 ArrayList：需要频繁通过索引访问元素、元素数量稳定的场景（如存储用户列表、配置项）；
- 优先用 LinkedList：需要频繁插入 / 删除元素的场景（如游戏道具栏、消息队列、LRU 缓存）。
举个 LRU 缓存的简化实现思路：用 LinkedList 存储缓存数据，每次访问数据时将其移到链表头部，当缓存满时，直接删除链表尾部元素（最近最少使用），这正是利用了 LinkedList 首尾操作的高效性。
五、总结
LinkedList 作为 Java 集合框架的重要成员，其核心优势在于高效的插入删除操作，这得益于双向链表的底层结构。但它的短板是随机访问效率低，因此选择时需根据业务场景的核心操作来决策。
掌握 LinkedList 的底层原理和核心用法，不仅能在实际开发中选择更合适的数据结构，还能帮助我们理解 “数据结构影响算法效率” 的核心思想。下一篇咱们将深入探讨 Java 集合框架的其他成员，敬请期待～
