Java 数据结构
Java 中常见数据结构的对应实现与选择依据。
常见数据结构与 Java 实现
Java ships the common structures in its collections framework, so you rarely implement them. Choose by operation mix: read-heavy or write-heavy, ordered or not, duplicates allowed or not.
| Structure | Java type | Best at |
|---|---|---|
| Dynamic array | ArrayList | Random access O(1) |
| Linked list | LinkedList | Insert/remove at ends |
| Stack | ArrayDeque | LIFO push/pop |
| Queue | ArrayDeque / LinkedList | FIFO offer/poll |
| Hash table | HashMap | Key lookup O(1) |
| Sorted map | TreeMap | Ordered keys O(log n) |
| Set | HashSet / TreeSet | Deduplication |
栈与队列的用法
Avoid the legacy Stack class; ArrayDeque serves as both stack and queue — push/pop for LIFO and offer/poll for FIFO.
import java.util.ArrayDeque;
import java.util.Deque;
public class StackQueue {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());
System.out.println(stack);
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll());
System.out.println(queue);
}
}2
[1]
1
[2]复杂度速查
Decide the dominant operation first. ArrayList reads by index in O(1) but inserts mid-list in O(n); LinkedList is the reverse; HashMap averages O(1) but is unordered; TreeMap is O(log n) with sorted keys.
| Operation | ArrayList | LinkedList | HashMap |
|---|---|---|---|
| get(i) | O(1) | O(n) | — |
| add(end) | O(1)* | O(1) | O(1)* |
| add(middle) | O(n) | O(1) | — |
| remove(middle) | O(n) | O(1) | O(1)* |
| contains | O(n) | O(n) | O(1) |
常见数据结构与 Java 实现
Java 把常用数据结构都封装在集合框架里，一般不需要自己写。选型的关键是看清操作频率：读多写少还是写多读少，是否需要有序、是否需要去重。
| 结构 | Java 实现 | 优势 |
|---|---|---|
| 动态数组 | ArrayList | 随机访问 O(1) |
| 链表 | LinkedList | 两端增删 |
| 栈 | ArrayDeque | 后进先出 |
| 队列 | ArrayDeque / LinkedList | 先进先出 |
| 哈希表 | HashMap | 按键查找 O(1) |
| 有序映射 | TreeMap | 有序键 O(log n) |
| 集合 | HashSet / TreeSet | 去重 |
栈与队列的用法
Java 不推荐用遗留的 Stack 类，官方建议用 ArrayDeque 同时实现栈和队列：push/pop 是栈语义，offer/poll 是队列语义。
import java.util.ArrayDeque;
import java.util.Deque;
public class StackQueue {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());
System.out.println(stack);
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll());
System.out.println(queue);
}
}2
[1]
1
[2]复杂度速查
选容器前先想清楚主要操作。ArrayList 按下标读是 O(1) 但中间插入是 O(n)；LinkedList 相反；HashMap 平均 O(1) 但无序；TreeMap O(log n) 且键有序。
| 操作 | ArrayList | LinkedList | HashMap |
|---|---|---|---|
| get(i) | O(1) | O(n) | — |
| 尾部添加 | O(1)* | O(1) | O(1)* |
| 中间插入 | O(n) | O(1) | — |
| 中间删除 | O(n) | O(1) | O(1)* |
| 是否包含 | O(n) | O(n) | O(1) |