Java—— ArrayList 和 LinkedList 详解

一、数据结构与核心特性

1. ArrayList

• 数据结构：基于动态数组实现，元素存储在连续内存中。
• 核心特性： – 通过索引随机访问元素，时间复杂度 O (1)。 – 扩容机制：容量不足时新建数组（原容量的 1.5 倍）并复制元素。 – 尾部添加 / 删除效率高（O (1)），中间操作需移动元素（O (n)）。 – 不直接支持 poll/offer，需借助 ArrayDeque 或 LinkedList 包装。

2. LinkedList

• 数据结构：双向链表，每个节点包含前驱、后继指针和元素值。
• 核心特性： – 任意位置插入 / 删除仅需修改指针（O (1)），但随机访问需遍历（O (n)）。 – 实现 Deque 接口，原生支持 poll/offer 等队列操作。 – 无容量限制，节点动态分配内存，内存占用高于 ArrayList。

二、核心方法对比

三、poll 和 offer 方法详解

1. 方法定义与功能

• poll()：获取并移除集合头部元素，空集合返回 null（区别于 remove() 的异常）。
• offer(E e)：添加元素到集合，成功返回 true（LinkedList 无容量限制，始终成功）。

2. LinkedList 中的队列操作

LinkedList<String> deque = new LinkedList<>();
// 添加元素
deque.offer("A"); // 尾部添加，等价于 addLast()
deque.offerFirst("B"); // 头部添加
deque.offerLast("C"); // 尾部添加，等价于 offer()

// 获取并移除元素
String head = deque.poll(); // 取头部（"B"），队列变为 ["A", "C"]
String tail = deque.pollLast(); // 取尾部（"C"），队列变为 ["A"]

// 空集合处理
String empty = deque.poll(); // 返回 null，不抛异常

3. ArrayList 实现队列操作（需适配器）

// 推荐方式：使用 ArrayDeque 包装 ArrayList
Deque<Integer> queue = new ArrayDeque<>(Arrays.asList(1, 2, 3));
queue.offer(4); // 尾部添加，队列变为 [1,2,3,4]
int first = queue.poll(); // 取头部（1），队列变为 [2,3,4]

// 不推荐方式：用 LinkedList 包装 ArrayList（性能差）
Queue<Integer> arrayListQueue = new LinkedList<>(new ArrayList<>());
arrayListQueue.offer(5); // 内部通过链表添加，非数组直接操作

四、性能与适用场景

1. 性能对比

2. 适用场景

• 选 ArrayList 的场景：
  • 频繁随机访问（如 get(index)）。
  • 尾部添加 / 删除为主（如日志记录）。
  • 数据量可预测，避免频繁扩容。
• 选 LinkedList 的场景：
  • 频繁在头部 / 中间插入 / 删除（如任务队列）。
  • 需要使用 poll/offer 等双端队列操作。
  • 数据量不确定，不希望有扩容开销。

五、代码示例：综合应用

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class ListComparison {
public static void main(String[] args) {
// === ArrayList 作为普通列表 ===
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("苹果");
arrayList.add("香蕉");
System.out.println("ArrayList 随机访问：" + arrayList.get(1)); // 输出：香蕉

// === LinkedList 作为队列 ===
Queue<String> taskQueue = new LinkedList<>();
taskQueue.offer("数据采集");
taskQueue.offer("模型训练");
System.out.println("队列处理顺序：");
while (!taskQueue.isEmpty()) {
System.out.println("- " + taskQueue.poll()); // 按添加顺序输出
}

// === LinkedList 作为栈 ===
Deque<String> stack = new LinkedList<>();
stack.offerFirst("HTML");
stack.offerFirst("CSS");
stack.offerFirst("JavaScript");
System.out.println("\\n栈弹出顺序：");
while (!stack.isEmpty()) {
System.out.println("- " + stack.pollFirst()); // 后入先出
}

// === ArrayList 实现队列（借助 ArrayDeque）===
Deque<Integer> arrayQueue = new ArrayDeque<>(Arrays.asList(10, 20));
arrayQueue.offer(30); // 尾部添加
System.out.println("\\nArrayDeque 包装 ArrayList 队列：");
while (!arrayQueue.isEmpty()) {
System.out.println("- " + arrayQueue.poll()); // 10, 20, 30
}
}
}

六、总结与注意事项

1. 数据结构决定性能：

• ArrayList 适合 “读多写少” 场景，尤其随机访问频繁时。
• LinkedList 适合 “写多读少” 场景，尤其需要队列 / 栈操作时。

2. 队列操作的最佳实践：

• 优先使用 LinkedList 或 ArrayDeque 实现队列 / 栈，而非包装 ArrayList。
• ArrayDeque 的性能通常优于 LinkedList，因数组连续存储减少内存跳转。

3. 线程安全：

• 两者均非线程安全，多线程环境需用 Collections.synchronizedList() 包装或使用 CopyOnWriteArrayList。

通过理解两者的底层实现与方法特性，可根据业务场景（如数据访问模式、操作频率）选择更合适的集合类，优化程序效率。