掌握双向链表的特点、原理和实际应用，学会性能优化技巧
LinkedList是Java集合框架中基于双向链表实现的List接口。与ArrayList不同，LinkedList在插入和删除操作上有着显著的性能优势，但在随机访问方面性能较差。理解LinkedList的特点对于选择合适的数据结构至关重要。
[prev|data|next] <-> [prev|data|next] <-> [prev|data|next]
节点1 节点2 节点3| 操作 | 时间复杂度 | 性能 |
|---|---|---|
| 随机访问 | O(n) | 较差 |
| 头部插入/删除 | O(1) | 优秀 |
| 尾部插入/删除 | O(1) | 优秀 |
| 中间插入/删除 | O(1)* | 良好 |
*需要先定位到指定位置
public class LinkedList
extends AbstractSequentialList
implements List, Deque,
Cloneable, Serializable import java.util.LinkedList;
import java.util.List;
// 创建LinkedList
LinkedList list = new LinkedList<>();
List list2 = new LinkedList<>(); // 使用接口引用
// 添加元素
list.add("Apple"); // 末尾添加
list.addFirst("Grape"); // 头部添加
list.addLast("Banana"); // 尾部添加
list.add(1, "Orange"); // 指定位置添加
// 队列操作
list.offer("Cherry"); // 入队（末尾添加）
System.out.println(list); // [Grape, Orange, Apple, Banana, Cherry] // 访问元素
String first = list.getFirst(); // 获取第一个元素
String last = list.getLast(); // 获取最后一个元素
String element = list.get(2); // 获取指定位置元素（性能较差）
// 队列操作
String head = list.peek(); // 查看队首元素
String headFirst = list.peekFirst(); // 查看第一个元素
String headLast = list.peekLast(); // 查看最后一个元素
// 查找操作
int index = list.indexOf("Apple"); // 查找元素索引
boolean contains = list.contains("Orange"); // 检查是否包含// 删除操作
String removed = list.removeFirst(); // 删除第一个元素
String removedLast = list.removeLast(); // 删除最后一个元素
String removedAt = list.remove(1); // 删除指定位置元素
boolean isRemoved = list.remove("Apple"); // 删除指定元素
// 队列操作
String polled = list.poll(); // 出队（删除第一个元素）
String pollFirst = list.pollFirst(); // 删除第一个元素
String pollLast = list.pollLast(); // 删除最后一个元素选择LinkedList还是ArrayList是Java开发中的常见问题。下表详细对比了两者的性能特点：
| 操作类型 | LinkedList | ArrayList | 建议 |
|---|---|---|---|
| 随机访问 get(index) | O(n) - 需要遍历 | O(1) - 数组索引 | 频繁随机访问选ArrayList |
| 头部插入 add(0, element) | O(1) - 直接操作 | O(n) - 需要移动元素 | 频繁头部操作选LinkedList |
| 尾部插入 add(element) | O(1) - 直接操作 | O(1) - 通常情况 | 性能相近 |
| 中间插入 add(index, element) | O(n) - 需要定位 | O(n) - 需要移动元素 | LinkedList略优 |
| 头部删除 remove(0) | O(1) - 直接操作 | O(n) - 需要移动元素 | LinkedList明显更优 |
| 内存开销 | 较高 - 每个节点需要指针 | 较低 - 连续内存 | 内存敏感选ArrayList |
LinkedList实现了Deque接口，可以作为队列、栈和双端队列使用，这是其相比ArrayList的独特优势。
import java.util.Queue;
import java.util.LinkedList;
Queue queue = new LinkedList<>();
// 入队操作
queue.offer("客户1");
queue.offer("客户2");
queue.offer("客户3");
// 查看队首
String head = queue.peek(); // "客户1"
// 出队操作
while (!queue.isEmpty()) {
String customer = queue.poll();
System.out.println("服务: " + customer);
}
// 输出：服务: 客户1, 服务: 客户2, 服务: 客户3 LinkedList stack = new LinkedList<>();
// 压栈操作
stack.push("方法A");
stack.push("方法B");
stack.push("方法C");
// 查看栈顶
String top = stack.peek(); // "方法C"
// 出栈操作
while (!stack.isEmpty()) {
String method = stack.pop();
System.out.println("执行: " + method);
}
// 输出：执行: 方法C, 执行: 方法B, 执行: 方法A import java.util.Deque;
import java.util.LinkedList;
Deque deque = new LinkedList<>();
// 两端添加
deque.addFirst(2);
deque.addLast(3);
deque.addFirst(1);
deque.addLast(4);
// 结果：[1, 2, 3, 4]
// 两端查看
Integer first = deque.peekFirst(); // 1
Integer last = deque.peekLast(); // 4
// 两端删除
Integer removeFirst = deque.removeFirst(); // 1
Integer removeLast = deque.removeLast(); // 4
// 结果：[2, 3] // ✅ 使用专门的头尾操作
list.addFirst(element);
list.addLast(element);
list.removeFirst();
list.removeLast();
// ✅ 使用迭代器遍历
for (String item : list) {
process(item);
}
// ✅ 使用队列接口
Queue queue = new LinkedList<>();
queue.offer(element);
String item = queue.poll(); // ❌ 避免频繁随机访问
for (int i = 0; i < list.size(); i++) {
String item = list.get(i); // O(n²)复杂度
}
// ❌ 避免使用索引操作
list.add(0, element); // 使用addFirst()
list.remove(0); // 使用removeFirst()
// ❌ 避免在大列表中间频繁插入
list.add(list.size()/2, element);LinkedList非常适合实现LRU（最近最少使用）缓存，因为需要频繁在头尾进行插入和删除操作。
文本编辑器、图形软件等需要撤销功能的应用，可以使用LinkedList存储操作历史。
在多线程环境中，LinkedList可以作为任务队列，支持高效的任务添加和获取。