Java LinkedList

学习目标

理解 LinkedList 的底层数据结构及其特点
掌握 LinkedList 的常用操作方法（增、删、改、查）
了解 LinkedList 与 ArrayList 的核心区别
能够在实际开发中合理选择使用 LinkedList

什么是 LinkedList

LinkedList 是 Java 集合框架的一部分，位于 java.util 包中。它基于双向链表实现，这意味着每个节点包含三部分：

当前元素的数据
指向下一个节点的引用
指向前一个节点的引用

由于链表不要求元素在内存中连续存储，因此具有以下特性：

动态大小：运行时可自动扩容或缩容
保持插入顺序：元素按添加顺序存储
允许重复元素
非线程安全：默认不支持并发操作；若需线程安全，可使用 Collections.synchronizedList() 包装
高效的插入 / 删除：尤其在列表头部或中间位置操作时，性能优于 ArrayList

注意：LinkedList 不支持通过索引直接访问节点，必须从头（或尾）开始遍历。

LinkedList 的类继承关系

LinkedList 同时实现了 List 接口和 Deque 接口，而这两个接口都继承自 Collection 接口。这使得 LinkedList 既可以作为列表使用，也可以作为双端队列（甚至栈）使用。

构造方法

LinkedList 提供了两种主要构造函数：

构造方法一

LinkedList()

创建一个空的链表：

LinkedList<String> list = new LinkedList<>();

构造方法二

LinkedList(Collection<? extends E> c)

创建一个包含指定集合中所有元素的链表（按迭代器返回的顺序）：

List<String> source = Arrays.asList("A", "B", "C");
LinkedList<String> list = new LinkedList<>(source);

常用操作

1. 添加元素

add(E e)：在末尾添加元素
add(int index, E e)：在指定位置插入元素

import java.util.*;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> ll = new LinkedList<>();
        ll.add("Hello");
        ll.add("World");
        ll.add(1, "Java");

        System.out.println(ll); // 输出: [Hello, Java, World]
    }
}

2. 更新元素

使用 set(int index, E element) 替换指定位置的元素：

ll.set(1, "Python");
System.out.println(ll); // [Hello, Python, World]

3. 删除元素

remove(int index)：删除指定索引处的元素
remove(Object o)：删除第一个匹配的对象

ll.remove(1);           // 删除索引 1 的元素
ll.remove("Hello");     // 删除第一个 "Hello"

4. 遍历元素

传统 for 循环 + `get(index)`

for (int i = 0; i < ll.size(); i++) {
    System.out.print(ll.get(i) + " ");
}

注意：get(index) 在 LinkedList 中时间复杂度为 O(n)，频繁使用会影响性能。

增强 for 循环

for (String item : ll) {
    System.out.print(item + " ");
}

常用方法

方法	描述
`add(E e)`	在末尾添加元素
`addFirst(E e)` / `addLast(E e)`	在首 / 尾添加元素
`get(int index)`	获取指定位置的元素（O(n)）
`getFirst()` / `getLast()`	获取首 / 尾元素（O(1)）
`set(int index, E e)`	替换指定位置的元素
`remove(int index)` / `remove(Object o)`	删除元素
`removeFirst()` / `removeLast()`	删除并返回首 / 尾元素
`peek()` / `peekFirst()` / `peekLast()`	查看但不移除首 / 尾元素（空时返回 null）
`poll()` / `pollFirst()` / `pollLast()`	移除并返回首 / 尾元素（空时返回 null）
`push(E e)` / `pop()`	作为栈使用（LIFO）
`size()`	返回元素个数
`contains(Object o)`	判断是否包含某元素

LinkedList vs ArrayList

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)，快速	O(n)，慢
内存占用	较低（连续内存）	较高（每个节点需额外指针）
插入 / 删除（中间或头部）	O(n)，需移动元素	O(1)，仅修改指针
迭代速度	快（缓存友好）	相对较慢
是否实现 Deque	否	是（支持双端队列操作）

使用建议：
需要频繁随机访问 → 选 ArrayList
需要在列表两端频繁插入 / 删除 → 选 LinkedList
一般场景下，ArrayList 性能更优且内存更紧凑

重点总结

LinkedList 是基于双向链表实现的 List 和 Deque
支持高效的首尾操作，适合用作栈、队列或双端队列
不支持快速随机访问，避免在循环中频繁调用 get(i)
默认非线程安全，多线程环境下需手动同步
相比 ArrayList，内存开销更大，但插入 / 删除性能更优（尤其在两端）

思考题

为什么在 LinkedList 中使用 get(i) 方法进行随机访问效率较低？其时间复杂度是多少？
如果你需要实现一个支持“撤销”操作的功能（如文本编辑器），使用 LinkedList 作为历史记录栈是否合适？为什么？
在什么场景下你会优先选择 LinkedList 而不是 ArrayList？请结合实际开发经验举例说明。