Java LinkedList 详解

LinkedList 是 Java 集合框架中常用的数据结构之一，位于 java.util 包中。它实现了 List、Deque 和 Queue 接口，是一个双向链表结构，适合频繁的插入和删除操作。

---

1. LinkedList 的特点

1. 数据结构：基于双向链表实现，每个节点包含：

   • 数据部分（存储值）。
   • 前驱指针（指向前一个节点）。
   • 后继指针（指向后一个节点）。

2. 实现接口：

   • List：支持按索引随机访问、插入和删除操作。
   • Deque：支持双端队列操作。
   • Queue：支持队列操作。

3. 操作特性：

   • 插入和删除效率高：在头部或尾部插入和删除操作的时间复杂度为 $O(1)$。
   • 随机访问效率低：需要遍历链表查找元素，时间复杂度为 $O(n)$。

---

2. LinkedList 的构造方法

LinkedList 提供了以下两种构造方法：

1. 无参构造：

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

   创建一个空的链表。

2. 带集合参数的构造：

   List<Integer> arrayList = Arrays.asList(1, 2, 3);
   LinkedList<Integer> list = new LinkedList<>(arrayList);
   

   使用另一个集合初始化链表。

---

3. 常用方法

LinkedList 继承了 List 和 Deque 的所有方法。以下是常用方法的分类及示例：

3.1 添加元素

• 尾部添加：

  list.add(10);  // 在尾部添加元素
  

• 指定位置添加：

  list.add(1, 20);  // 在索引 1 处插入元素 20
  

• 头部添加：

  list.addFirst(5);  // 在头部添加元素
  

• 尾部添加：

  list.addLast(15);  // 在尾部添加元素
  

---

3.2 删除元素

• 删除头部元素：

  list.removeFirst();  // 删除并返回头部元素
  

• 删除尾部元素：

  list.removeLast();  // 删除并返回尾部元素
  

• 删除指定位置元素：

  list.remove(2);  // 删除索引 2 处的元素
  

• 删除指定值：

  list.remove(Integer.valueOf(10));  // 删除第一个匹配值为 10 的元素
  

---

3.3 获取元素

• 头部或尾部元素：

  list.getFirst();  // 返回头部元素
  list.getLast();   // 返回尾部元素
  

• 指定位置元素：

  list.get(2);  // 返回索引 2 处的元素
  

---

3.4 检查元素

• 是否包含某个元素：

  list.contains(20);  // 检查链表是否包含值为 20 的元素
  

• 是否为空：

  list.isEmpty();  // 检查链表是否为空
  

---

3.5 迭代元素

• 普通 for 循环：

  for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));
  }
  

• 增强 for 循环：

  for (Integer num : list) {System.out.println(num);
  }
  

• 使用迭代器：

  Iterator<Integer> iterator = list.iterator();
  while (iterator.hasNext()) {System.out.println(iterator.next());
  }
  

---

3.6 双端队列操作

LinkedList 实现了 Deque 接口，支持双端队列的操作。

• 入队（头部或尾部）：

  list.offerFirst(1);  // 在头部添加元素
  list.offerLast(2);   // 在尾部添加元素
  

• 出队（头部或尾部）：

  list.pollFirst();  // 删除并返回头部元素
  list.pollLast();   // 删除并返回尾部元素
  

---

3.7 栈操作

LinkedList 也可以用作栈，支持栈的基本操作。

• 压栈：

  list.push(10);  // 将元素压入栈顶（头部）
  

• 出栈：

  list.pop();  // 弹出栈顶元素（头部）
  

---

4. 示例代码

以下是一个综合使用 LinkedList 的示例：

import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();// 添加元素list.add(10);list.add(20);list.add(30);list.addFirst(5);list.addLast(40);System.out.println("链表内容: " + list);// 删除元素list.removeFirst();list.removeLast();list.remove(Integer.valueOf(20));System.out.println("删除元素后的链表: " + list);// 获取元素System.out.println("头部元素: " + list.getFirst());System.out.println("尾部元素: " + list.getLast());// 检查元素System.out.println("是否包含 30: " + list.contains(30));// 使用栈操作list.push(50);  // 压栈System.out.println("压栈后的链表: " + list);list.pop();     // 出栈System.out.println("出栈后的链表: " + list);// 使用队列操作list.offerFirst(5);  // 入队头部list.offerLast(60);  // 入队尾部System.out.println("使用队列操作后的链表: " + list);// 遍历元素System.out.println("遍历链表:");for (Integer num : list) {System.out.println(num);}}
}

输出：

链表内容: [5, 10, 20, 30, 40]
删除元素后的链表: [10, 30]
头部元素: 10
尾部元素: 30
是否包含 30: true
压栈后的链表: [50, 10, 30]
出栈后的链表: [10, 30]
使用队列操作后的链表: [5, 10, 30, 60]
遍历链表:
5
10
30
60

---

5. LinkedList 的时间复杂度

操作	时间复杂度	原因
插入（头部/尾部）	$O(1)$	双向链表操作，直接修改指针即可
删除（头部/尾部）	$O(1)$	双向链表操作，直接修改指针即可
按索引访问元素	$O(n)$	需要从头部或尾部遍历到指定位置
查找某个元素	$O(n)$	遍历整个链表
插入/删除（中间位置）	$O(n)$	需要先遍历找到位置，然后修改指针

---

6. LinkedList 的优缺点

优点：

1. 适合频繁插入和删除操作。
2. 实现了多种接口（List、Deque、Queue），功能强大。
3. 支持双端操作（头部和尾部操作都高效）。

缺点：

1. 随机访问性能差，需要遍历链表，时间复杂度为 $O(n)$。
2. 占用额外的内存空间（指针存储前驱和后继节点）。

---

7. 总结

• 适用场景：

  • 数据插入和删除频繁的场景（如队列、栈操作）。
  • 数据大小较小，链表的额外内存开销可以接受。

• 不适用场景：

  • 随机访问频繁的场景（推荐使用 ArrayList
    ）。

通过合理选择数据结构，可以根据具体需求提高程序性能和代码效率。