线性数据结构
学习线性数据结构是理解 JDK 数据结构的第一步。线性数据结构指的是元素之间存在线性关系的数据结构，其中每个元素有且只有一个前驱和后继元素。常见的线性数据结构包括数组、链表、栈和队列。
1. 数组（Array）
数组是最简单的线性数据结构，具有固定的大小，元素在内存中是连续存储的。
JDK中的实现：
java.util.ArrayList：基于数组实现的动态数组。相比于普通数组，它的大小可以自动扩展。java.util.Arrays：提供数组操作的工具类，包含了对数组的排序、查找、填充等常用操作。
关键操作：
- 访问：通过索引可以快速访问元素。
- 插入/删除：在数组中间插入/删除元素可能需要移动大量元素，时间复杂度是O(n)。
- 动态调整：
ArrayList在大小不足时会自动扩展。
import java.util.ArrayList;
import java.util.Arrays;
public class ArrayExample {
public static void main(String[] args) {
// ArrayList示例
ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
System.out.println(list); // 输出: [10, 20]
// Arrays工具类示例
int[] arr = {1, 2, 3, 4};
System.out.println(Arrays.toString(arr)); // 输出: [1, 2, 3, 4]
}
}
2. 链表（Linked List）
链表是一种线性数据结构，其中的元素（节点）通过指针连接。链表中的每个节点包含一个数据部分和一个指向下一个节点的指针。
JDK中的实现：
java.util.LinkedList：实现了双向链表，支持快速的插入和删除操作。
关键操作：
- 访问：访问链表中的元素需要从头开始遍历，时间复杂度是O(n)。
- 插入/删除：插入和删除操作相对简单，只需要调整指针即可，时间复杂度为O(1)（如果知道插入位置）。
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.addFirst(5); // 在开头插入
System.out.println(list); // 输出: [5, 10, 20]
}
}
3. 栈（Stack）
栈是一种先进后出（LIFO，Last In First Out）的数据结构。你可以在栈的顶部推入元素，也可以从栈的顶部弹出元素。
JDK中的实现：
java.util.Stack：栈的传统实现类（虽然它在 JDK 中已经不再推荐使用）。java.utilDeque：接口，ArrayDeque实现了栈的功能，且效率更高。
关键操作：
push()：压栈，将元素推入栈顶。pop()：弹栈，从栈顶移除并返回元素。peek()：查看栈顶元素，但不移除。
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
System.out.println(stack.peek()); // 输出: 20
stack.pop();
System.out.println(stack.peek()); // 输出: 10
}
}
4. 队列（Queue）
队列是一种先进先出（FIFO，First In First Out）的数据结构。元素在队列的尾部进入，在队列的头部移除。
JDK中的实现：
java.util.LinkedList：也可以作为队列使用，使用offer()和poll()来操作队列。java.util.Queue：接口，LinkedList和PriorityQueue都实现了它。
关键操作：
offer()：将元素添加到队列尾部。poll()：移除并返回队列头部的元素。peek()：查看队列头部元素，但不移除。
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(10);
queue.offer(20);
System.out.println(queue.peek()); // 输出: 10
queue.poll();
System.out.println(queue.peek()); // 输出: 20
}
}
总结：
这些线性数据结构在 JDK 中有很好的实现和优化。在学习这些数据结构时，理解它们的基本特性和在 JDK 中的应用非常重要。你可以通过 Java 代码练习这些数据结构的操作，掌握它们的优缺点和适用场景，进一步提升对 JDK 中数据结构的理解。
非线性数据结构
非线性数据结构是与线性数据结构相对的，元素之间的关系不是线性的，而是呈现更复杂的结构。常见的非线性数据结构包括树（Tree）和图（Graph）。在 JDK 中，这些数据结构也有相关的实现。
1. 树（Tree）
树是一种非线性的数据结构，由节点和连接节点的边组成，树的特点是有一个根节点，从根节点出发，每个节点都有零个或多个子节点。
常见的树结构：
- 二叉树：每个节点最多有两个子节点。
- 平衡二叉树（AVL树、红黑树）：保证树的高度平衡，避免出现极端不平衡的情况，保证操作的时间复杂度。
- 堆：特殊的树形结构，通常用于优先队列。
JDK中的实现：
java.util.TreeMap：基于红黑树实现的Map，它保证了键值对的有序性。java.util.TreeSet：基于红黑树实现的集合，提供了有序的元素集合。
关键操作：
- 插入、删除、查找：这些操作的时间复杂度通常为O(log n)，但在最坏情况下可能是O(n)，如不平衡的树。
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<>();
set.add(10);
set.add(5);
set.add(20);
System.out.println(set); // 输出: [5, 10, 20]
}
}
2. 图（Graph）
图是一种由节点（顶点）和边组成的非线性数据结构，边用于表示节点之间的关系。图可以是有向的或无向的，也可以是加权的或非加权的。
JDK中的实现：
JDK 本身没有直接的图结构实现，但是可以通过使用集合（Set、Map）来自定义图的表示方法。
- 邻接表表示法：通过
Map存储每个节点及其相邻节点。 - 邻接矩阵表示法：通过二维数组存储节点之间的边。
图的类型：
- 有向图（Directed Graph）：边有方向，表示从一个节点到另一个节点的有向关系。
- 无向图（Undirected Graph）：边没有方向，表示节点之间的双向关系。
- 加权图（Weighted Graph）：每条边都有权重。
关键操作：
- 查找：可以通过深度优先搜索（DFS）或广度优先搜索（BFS）进行遍历。
- 插入、删除：可以添加或删除节点及其相邻的边。
import java.util.*;
public class GraphExample {
static class Graph {
private Map<Integer, List<Integer>> adjList = new HashMap<>();
public void addEdge(int v1, int v2) {
adjList.computeIfAbsent(v1, k -> new ArrayList<>()).add(v2);
adjList.computeIfAbsent(v2, k -> new ArrayList<>()).add(v1); // 无向图
}
public void printGraph() {
for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
}
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.printGraph();
}
}
输出：
1 -> [2, 3]
2 -> [1, 4]
3 -> [1]
4 -> [2]
3. 堆（Heap）
堆是一种特殊的完全二叉树，满足堆的性质：
- 最大堆（Max-Heap）：每个父节点的值都大于或等于其子节点的值，根节点的值最大。
- 最小堆（Min-Heap）：每个父节点的值都小于或等于其子节点的值，根节点的值最小。
JDK中的实现：
java.util.PriorityQueue：基于堆实现的优先队列，默认实现最小堆（最小值优先）。
关键操作：
- 插入：在堆中插入一个元素，时间复杂度是O(log n)。
- 删除：删除根节点并调整堆，时间复杂度是O(log n)。
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// 默认是最小堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(20);
pq.add(5);
System.out.println(pq.poll()); // 输出: 5 (最小值被移除)
System.out.println(pq); // 输出: [10, 20]
}
}
总结：
非线性数据结构相比于线性数据结构，具有更复杂的结构和更强大的功能。它们适用于需要处理多对多关系、层次结构或优先级等问题的场景。
- 树：适用于表示层次结构，如文件系统、组织结构等。
- 图：适用于表示复杂关系，如社交网络、网络拓扑等。
- 堆：适用于需要快速访问最大或最小元素的场景，如优先队列、图的最短路径算法等。
通过 JDK 提供的类和接口，我们可以高效地使用这些非线性数据结构。