第51章

Java LinkedList

掌握双向链表的特点、原理和实际应用，学会性能优化技巧

学习目标

掌握LinkedList双向链表的数据结构原理

学会LinkedList的基本操作和API使用

理解LinkedList与ArrayList的性能差异

掌握LinkedList作为队列、栈、双端队列的使用

学会LinkedList的高级操作和优化技巧

了解LinkedList的实际应用场景和最佳实践

LinkedList特点详解

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

List接口 - 列表操作

Deque接口 - 双端队列操作

Queue接口 - 队列操作

支持克隆和序列化

基本操作示例

创建和添加元素

LinkedList创建和添加操作：

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]

访问和查找元素

LinkedList访问操作：

// 访问元素

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"); // 检查是否包含

删除元素

LinkedList删除操作：

// 删除操作

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(); // 删除最后一个元素

💻 查看完整代码 - 在线IDE体验

LinkedList vs ArrayList

选择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：频繁头部操作、实现队列/栈、不需要随机访问

选择ArrayList：频繁随机访问、内存敏感、主要在尾部操作

队列和栈操作

LinkedList实现了Deque接口，可以作为队列、栈和双端队列使用，这是其相比ArrayList的独特优势。

作为队列使用（FIFO）

队列操作示例：

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

作为栈使用（LIFO）

栈操作示例：

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]

LinkedList最佳实践

性能优化技巧

推荐做法

// ✅ 使用专门的头尾操作

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的get(index)方法需要从头或尾开始遍历，时间复杂度为O(n)。在大列表上频繁使用会导致严重的性能问题。

实际应用场景

LRU缓存实现

LinkedList非常适合实现LRU（最近最少使用）缓存，因为需要频繁在头尾进行插入和删除操作。

新访问的元素移到头部

超出容量时删除尾部元素

O(1)时间复杂度的操作

撤销功能

文本编辑器、图形软件等需要撤销功能的应用，可以使用LinkedList存储操作历史。

新操作添加到头部

撤销时从头部删除

支持多级撤销

任务队列

在多线程环境中，LinkedList可以作为任务队列，支持高效的任务添加和获取。

生产者在尾部添加任务

消费者从头部获取任务

支持优先级任务插入

章节总结

LinkedList基于双向链表实现，适合频繁插入删除操作

在头部操作方面LinkedList比ArrayList有显著优势

随机访问性能较差，应避免频繁使用get(index)方法

实现了多个接口，可作为列表、队列、栈、双端队列使用

内存开销比ArrayList大，每个节点需要额外的指针空间

适用于LRU缓存、撤销功能、任务队列等场景

选择数据结构时要根据具体的使用模式来决定

上一章：ArrayList详解

章节测试

下一章：Vector和Stack