List 与 Set

约 1006 字大约 3 分钟

布欧-Lewyon

2026-05-15

首页 › Java › 集合 › List 与 Set

集合框架中最核心的两个接口是 List（有序列表，允许重复）和 Set（唯一集合，不允许重复）。理解它们各自的契约与实现差异，是日常编码的基础。

集合框架概览

Collection (接口)
├── List（有序、可重复）── ArrayList, LinkedList
├── Set（不可重复）      ── HashSet, TreeSet, LinkedHashSet
└── Queue（队列）        ── ArrayDeque, LinkedList

所有集合都继承 Collection 接口，因此共享 add、remove、contains、size、isEmpty、clear 等基础方法。

`List` 接口

List 维护元素的插入顺序，允许重复元素，可通过索引访问。

ArrayList

ArrayList 基于动态数组实现。它在内存中是连续空间，因此随机访问（按索引 get/set）是 O(1)；但中间插入和删除需要移动后续元素，为 O(n)。

List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("Go");
list.add(1, "C++");        // 在索引 1 处插入
String lang = list.get(2);  // "Go"（随机访问 O(1)）
list.remove(0);             // 删除后后续元素前移

初始容量默认 10，超出时自动扩容（约 1.5 倍）；预知元素量时可通过构造器或 ensureCapacity 优化。
ArrayList 与 LinkedList 的选择：绝大多数场景首选 ArrayList；仅在频繁头部插入/删除时考虑 LinkedList。

LinkedList

LinkedList 基于双向链表实现。头尾插入/删除为 O(1)；按索引访问为 O(n)。它同时实现了 List 和 Deque，可用作队列或双端队列：

LinkedList<String> stack = new LinkedList<>();
stack.push("A");   // 入栈（头部插入）
stack.push("B");
stack.pop();       // 出栈 -> "B"

LinkedList<String> queue = new LinkedList<>();
queue.offer("X");  // 入队（尾部插入）
queue.offer("Y");
queue.poll();      // 出队 -> "X"

遍历 List

// 方式一：增强 for
for (String s : list) {
    System.out.println(s);
}

// 方式二：forEach + Lambda（Java 8+）
list.forEach(System.out::println);

// 方式三：传统 for + 索引（需要索引时）
for (int i = 0; i < list.size(); i++) {
    System.out.println(i + ": " + list.get(i));
}

不要在增强 for 循环中删除元素——会抛 ConcurrentModificationException。需要遍历中删除时使用显式 Iterator。

`Set` 接口

Set 保证元素不重复（基于 equals 判断）。三个主要实现各有不同的顺序保证。

HashSet

HashSet 基于 HashMap 实现，不保证迭代顺序，查找效率 O(1)：

Set<String> set = new HashSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");
set.add("apple");      // 重复，不会添加
System.out.println(set.size()); // 3

HashSet 依赖 hashCode() 和 equals() 判断重复，存入的自定义对象必须正确重写这两个方法（见 Map 与 hashCode/equals）。
大多数场景的首选 Set 实现。

TreeSet

TreeSet 基于红黑树，元素按键排序（自然顺序或自定义 Comparator），操作 O(log n)：

Set<String> sorted = new TreeSet<>(Set.of("banana", "apple", "cherry"));
System.out.println(sorted);  // [apple, banana, cherry]（字母序）

元素必须实现 Comparable，或在构造时传入 Comparator，否则 ClassCastException。
适用需要有序且不重复的场景。与 HashSet 联合使用时，可先用 HashSet 构建再复制到 TreeSet 排序。

LinkedHashSet

LinkedHashSet 用哈希表维护唯一性，同时用链表维护插入顺序，性能接近 HashSet：

Set<String> linked = new LinkedHashSet<>();
linked.add("banana");
linked.add("apple");
System.out.println(linked);  // [banana, apple]（保持插入顺序）

Queue 与 Deque（简）

Queue：FIFO 队列，常用 offer/poll/peek。
Deque：双端队列，支持两端插入/删除；ArrayDeque 比 LinkedList 做队列/栈时更高效。

Queue<String> q = new ArrayDeque<>();
q.offer("A");
q.offer("B");
String head = q.poll();  // "A"

小结

List 有序可重复：ArrayList（随机访问快，默认首选） vs LinkedList（头尾操作快）。
Set 不可重复：HashSet（最快、无序）、LinkedHashSet（保留插入顺序）、TreeSet（排序）。
Queue/Deque 用于队列和双端队列场景，ArrayDeque 性能优于 LinkedList。
增强 for 遍历时禁止修改集合结构（增删元素），否则抛 ConcurrentModificationException。
易错：Set.contains(obj) 依赖 equals 和 hashCode；自定义对象存入 HashSet 后若修改了参与 hashCode 计算的字段，会导致无法正确移除或查找。
思考任务：创建一个 ArrayList 包含若干元素，用 Collections.shuffle 打乱顺序；然后用 LinkedHashSet 去重同时保留首次出现的顺序。

上一节：泛型基础

下一节：Map 与 hashCode/equals