在软件开发领域,java 数据结构以及算法是程序员必须掌握的核心能力。无论您是初学者还是资深工程师,扎实的数据结构与算法功底,都是应对复杂业务逻辑、优化系统性能、高效解决问题的基石。本页面围绕java 数据结构以及算法展开系统性讲解,结合实际场景与代码实践,帮助您构建完整的知识体系。
当前,随着互联网应用日益复杂,对程序执行效率与资源利用率的要求持续提升,单纯依靠业务逻辑堆砌已无法满足高性能、高并发系统的设计需求。此时,合理选择与运用数据结构与算法,便成为提升系统稳定性和响应速度的关键所在。尤其在Java生态中,JDK内置了丰富且高效的集合框架(如ArrayList、HashMap、TreeMap等),其底层实现均依赖于经典的数据结构与算法思想。深入理解其原理,不仅有助于我们“知其然,更知其所以然”,更能指导我们在实际开发中做出更优的技术选型。
本页面内容涵盖:线性结构(数组、链表、栈与队列)、树形结构(二叉树、AVL树、红黑树、B树)、图结构、常用排序与查找算法、动态规划与贪心策略等核心模块,并辅以LeetCode高频题型解析、Java集合源码剖析、并发场景下的数据结构选择建议等实战内容,力求构建从理论到落地的完整闭环。
特别说明:本文内容严格遵循java 数据结构以及算法教学逻辑,所有示例均使用标准Java 11+语法编写,确保可运行性与可迁移性。所有时间复杂度、空间复杂度分析均基于大O表示法,符合计算机科学通用规范。
数组(Array)是内存中连续存储的线性结构,支持O(1)时间复杂度的随机访问,适用于读多写少、元素固定不变的场景。例如:在图像处理中,像素点坐标映射为二维数组,可快速定位像素值;在数据库索引结构(如B+树叶子节点)中,也常以数组形式存储有序键值对。
但数组存在插入/删除成本高(O(n))、需预分配空间等缺点。链表(Linked List)通过指针连接节点,支持O(1)时间复杂度的插入与删除(已知节点位置),适用于频繁修改结构的场景。例如:浏览器历史记录管理,使用双向链表可高效实现“前进/后退”功能。
// 一维数组定义与遍历
int[] arr = new int[]{10, 20, 30, 40, 50};
for (int i = 0; i < arr.length; i++) {
System.out.println("Index " + i + ": " + arr[i]);
}
// 二维数组(矩阵)初始化
int[][] matrix = new int[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
matrix[i][j] = i * 3 + j + 1;
}
}
// 输出:1 2 3
// 4 5 6
// 7 8 9
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
// 创建链表:1 → 2 → 3
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
// 插入节点(在值为2的节点后插入4)
ListNode node2 = head.next;
ListNode newNode = new ListNode(4);
newNode.next = node2.next;
node2.next = newNode;
// 遍历链表
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " → ");
curr = curr.next;
}
// 输出:1 → 2 → 4 → 3 →
栈(Stack)遵循“后进先出”(LIFO)原则,典型应用包括函数调用栈、表达式求值、括号匹配、撤销操作(Undo)等。队列(Queue)遵循“先进先出”(FIFO)原则,广泛用于任务调度、缓冲区管理、广度优先搜索(BFS)等场景。
public static boolean isValid(String s) {
Deque stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue queue = new LinkedList<>();
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) return depth;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
depth++;
}
return depth;
}
树(Tree)是典型的非线性结构,具有层次关系。二叉树作为最基础的树形结构,是理解递归、分治思想的重要载体。Java中TreeMap与TreeSet底层基于红黑树实现,保证了排序与查找性能的平衡。
四种遍历方式:
public void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
这些性质保证了红黑树最长路径不超过最短路径的2倍,从而确保插入、删除、查找操作时间复杂度为O(log n),适用于频繁动态更新的场景。
InnoDB存储引擎的聚簇索引基于B+树实现。其特点包括:
例如:SELECT * FROM users WHERE id BETWEEN 1000 AND 2000;B+树可快速定位起始节点,再顺序遍历链表,避免全表扫描。
图(Graph)由顶点(Vertex)和边(Edge)组成,适用于社交网络、地图导航、依赖关系分析等场景。Java中可通过邻接表(Adjacency List)高效表示稀疏图。
class Graph {
private int V; // 顶点数
private LinkedList adj[]; // 邻接表数组
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<>();
}
void addEdge(int v, int w) {
adj[v].add(w); // 无向图需同时 adj[w].add(v)
}
}
例如:在Java微服务架构中,服务依赖关系可用有向图建模,通过拓扑排序判断是否存在循环依赖,保障系统部署顺序正确性。
排序是数据处理的基础操作。Java中Arrays.sort()对对象使用Timsort(归并+插入优化),对基本类型使用Dual-Pivot Quicksort(双轴快速排序),兼顾稳定性与效率。
| 算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| Timsort | O(n log n) | O(n log n) | O(n) | 稳定 |
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
二分查找(Binary Search)是有序数组查找的黄金标准,时间复杂度O(log n)。其变体包括旋转数组查找、二维矩阵查找等,广泛用于数据库索引、内存页表管理。
public int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
注意:实际应用中需确保数组有序;若存在重复元素,可扩展为查找左边界或右边界。
Java的HashMap通过哈希函数将键映射到桶(Bucket),再结合链表/红黑树解决冲突,平均查找时间复杂度为O(1)。关键点包括:
例如:在用户登录系统中,通过用户名(Key)快速查询用户信息,HashMap提供毫秒级响应。
递归(Recursion)通过函数自调用解决问题,典型应用包括树遍历、阶乘、斐波那契数列等。分治(Divide and Conquer)将大问题分解为子问题,递归求解后合并结果,如归并排序、快速排序。
public long fib(int n, long[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}
// 调用方式
long[] memo = new long[50];
System.out.println(fib(45, memo)); // 输出1134903170
将数组递归二分,直至子数组长度为1,再合并两个有序子数组:
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, 0, arr, left, temp.length);
}
动态规划(DP)通过状态转移方程求解最优子结构问题,适用于重叠子问题场景(如背包问题、最长公共子序列)。贪心算法在每一步选择局部最优,期望达到全局最优(如活动选择、霍夫曼编码)。
public int knapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
状态定义:dp[w]表示容量为w时的最大价值;状态转移:不选当前物品或选(需确保容量足够)。
按结束时间排序,每次选择最早结束且不冲突的活动:
class Activity {
int start, end;
Activity(int s, int e) { start = s; end = e; }
}
public List selectActivities(List acts) {
acts.sort((a, b) -> a.end - b.end);
List result = new ArrayList<>();
int lastEnd = -1;
for (Activity a : acts) {
if (a.start >= lastEnd) {
result.add(a);
lastEnd = a.end;
}
}
return result;
}
以下题目来自阿里、腾讯、字节等一线大厂技术面试,覆盖数据结构与算法核心考点:
解法:快慢指针(Floyd判圈算法)。
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
扩容机制:当size > capacity * loadFactor时触发,新容量为原容量2倍,需重新哈希(rehash)。
红黑树转换:链表长度≥8且容量≥64时转红黑树;长度≤6时退化为链表。
思路:后序遍历,计算每个节点作为最高点的路径和(左子树最大贡献 + 右子树最大贡献 + 节点值),同时维护全局最大值。
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, left + right + node.val);
return Math.max(left, right) + node.val;
}
| 操作类型 | 数组 | 链表 | 栈/队列 | 哈希表 | 二叉搜索树 |
|---|---|---|---|---|---|
| 访问 | O(1) | O(n) | - | - | O(log n) |
| 搜索 | O(n) | O(n) | - | O(1) | O(log n) |
| 插入 | O(n) | O(1) | O(1) | O(1) | O(log n) |
| 删除 | O(n) | O(1) | O(1) | O(1) | O(log n) |