一、数据结构与核心特性
1. ArrayList
- 数据结构：基于动态数组实现，元素存储在连续内存中。
- 核心特性：
– 通过索引随机访问元素，时间复杂度 O (1)。
– 扩容机制：容量不足时新建数组（原容量的 1.5 倍）并复制元素。
– 尾部添加 / 删除效率高（O (1)），中间操作需移动元素（O (n)）。
– 不直接支持 poll/offer，需借助 ArrayDeque 或 LinkedList 包装。
2. LinkedList
- 数据结构：双向链表，每个节点包含前驱、后继指针和元素值。
- 核心特性：
– 任意位置插入 / 删除仅需修改指针（O (1)），但随机访问需遍历（O (n)）。
– 实现 Deque 接口，原生支持 poll/offer 等队列操作。
– 无容量限制，节点动态分配内存，内存占用高于 ArrayList。
二、核心方法对比
| 操作类型 | ArrayList | LinkedList |
|---|
| 构造 | new ArrayList<>()（初始容量 10） | new LinkedList<>() |
| 添加元素 | add(E e)（尾部，O(1)）
add(index, e)（中间，O(n)） | add(e)（尾部，O(1)）
addFirst(e) / addLast(e)（O(1)） |
| 删除元素 | remove(index)（O(n)） | removeFirst() / removeLast()（O(1)） |
| 随机访问 | get(index)（O(1)） | get(index)（O(n)，需遍历链表） |
| 队列操作（poll） | 需包装为 ArrayDeque，本质数组操作 | poll()（取头部，O(1)）
pollFirst() / pollLast()（O(1)） |
| 队列操作（offer） | 需包装为 ArrayDeque，尾部添加 O(1) | offer(e)（尾部，O(1)）
offerFirst(e) / offerLast(e)（O(1)） |
三、poll 和 offer 方法详解
1. 方法定义与功能
- poll()：获取并移除集合头部元素，空集合返回 null（区别于 remove() 的异常）。
- offer(E e)：添加元素到集合，成功返回 true（LinkedList 无容量限制，始终成功）。
2. LinkedList 中的队列操作
LinkedList<String> deque = new LinkedList<>();
deque.offer("A");
deque.offerFirst("B");
deque.offerLast("C");
String head = deque.poll();
String tail = deque.pollLast();
String empty = deque.poll();
3. ArrayList 实现队列操作（需适配器）
Deque<Integer> queue = new ArrayDeque<>(Arrays.asList(1, 2, 3));
queue.offer(4);
int first = queue.poll();
Queue<Integer> arrayListQueue = new LinkedList<>(new ArrayList<>());
arrayListQueue.offer(5);
四、性能与适用场景
1. 性能对比
| 操作 | ArrayList | LinkedList |
|---|
| 尾部添加 | O(1) | O(1) |
| 中间插入 | O(n) (移动元素) | O(1) (修改指针) |
| 随机访问 | O(1) | O(n) (遍历链表) |
| poll/offer 头部 | 需适配器，O(1) | O(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<String> arrayList = new ArrayList<>();arrayList.add("苹果");arrayList.add("香蕉");System.out.println("ArrayList 随机访问：" + arrayList.get(1)); Queue<String> taskQueue = new LinkedList<>();taskQueue.offer("数据采集");taskQueue.offer("模型训练");System.out.println("队列处理顺序：");while (!taskQueue.isEmpty()) {System.out.println("- " + taskQueue.poll()); }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()); }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()); }}
}
六、总结与注意事项
1. 数据结构决定性能：
- ArrayList 适合 “读多写少” 场景，尤其随机访问频繁时。
- LinkedList 适合 “写多读少” 场景，尤其需要队列 / 栈操作时。
2. 队列操作的最佳实践：
- 优先使用 LinkedList 或 ArrayDeque 实现队列 / 栈，而非包装 ArrayList。
- ArrayDeque 的性能通常优于 LinkedList，因数组连续存储减少内存跳转。
3. 线程安全：
- 两者均非线程安全，多线程环境需用 Collections.synchronizedList() 包装或使用 CopyOnWriteArrayList。
通过理解两者的底层实现与方法特性，可根据业务场景（如数据访问模式、操作频率）选择更合适的集合类，优化程序效率。
