Java 数据结构详细学习笔记

目录

1. 概述与复杂度分析
2. 数组 (Array)
3. 链表 (Linked List)
4. 栈 (Stack)
5. 队列 (Queue)
6. 哈希表 (Hash Table)
7. 树 (Tree)
8. 堆 (Heap)
9. 图 (Graph)
10. Java 集合框架总结

---

1. 概述与复杂度分析

1.1 什么是数据结构

数据结构是计算机存储、组织数据的方式。选择合适的数据结构可以显著提高程序的运行效率和内存利用率。

1.2 时间复杂度与空间复杂度

• 时间复杂度 (Time Complexity): 衡量算法执行时间随数据规模增长的变化趋势。常用大 O 表示法 (Big O Notation)。
• 空间复杂度 (Space Complexity): 衡量算法执行过程中临时占用存储空间的大小。

1.3 常见复杂度排序 (从小到大)

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)$$

复杂度	名称	示例操作
$O(1)$	常数阶	数组随机访问、哈希表查找 (平均)
$O(\log n)$	对数阶	二分查找、平衡树操作
$O(n)$	线性阶	遍历数组、单链表查找
$O(n\log n)$	线性对数阶	快速排序、归并排序、堆排序
$O(n^2)$	平方阶	冒泡排序、插入排序、双重循环

---

2. 数组 (Array)

2.1 特点

• 连续内存: 在内存中连续存储。
• 随机访问: 通过下标直接访问元素，时间复杂度 $O(1)$。
• 固定长度: Java 中数组长度一旦创建不可改变。
• 插入/删除: 需要移动元素，平均时间复杂度 $O(n)$。

2.2 Java 实现

int[] arr = new int[5]; // 声明并初始化
arr[0] = 10;
int val = arr[0]; // O(1) 访问

// 动态扩容模拟 (ArrayList 底层原理)
public int[] resize(int[] oldArr, int newCapacity) {
    int[] newArr = new int[newCapacity];
    System.arraycopy(oldArr, 0, newArr, 0, oldArr.length);
    return newArr;
}

2.3 优缺点

• 优点: 访问速度快，内存利用率高（无额外指针开销）。
• 缺点: 插入删除慢，大小固定。

---

3. 链表 (Linked List)

3.1 特点

• 非连续内存: 节点在内存中任意分布，通过指针连接。
• 顺序访问: 必须从头节点遍历，时间复杂度 $O(n)$。
• 动态长度: 插入删除只需修改指针，无需移动元素。

3.2 分类

1. 单链表 (Singly Linked List): 每个节点指向下一个节点。
2. 双链表 (Doubly Linked List): 每个节点指向前一个和后一个节点。
3. 循环链表 (Circular Linked List): 尾节点指向头节点。

3.3 Java 实现 (单链表节点)

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// 插入节点 (在 head 之后)
public void insert(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head.next;
    head.next = newNode;
}

3.4 优缺点

• 优点: 插入删除效率高 ($O(1)$，已知节点位置)，动态扩容。
• 缺点: 不支持随机访问，额外内存开销 (指针)，缓存局部性差。

---

4. 栈 (Stack)

4.1 特点

• LIFO (Last In First Out): 后进先出。
• 操作: push (入栈), pop (出栈), peek (查看栈顶)。
• 复杂度: 所有操作均为 $O(1)$。

4.2 应用场景

• 函数调用栈 (递归)。
• 表达式求值 (括号匹配)。
• 撤销操作 (Undo)。

4.3 Java 实现

Java 中推荐使用 Deque 接口实现栈，而不是过时的 Stack 类。

import java.util.Deque;
import java.util.ArrayDeque;

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);       // 入栈
int top = stack.pop(); // 出栈
int peek = stack.peek(); // 查看栈顶

---

5. 队列 (Queue)

5.1 特点

• FIFO (First In First Out): 先进先出。
• 操作: offer (入队), poll (出队), peek (查看队头)。
• 变体:
  • 双端队列 (Deque): 两端都可以进出。
  • 优先队列 (PriorityQueue): 根据优先级出队，非严格 FIFO。

5.2 应用场景

• 任务调度。
• 广度优先搜索 (BFS)。
• 消息队列。

5.3 Java 实现

import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();
queue.offer(10);      // 入队
int head = queue.poll(); // 出队
int front = queue.peek(); // 查看队头

---

6. 哈希表 (Hash Table)

6.1 特点

• 键值对存储: Key-Value。
• 快速查找: 平均时间复杂度 $O(1)$。
• 哈希函数: 将 Key 映射为数组下标。
• 冲突解决:
  • 链地址法 (Chaining): Java HashMap 使用此法（数组 + 链表/红黑树）。
  • 开放寻址法 (Open Addressing): 线性探测、二次探测。

6.2 Java HashMap 原理 (JDK 1.8+)

• 结构: 数组 + 链表 + 红黑树。
• 扩容: 当元素个数 > 容量 * 负载因子 (默认 0.75) 时扩容 (2倍)。
• 树化: 当链表长度 > 8 且数组长度 > 64 时，链表转为红黑树，查找从 $O(n)$ 变为 $O(\log n)$。
• Key 要求: 必须重写 hashCode() 和 equals() 方法。

6.3 代码示例

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> map = new HashMap<>();
map.put("Java", 1);
map.put("Python", 2);
int val = map.get("Java"); // O(1)
boolean exists = map.containsKey("Java");

---

7. 树 (Tree)

7.1 二叉树 (Binary Tree)

• 每个节点最多有两个子节点 (左子树、右子树)。
• 遍历方式:
  • 前序 (Pre-order): 根 -> 左 -> 右
  • 中序 (In-order): 左 -> 根 -> 右 (二叉搜索树中序遍历为有序序列)
  • 后序 (Post-order): 左 -> 右 -> 根
  • 层序 (Level-order): 使用队列实现 BFS。

7.2 二叉搜索树 (BST)

• 左子树所有节点 < 根节点 < 右子树所有节点。
• 查找、插入、删除平均 $O(\log n)$，最坏 $O(n)$ (退化为链表)。

7.3 平衡二叉树 (AVL / Red-Black Tree)

• AVL 树: 严格平衡，左右子树高度差 <= 1。
• 红黑树: 弱平衡，通过颜色约束保证最长路径不超过最短路径的 2 倍。
  • Java TreeMap 和 TreeSet 底层使用红黑树。
  • 保证最坏情况 $O(\log n)$。

7.4 Java 实现示例 (BST 节点)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// 中序遍历递归
void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

---

8. 堆 (Heap)

8.1 特点

• 完全二叉树: 除了最后一层，其他层全满，最后一层靠左。
• 堆性质:
  • 大顶堆: 父节点 >= 子节点 (根节点最大)。
  • 小顶堆: 父节点 <= 子节点 (根节点最小)。
• 操作: 插入 $O(\log n)$, 删除堆顶 $O(\log n)$, 获取堆顶 $O(1)$。

8.2 应用场景

• Top K 问题。
• 优先级队列。
• 堆排序。

8.3 Java 实现

Java 的 PriorityQueue 默认是小顶堆。

import java.util.PriorityQueue;

// 小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
int min = minHeap.poll(); // 1

// 大顶堆 (自定义比较器)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

---

9. 图 (Graph)

9.1 基本概念

• 顶点 (Vertex) 和 边 (Edge)。
• 有向图 / 无向图。
• 加权图 / 无权图。

9.2 存储方式

1. 邻接矩阵 (Adjacency Matrix):
   • 二维数组 matrix[i][j]。
   • 适合稠密图。
   • 空间复杂度 $O(V^2)$。
2. 邻接表 (Adjacency List):
   • 数组 + 链表/列表。
   • 适合稀疏图。
   • 空间复杂度 $O(V+E)$。

9.3 遍历算法

• DFS (深度优先搜索): 递归或栈。
• BFS (广度优先搜索): 队列。

9.4 经典算法

• 最短路径: Dijkstra (单源), Floyd (多源)。
• 最小生成树: Prim, Kruskal。
• 拓扑排序: 解决依赖关系。

---

10. Java 集合框架总结

Java 提供了强大的 java.util 包，涵盖了上述所有数据结构。

接口/类	底层实现	特点	适用场景
List		有序，可重复
ArrayList	动态数组	随机访问快，增删慢	读多写少
LinkedList	双向链表	增删快，随机访问慢	频繁增删，作为栈/队列
Vector	动态数组 (同步)	线程安全，性能低	不推荐，用 CopyOnWriteArrayList
Set		无序 (部分有序)，不可重复
HashSet	哈希表	查找快，无序	去重
LinkedHashSet	哈希表 + 链表	保持插入顺序	去重且需顺序
TreeSet	红黑树	自然排序或自定义排序	需要排序的去重
Map		Key-Value 映射
HashMap	数组+链表+红黑树	非线程安全，效率高	最常用
LinkedHashMap	哈希表 + 链表	保持插入顺序	LRU 缓存实现
TreeMap	红黑树	Key 有序	范围查询
Hashtable	哈希表 (同步)	线程安全，Key 不能为 null	不推荐，用 ConcurrentHashMap
Queue		队列
PriorityQueue	堆	优先级排序	优先级任务
ArrayDeque	循环数组	高效的栈和队列	推荐替代 Stack/LinkedList

10.1 线程安全集合

• Collections.synchronizedList(...): 包装器，性能一般。
• CopyOnWriteArrayList: 写时复制，适合读多写少。
• ConcurrentHashMap: 分段锁 (JDK 1.7) 或 CAS+synchronized (JDK 1.8)，高性能并发 Map。
• BlockingQueue: 阻塞队列，用于生产者 - 消费者模型 (如 ArrayBlockingQueue, LinkedBlockingQueue)。

---

学习建议

1. 理解原理: 不要只背 API，要理解底层数据结构是如何工作的。
2. 手写实现: 尝试用 Java 手写 ArrayList, LinkedList, HashMap 的简化版。
3. 刷题实践: 在 LeetCode 上针对每种数据结构进行专项练习。
4. 关注边界: 注意空指针、容量溢出、并发修改异常等边界情况。