LinkedList 是什么？
LinkedList 是一个实现了 List 接口和 Deque 接口的双向链表，这意味着它不仅是一个列表，还可以作为一个双端队列来使用。
（图片来源网络，侵删）
核心特点：双向链表
与 ArrayList（基于动态数组）不同，LinkedList 的内部结构不是连续的内存空间，它由一系列的节点 组成，每个节点包含三部分：
- 数据：节点存储的元素。
- 前驱指针：指向前一个节点的引用。
- 后继指针：指向后一个节点的引用。
这个结构带来了 LinkedList 独特的性能特征。
LinkedList 的主要特点
| 特性 | 描述 |
|---|---|
| 数据结构 | 双向链表，每个节点都指向其前一个和后一个节点。 |
| 插入/删除 | 在中间位置非常快，因为只需要修改相邻节点的指针即可，时间复杂度为 O(1)（前提是已定位到节点）。 |
| 随机访问 | 非常慢，要访问第 i 个元素，必须从头或尾开始，一个一个地遍历，直到找到该元素，时间复杂度为 O(n)。 |
| 内存占用 | 比 ArrayList 大，除了存储元素本身，每个节点还需要额外空间存储两个指针。 |
| 线程安全 | 非线程安全，如果在多线程环境下使用，需要手动进行同步，例如使用 Collections.synchronizedList(new LinkedList<>()) 或 ConcurrentLinkedQueue。 |
LinkedList 的常用方法
LinkedList 继承了 AbstractList 并实现了 List, Deque, Cloneable, java.io.Serializable 接口，因此它拥有非常丰富的方法。
1 作为 List 的基本操作 (增删改查)
这些方法与 ArrayList 类似，但底层实现原理不同。
（图片来源网络，侵删）
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
// 1. 创建 LinkedList
LinkedList<String> list = new LinkedList<>();
// 2. 添加元素
list.add("Apple"); // 在末尾添加
list.add("Banana");
list.add("Cherry");
System.out.println("初始列表: " + list); // [Apple, Banana, Cherry]
// 在指定位置添加
list.add(1, "Blueberry");
System.out.println("在索引1添加后: " + list); // [Apple, Blueberry, Banana, Cherry]
// 3. 删除元素
list.remove("Banana"); // 删除第一个匹配的元素
System.out.println("删除'Banana'后: " + list); // [Apple, Blueberry, Cherry]
list.remove(0); // 删除指定索引的元素
System.out.println("删除索引0后: " + list); // [Blueberry, Cherry]
// 4. 修改元素
list.set(0, "Blackberry");
System.out.println("修改索引0后: " + list); // [Blackberry, Cherry]
// 5. 查询元素
String first = list.getFirst();
String last = list.getLast();
System.out.println("第一个元素: " + first); // Blackberry
System.out.println("最后一个元素: " + last); // Cherry
System.out.println("索引1的元素: " + list.get(1)); // Cherry
}
}
2 作为 Deque (双端队列) 的高效操作
这是 LinkedList 的精髓所在，这些操作在链表的两端进行，效率极高（O(1)）。
import java.util.LinkedList;
public class LinkedListAsDeque {
public static void main(String[] args) {
LinkedList<String> deque = new LinkedList<>();
// --- 从队首/前端操作 ---
// 添加到队首
deque.addFirst("First");
deque.offerFirst("OfferFirst"); // addFirst的替代方法，在队列满时可能更友好（但LinkedList不会满）
System.out.println("从队首添加后: " + deque); // [OfferFirst, First]
// 查看队首元素（不删除）
System.out.println("peekFirst(): " + deque.peekFirst()); // OfferFirst
// 获取并移除队首元素
System.out.println("pollFirst(): " + deque.pollFirst()); // OfferFirst
System.out.println("pollFirst()后: " + deque); // [First]
// --- 从队尾/后端操作 ---
// 添加到队尾
deque.addLast("Last");
deque.offerLast("OfferLast"); // addLast的替代方法
System.out.println("从队尾添加后: " + deque); // [First, Last, OfferLast]
// 查看队尾元素（不删除）
System.out.println("peekLast(): " + deque.peekLast()); // OfferLast
// 获取并移除队尾元素
System.out.println("pollLast(): " + deque.pollLast()); // OfferLast
System.out.println("pollLast()后: " + deque); // [First, Last]
}
}
addFirst vs offerFirst / addLast vs offerLast:
addXxx: 在操作成功时返回true，如果操作失败（例如容量受限的队列）会抛出异常。offerXxx: 在操作成功时返回true，如果操作失败则返回false。- 对于
LinkedList（无容量限制），它们的行为基本一致，但offerXxx的命名更符合队列的语义。
3 栈操作 (LIFO - Last-In, First-Out)
LinkedList 也可以作为一个栈来使用。
import java.util.LinkedList;
public class LinkedListAsStack {
public static void main(String[] args) {
LinkedList<Integer> stack = new LinkedList<>();
// 入栈
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("栈内容: " + stack); // [30, 20, 10] (30在顶部)
// 查看栈顶元素（不删除）
System.out.println("peek(): " + stack.peek()); // 30
// 出栈
System.out.println("pop(): " + stack.pop()); // 30
System.out.println("pop()后: " + stack); // [20, 10]
}
}
push(E e): 等同于addFirst(E e)。pop(): 等同于removeFirst()。peek(): 等同于getFirst()。
LinkedList vs ArrayList：如何选择？
这是一个非常经典的问题,选择哪个取决于你的应用场景。
（图片来源网络，侵删）
| 特性 | LinkedList |
ArrayList |
|---|---|---|
| 数据结构 | 双向链表 | 动态数组 |
| 随机访问 | 慢 (O(n)) | 快 (O(1)) |
| 中间插入/删除 | 快 (O(1)) (若已定位) | 慢 (O(n)) (需要移动元素) |
| 头部/尾部插入/删除 | 快 (O(1)) | 头部慢 (O(n)), 尾部快 (O(1)) (均摊) |
| 内存占用 | 高 (每个元素有两个指针) | 低 (只有元素本身) |
| 缓存局部性 | 差 (元素分散在内存) | 好 (元素连续存储，CPU缓存友好) |
选择 LinkedList 的场景：
- 频繁的头部/中间插入和删除操作，实现一个任务队列，需要频繁地在队列头部添加新任务，或在中间取消任务。
- 你需要实现一个栈或双端队列。
LinkedList实现了Deque接口，提供了丰富且高效的栈/队列操作。 - 数据量很大，且需要频繁增删，但对随机访问性能要求不高。
选择 ArrayList 的场景：
- 需要频繁的随机访问，根据索引
i获取元素，这是ArrayList的强项。 - 主要在末尾添加或删除元素。
ArrayList的add(E e)和remove(size() - 1)操作性能非常好。 - 数据量不大，且对内存占用比较敏感。
- 默认选择，如果你不确定，
ArrayList是更好的选择，因为它更通用，并且在大多数情况下性能表现优异。
LinkedList 的遍历方式
有三种主要的遍历方式,性能略有不同。
LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
// 1. For-Each 循环 (最常用，代码简洁)
for (String item : list) {
System.out.print(item + " "); // A B C
}
System.out.println();
// 2. 使用迭代器
// 可以安全地在遍历过程中修改列表（除了当前元素）
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String item = iterator.next();
if ("B".equals(item)) {
iterator.remove(); // 安全删除
}
System.out.print(item + " "); // A B C (删除后变为 A C)
}
System.out.println();
// 3. 使用索引 (不推荐！性能差)
// 因为 get(i) 是 O(n) 操作，整个循环就是 O(n^2)
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " "); // A C
}
System.out.println();
遍历性能建议：
- 优先使用 For-Each 循环，它既简洁又高效。
- 需要边遍历边删除时，必须使用迭代器。
- 避免使用索引遍历
LinkedList，除非你有特殊需求且列表非常小。
LinkedList 是 Java 集合框架中的一个强大工具，它通过双向链表的结构，在频繁的插入和删除操作（尤其是在头部和中间）上表现出色，理解其与 ArrayList 的根本区别和各自的适用场景，是写出高效、健壮 Java 代码的关键，当你需要一个高性能的栈或双端队列，或者你的应用场景充满了中间元素的增删时，LinkedList 是你的不二之选。
