编辑“︁Java LinkedList”︁

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

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

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

== 基本操作 ==  
=== 创建 LinkedList ===  
<syntaxhighlight lang="java">  
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]  
    }  
}  
</syntaxhighlight>  

=== 添加元素 ===  
* <code>add(E e)</code>：尾部插入。  
* <code>addFirst(E e)</code>：头部插入。  
* <code>addLast(E e)</code>：同 <code>add(E e)</code>。  

<syntaxhighlight lang="java">  
fruits.addFirst("Orange");  
fruits.addLast("Mango");  
System.out.println(fruits); // 输出: [Orange, Apple, Banana, Mango]  
</syntaxhighlight>  

=== 删除元素 ===  
* <code>remove()</code>：删除头部元素。  
* <code>remove(int index)</code>：删除指定位置元素。  

<syntaxhighlight lang="java">  
fruits.remove(); // 删除 Orange  
fruits.remove(1); // 删除 Banana  
System.out.println(fruits); // 输出: [Apple, Mango]  
</syntaxhighlight>  

=== 访问元素 ===  
* <code>get(int index)</code>：性能较差（需遍历链表）。  
* <code>peekFirst()</code>/<code>peekLast()</code>：获取头/尾元素。  

<syntaxhighlight lang="java">  
String first = fruits.getFirst(); // Apple  
String last = fruits.getLast(); // Mango  
</syntaxhighlight>  

== 性能分析 ==  
以下为 LinkedList 常见操作的时间复杂度：  

{| class="wikitable"  
! 操作 !! 时间复杂度  
|-  
| 插入/删除（头/尾） || <math>O(1)</math>  
|-  
| 插入/删除（中间） || <math>O(n)</math>  
|-  
| 随机访问（get/set） || <math>O(n)</math>  
|}  

== 实际应用案例 ==  
=== 场景：实现队列 ===  
利用 <code>Deque</code> 接口实现 FIFO 队列：  
<syntaxhighlight lang="java">  
LinkedList<Integer> queue = new LinkedList<>();  
queue.offer(10); // 入队  
queue.offer(20);  
System.out.println(queue.poll()); // 出队，输出: 10  
</syntaxhighlight>  

=== 场景：反转链表 ===  
<syntaxhighlight lang="java">  
LinkedList<String> list = new LinkedList<>();  
list.add("A"); list.add("B"); list.add("C");  
Collections.reverse(list);  
System.out.println(list); // 输出: [C, B, A]  
</syntaxhighlight>  

== 内部结构图解 ==  
<mermaid>  
graph LR  
    A[Node] -->|prev| B[Node]  
    B -->|next| C[Node]  
    B -->|prev| A  
    C -->|prev| B  
</mermaid>  
* 每个节点包含前驱（prev）、数据（item）和后继（next）指针。  

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

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

{{Java集合框架导航}}

[[Category:编程语言]]
[[Category:Java]]
[[Category:Java集合框架]]