Java LinkedList

Java LinkedList 是 Java集合框架 中实现 List接口 和 Deque接口 的双向链表数据结构。它允许高效的元素插入和删除操作，但随机访问性能较差。本教程将详细介绍其特性、用法及实际应用场景。

概述

LinkedList 类位于 java.util 包中，基于节点（Node）的链式存储结构。每个节点包含数据（元素）、前驱节点（prev）和后继节点（next）的引用。与 ArrayList 不同，LinkedList 不需要连续内存空间，因此适合频繁增删的场景。

核心特性

• 动态大小：无需预先指定容量。
• 双向链表：支持从头或尾遍历。
• 非线程安全：需外部同步（如使用 Collections.synchronizedList）。
• 实现接口：List, Deque, 支持队列和栈操作。

基本操作

创建 LinkedList

  
import java.util.LinkedList;  

public class Main {  
    public static void main(String[] args) {  
        LinkedList<String> fruits = new LinkedList<>();  
        fruits.add("Apple");  
        fruits.add("Banana");  
        System.out.println(fruits); // 输出: [Apple, Banana]  
    }  
}

添加元素

• add(E e)：尾部插入。
• addFirst(E e)：头部插入。
• addLast(E e)：同 add(E e)。

  
fruits.addFirst("Orange");  
fruits.addLast("Mango");  
System.out.println(fruits); // 输出: [Orange, Apple, Banana, Mango]

删除元素

• remove()：删除头部元素。
• remove(int index)：删除指定位置元素。

  
fruits.remove(); // 删除 Orange  
fruits.remove(1); // 删除 Banana  
System.out.println(fruits); // 输出: [Apple, Mango]

访问元素

• get(int index)：性能较差（需遍历链表）。
• peekFirst()/peekLast()：获取头/尾元素。

  
String first = fruits.getFirst(); // Apple  
String last = fruits.getLast(); // Mango

性能分析

以下为 LinkedList 常见操作的时间复杂度：

操作	时间复杂度
插入/删除（头/尾）	$O(1)$
插入/删除（中间）	$O(n)$
随机访问（get/set）	$O(n)$

实际应用案例

场景：实现队列

利用 Deque 接口实现 FIFO 队列：

  
LinkedList<Integer> queue = new LinkedList<>();  
queue.offer(10); // 入队  
queue.offer(20);  
System.out.println(queue.poll()); // 出队，输出: 10

场景：反转链表

  
LinkedList<String> list = new LinkedList<>();  
list.add("A"); list.add("B"); list.add("C");  
Collections.reverse(list);  
System.out.println(list); // 输出: [C, B, A]

内部结构图解

graph LR A[Node] -->|prev| B[Node] B -->|next| C[Node] B -->|prev| A C -->|prev| B

• 每个节点包含前驱（prev）、数据（item）和后继（next）指针。

注意事项

• 避免随机访问：频繁调用 get(index) 会导致性能问题。
• 迭代器遍历：优先使用 Iterator 或增强型 for 循环。
• 内存开销：每个节点需额外存储前后指针，占用更多内存。

总结

LinkedList 适合频繁增删的场景（如队列、栈），但不适合大量随机访问。理解其底层链表结构有助于合理选择数据结构。