在 Java 中,常用的数据结构可以通过 集合框架(Collections Framework) 实现,也可以手动实现。以下是常见数据结构及其特点,以及对应的 Java 实现示例:
1. 数组(Array)
- 特点:固定大小、内存连续、随机访问高效。
- 用途:存储固定数量的元素。
- Java 实现:
int[] array = new int[5]; // 静态数组 array[0] = 10;
2. 动态数组(ArrayList)
- 特点:基于数组实现,支持动态扩容,随机访问高效(O(1)),插入/删除低效(O(n))。
- 用途:需要频繁随机访问的场景。
- Java 实现:
import java.util.ArrayList; ArrayList<Integer> list = new ArrayList<>(); list.add(10); // 添加元素 int value = list.get(0); // 访问元素
3. 链表(LinkedList)
- 特点:基于双向链表实现,插入/删除高效(O(1)),随机访问低效(O(n))。
- 用途:频繁插入/删除的场景。
- Java 实现:
import java.util.LinkedList; LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(10); // 添加元素 linkedList.addFirst(5); // 头部插入 int first = linkedList.getFirst(); // 访问头部元素
4. 栈(Stack)
- 特点:后进先出(LIFO),支持
push
和pop
操作。 - 用途:函数调用栈、表达式求值。
- Java 实现(推荐使用
Deque
):import java.util.ArrayDeque; ArrayDeque<Integer> stack = new ArrayDeque<>(); stack.push(10); // 压栈 int top = stack.pop(); // 弹栈
5. 队列(Queue)
- 特点:先进先出(FIFO),支持
offer
和poll
操作。 - 用途:任务调度、广度优先搜索(BFS)。
- Java 实现:
import java.util.Queue; import java.util.LinkedList; Queue<Integer> queue = new LinkedList<>(); queue.offer(10); // 入队 int head = queue.poll(); // 出队
6. 哈希表(HashMap)
- 特点:基于哈希表实现,键值对存储,查找高效(平均 O(1)),无序。
- 用途:快速查找、去重。
- Java 实现:
import java.util.HashMap; HashMap<String, Integer> map = new HashMap<>(); map.put("Alice", 25); // 添加键值对 int age = map.get("Alice"); // 查找
7. 树(TreeSet/TreeMap)
- 特点:基于红黑树实现,元素自动排序(按自然顺序或自定义比较器),查找/插入/删除时间复杂度为 O(log n)。
- 用途:需要有序存储的场景。
- Java 实现:
import java.util.TreeSet; TreeSet<Integer> treeSet = new TreeSet<>(); treeSet.add(10); treeSet.add(5); // 自动排序为 [5, 10]
8. 堆(PriorityQueue)
- 特点:基于堆(默认最小堆)实现,元素按优先级排序。
- 用途:任务调度、求 Top K 问题。
- Java 实现:
import java.util.PriorityQueue; PriorityQueue<Integer> heap = new PriorityQueue<>(); heap.offer(10); heap.offer(5); // 堆顶为 5 int min = heap.poll(); // 弹出最小值 5
9. 图(Graph)
- 特点:节点和边的集合,通常通过邻接表或邻接矩阵实现。
- 用途:社交网络、路径规划。
- Java 实现(邻接表):
import java.util.*; class Graph {private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();public void addEdge(int src, int dest) {adjacencyList.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);adjacencyList.computeIfAbsent(dest, k -> new ArrayList<>()).add(src); // 无向图} }
10. 集合(Set)
- 特点:不允许重复元素。
- Java 实现(
HashSet
和TreeSet
):import java.util.HashSet; HashSet<String> set = new HashSet<>(); set.add("Apple"); set.add("Apple"); // 重复元素会被忽略
11. 双向队列(Deque)
- 特点:支持两端插入和删除。
- 用途:滑动窗口、双端操作。
- Java 实现:
import java.util.ArrayDeque; ArrayDeque<Integer> deque = new ArrayDeque<>(); deque.addFirst(10); deque.addLast(20); int first = deque.removeFirst();
12. 自定义链表(手动实现)
class Node {int data;Node next;Node(int data) {this.data = data;this.next = null;}
}class LinkedList {Node head;public void add(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;}}
}
总结
Java 提供了丰富的内置数据结构(通过 java.util
包),开发者可以根据需求选择合适的结构:
- 快速查找:
HashMap
、HashSet
- 有序存储:
TreeMap
、TreeSet
- 高效插入/删除:
LinkedList
、ArrayDeque
- 动态扩容:
ArrayList
- 优先级处理:
PriorityQueue
掌握这些数据结构的特点和使用场景,可以显著提升代码效率和可维护性!