📌 目录
- 什么是数据结构？
- Java 中的数据结构分类
- 数组（Array）
- 链表（Linked List）
- 栈（Stack）
- 队列（Queue）
- 哈希表（Hash Table）
- 树（Tree）
- 图（Graph）
- 优先队列（Priority Queue）
- 参考资料
- 出站链接
1. 什么是数据结构？
数据结构 是计算机中存储、组织数据的方式。通过合理的数据结构，可以提高程序的效率和性能。数据结构分为线性结构（如数组、链表）和非线性结构（如树、图）。数据结构的选择直接影响程序的执行效率和内存占用。
在 Java 中，数据结构通常由不同的类和接口表示，Java 的集合框架（Java Collections Framework）提供了大量的实现，帮助开发者高效地存储和操作数据。
2. Java 中的数据结构分类
Java 中常见的数据结构主要包括以下几类：
- 线性结构：
- 数组（Array）
- 链表（Linked List）
- 栈（Stack）
- 队列（Queue）
- 非线性结构：
- 树（Tree）
- 图（Graph）
- 哈希表（Hash Table）
- 特殊数据结构：
- 优先队列（Priority Queue）
3. 数组（Array）
数组 是一种线性数据结构，用来存储固定大小的同类型元素集合。在 Java 中，数组是对象，因此数组的大小是固定的，不能动态调整。
数组的特点：
- 访问时间快：通过索引可以直接访问数组中的元素，时间复杂度为 O(1)。
- 大小固定：数组一旦创建，大小就不能更改。
- 存储连续内存位置：数组元素在内存中是连续存储的。
示例代码：
public class ArrayExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println("First element: " + arr[0]);
System.out.println("Array length: " + arr.length);
}
}
4. 链表（Linked List）
链表 是由一系列节点（Node）组成的数据结构，每个节点包含数据部分和指向下一个节点的指针（或引用）。链表不需要在内存中存储连续的元素，它是动态的，可以在运行时插入和删除节点。
链表的类型：
- 单向链表：每个节点只指向下一个节点。
- 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
- 循环链表：最后一个节点的指针指向头节点，形成一个循环。
示例代码：
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public class LinkedListExample {
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
// Traverse the linked list
Node current = head;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
}
5. 栈（Stack）
栈 是一种后进先出（LIFO，Last In First Out）的数据结构。栈支持的主要操作包括：
- push：将元素压入栈中。
- pop：弹出栈顶元素。
- peek：查看栈顶元素，但不弹出它。
示例代码：
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Top element: " + stack.peek()); // 查看栈顶元素
stack.pop(); // 弹出栈顶元素
System.out.println("Top element after pop: " + stack.peek());
}
}
6. 队列（Queue）
队列 是一种先进先出（FIFO，First In First Out）的数据结构。队列支持的主要操作包括：
- enqueue：将元素添加到队列的尾部。
- dequeue：从队列的头部移除元素。
- peek：查看队列头部的元素。
Java 中提供了多种队列的实现，如 LinkedList 和 PriorityQueue。
示例代码：
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println("Front element: " + queue.peek());
queue.poll(); // 移除队列头部元素
System.out.println("Front element after poll: " + queue.peek());
}
}
7. 哈希表（Hash Table）
哈希表 是一种通过哈希函数将数据映射到数组索引的数据结构。哈希表支持快速的查找、插入和删除操作，时间复杂度为 O(1)，但当发生哈希冲突时，性能可能下降。
哈希表的实现：
- Java 中的 HashMap 和 Hashtable 是哈希表的常见实现，HashMap 不同步，性能更好，而 Hashtable 是同步的。
示例代码：
import java.util.HashMap;
public class HashTableExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
System.out.println("Value for key 'one': " + map.get("one"));
}
}
8. 树（Tree）
树 是一种非线性数据结构，由一组节点组成，节点之间通过边连接。树的一个常见例子是 二叉树，每个节点最多有两个子节点（左子节点和右子节点）。
树的特点：
- 根节点：树的起始节点。
- 叶节点：没有子节点的节点。
- 高度：树的深度。
- 深度优先遍历和广度优先遍历是常见的树遍历方法。
示例代码：
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeExample {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
System.out.println("Root value: " + root.val);
}
}
9. 图（Graph）
图 是由节点（或顶点）和边组成的数据结构。图可以是有向的或无向的，边可以带权重。图广泛用于表示网络结构、社交网络、计算机网络等。
图的表示方式：
- 邻接矩阵：用二维数组表示图的顶点间的连接关系。
- 邻接列表：用链表表示每个顶点相邻的顶点。
10. 优先队列（Priority Queue）
优先队列 是一种队列，其中每个元素都关联一个优先级，具有较高优先级的元素会优先出队。Java 提供了 PriorityQueue 类来实现优先队列。
示例代码：
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(2);
pq.add(8);
System.out.println("PriorityQueue front: " + pq.peek()); // 获取优先队列的最小元素
pq.poll(); // 移除最小元素
System.out.println("After poll, front: " + pq.peek());
}
}
发表回复