第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接口 - 队列操作
支持克隆和序列化

基本操作示例

创建和添加元素

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

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

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最佳实践

性能优化技巧

避免做法

// ❌ 避免频繁随机访问
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 JavaScript