当前位置：首页 > ops >正文

Java—— ArrayList 和 LinkedList 详解

ops 2025/6/17 20:10:10

一、数据结构与核心特性

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");       // 尾部添加，等价于 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. 性能对比

操作	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 作为普通列表 ===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}}
}