【数据结构】数据结构总结（持续更新）
数据结构是计算机科学中的核心概念之一，是优化算法性能和资源利用率的关键。在软件开发和数据处理中，选择合适的数据结构对于算法的效率至关重要。数据结构的选择通常基于数据的使用模式，包括数据元素之间的关系、数据的存储方式、以及对数据的操作类型（如检索、更新、排序等）。常用的数据结构有：数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、图（Graph
目录
概述
数据结构是计算机科学中的核心概念之一，是优化算法性能和资源利用率的关键。在软件开发和数据处理中，选择合适的数据结构对于算法的效率至关重要。数据结构的选择通常基于数据的使用模式，包括数据元素之间的关系、数据的存储方式、以及对数据的操作类型（如检索、更新、排序等）。
常用的数据结构有：数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、图（Graph）、堆（Heap）、散列表（Hash）等等。
数据结构分类
数据结构可以根据其特性和用途被分为多种类型。
排列方式
集合（Set）
元素之间除了“同属一个集合” 的相互关系外，别无其他关系
集合是一种抽象数据类型，它可以用来存储一组独特的项，即不允许重复的元素。在集合中，元素的存储顺序通常不重要，也不保证任何特定的顺序。集合的主要操作包括添加元素、删除元素、检查元素是否存在、遍历元素、求并集、交集和差集等。
线性结构（Linear Structure）
元素存在一对一的相互关系。
线性结构是一种数据结构，其中的元素形成一个序列，并且每个元素都有唯一的前驱和后继（除了第一个和最后一个元素）。常见的线性结构包括数组、链表、栈和队列。
树形结构（Tree Structure）
元素存在一对多的相互关系
树形结构是一种分层的数据结构，由节点组成，每个节点有零个或多个子节点，但只有一个父节点（除了根节点，它没有父节点）。在树形结构中，元素之间存在一对多的层次关系。
图形结构（Graph Structure）
元素存在多对多的相互关系
图形结构是一种复杂的数据结构，由节点（也称为顶点）和连接这些节点的边组成。在图形结构中，任意两个节点之间都可能存在关系，即边，这些关系可以是单向的也可以是双向的。
逻辑结构
线性数据结构
线性数据结构中的元素形成一个序列。有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。
主要的线性数据结构包括：
1.数组（Array）
定义：在内存中连续存储的元素集合，可以通过索引直接访问任何元素。
特点：固定大小，高效的随机访问。
2.栈（Stack）
定义：遵循后进先出（LIFO）原则的集合。
特点：只能在一端（通常称为栈顶）进行添加或删除操作。
3.队列（Queue）
定义：遵循先进先出（FIFO）原则的集合。
特点：在队尾添加元素，在队首移除元素。
4.链表（LinkedList）
定义：由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。
特点：动态大小，高效的插入和删除操作。
5.双端队列（Deque）
定义：一种具有队列和栈性质的数据结构。
特点：两端都可以进行插入和删除操作。
非线性数据结构
非线性数据结构中的元素不是简单的顺序排列，而是按照更复杂的关系组织。对应于线性结构，非线性结构也就是每个结点可以有不止一个直接前驱和直接后继。
主要的非线性数据结构包括：
1.树（Tree）
定义：由节点组成的分层数据结构，有一个根节点，并且每个节点可以有多个子节点。
特点：反映层次关系，常用于表示继承结构。
2.图（Graph）
定义：由节点（或称顶点）和连接这些节点的边组成。
特点：可以用来表示网络结构，边可以是有向的也可以是无向的，可以有权重。
3.堆（Heap）
定义：可以迅速找到最大值或最小值的数据结构。
特点：通常用数组实现，满足特定的堆属性。
原始和复合数据结构
数据结构也可以根据它们的复杂性分为原始（Primitive）和复合（NonPrimitive）数据结构：
1.原始数据结构
定义：基本的数据类型，如整数（int）、字符（char）、浮点数（float）、布尔值（boolean）等。
特点：通常由编程语言直接支持，是构建更复杂数据结构的基础。
2.复合数据结构
定义：由原始数据类型或其他复合类型组合而成的数据结构。
特点：可以是线性的也可以是非线性的，更加复杂，如类（Class）、数组、链表、树等。
特殊类型的数据结构
除了上述分类，还有一些特殊类型的数据结构，它们是为了解决特定问题而设计的：
1.散列表（HashTable）
定义：使用哈希函数将键（Key）映射到表中一个位置来访问记录的数据结构，以支持快速的插入、删除和查找操作。
特点：通过键直接访问内存存储位置，平均情况下能够提供接近常数时间的性能。
2.优先队列（PriorityQueue）
定义：元素带有优先级的队列，元素的出队顺序是根据它们的优先级而定的，而不是它们的入队顺序。
特点：通常用堆来实现，可以迅速访问到优先级最高的元素。
3.图（Graph）的变体
有向图（DirectedGraph）：边有方向。
无向图（UndirectedGraph）：边没有方向。
加权图（WeightedGraph）：边赋予了权重，表示从一个顶点到另一个顶点的成本。
连通图（ConnectedGraph）：任意两个顶点间都存在路径。
非连通图（DisconnectedGraph）：存在至少一对顶点，它们之间没有路径。
完全图（CompleteGraph）：每对顶点之间都有一条边。
4.树（Tree）的变体
二叉树（BinaryTree）：每个节点最多有两个子节点。
二叉搜索树（BinarySearchTree,BST）：左子树的所有元素小于根节点，右子树的所有元素大于根节点。
平衡二叉树（例如AVL树）：任何节点的两个子树的高度差最大为一，确保树的平衡。
B树和B+树：多路搜索树，通常用于数据库和文件系统。
5.集合（Set）
定义：一组无序的、互不相同的元素集合。
特点：主要操作包括添加元素、删除元素和检查元素是否存在。
6.字典（Dictionary）
定义：存储键值对的数据结构，每个键映射到一个值。
特点：与散列表类似，但通常更强调查找操作。
7.图的特殊类型
最小生成树（MinimumSpanningTree）：一个无向图的生成树，包含所有顶点且边的总权重最小。
有向无环图（DirectedAcyclicGraph,DAG）：一个有向图，没有任何循环。
8.线性表（LinearList）
定义：线性顺序排列的元素集合，可以是数组或链表的形式。
特点：元素之间有序排列，可以通过位置索引访问。
9.多维数组（MultidimensionalArray）
定义：由数组的数组构成，可以是二维数组、三维数组等。
特点：用于表示多维空间中的数据。
各种数据结构
| 分类 | 数组 | 链表 | 栈 | 队列 | 树 | 堆 | 散列表 | 图 |
|---|---|---|---|---|---|---|---|---|
| 特点 | 固定大小，连续内存空间 | 动态大小，非连续内存空间 | LIFO（后进先出） | FIFO（先进先出） | 分层结构 | 完全二叉树，具有顺序性 | 键值对映射，快速查找 | 节点加边，可表示网络关系 |
| 优点 | 访问速度快，O(1)查找元素 | 动态扩容，插入删除快 | 简单易实现，插入删除快 | 简单易实现，插入删除快 | 分层次清晰，查找效率高 | 插入删除快，可快速找到最大/最小值 | 平均情况下快速查找、插入和删除 | 表示复杂关系，灵活 |
| 缺点 | 大小固定，扩容代价大 | 访问速度慢，O(n)查找元素 | 只能访问栈顶元素 | 只能从两端进行操作 | 存储空间大，操作复杂 | 查找任意元素慢 | 最坏情况下性能差，需要良好的哈希函数 | 存储空间可能大，操作复杂 |
| 使用场景 | 需要快速访问元素，大小固定时使用 | 数据量变化大，插入删除频繁时使用 | 撤销操作，后退功能 | 排队系统，任务调度 | 层级关系，如文件系统 | 优先队列，任务调度 | 需要快速查找记录，如数据库 | 网络分析，如社交网络 |
数组（Array）
概念：
数组是一种基本的数据结构，它存储一系列固定大小的元素，这些元素在内存中连续排列。每个元素可以通过一个整数下标快速访问。
int[] arr = new int[5]; // 声明一个整型数组，大小为5
arr[0] = 5; // 初始化数组第一个元素
arr[1] = 10; // 初始化数组第二个元素
// ...以此类推特点：
随机访问：可以通过下标在常数时间内访问任何元素。
固定大小：一旦声明，大小不可改变。
优缺点：
优点：快速访问元素；适合于已知固定大小的数据存储。
缺点：大小固定，不灵活；插入和删除操作效率低，因为这些操作需要移动元素以保持元素连续,由于数组为每个元素都分配了索引且索引是自增连续的，因此一但删除或者新增了某个元素时需要调整后面的所有元素的索引。
使用场景：
适用于元素数量固定，频繁访问元素的场景，如存储像素值的图像处理。
总结：
数组查询快，增删慢，适用于频繁查询，增删较少的情况。
举例：
存储一周内每天的温度值。
public class TemperatureArray {
private static final int DAYS_OF_WEEK = 7;
private double[] temperatures = new double[DAYS_OF_WEEK]; // 假设一周7天
public void setTemperature(int day, double temp) {
if (day < 0 || day >= DAYS_OF_WEEK) {
throw new IllegalArgumentException("Invalid day of the week.");
}
temperatures[day] = temp; // O(1) 时间复杂度
}
public double getTemperature(int day) {
if (day < 0 || day >= DAYS_OF_WEEK) {
throw new IllegalArgumentException("Invalid day of the week.");
}
return temperatures[day]; // O(1) 时间复杂度
}
}
相关编程
链表（LinkedList）
概念：
链表是由一系列节点Node（也可称元素）组成，数据元素的逻辑顺序是通过链表的指针地址实现，通常情况下，每个节点包含两个部分，一个用于存储元素的内存地址，名叫数据域，另一个则指向下一个相邻节点地址的指针，名叫指针域；根据链表的指向不同可分为单向链表、双向链表、循环链表等。
链表节点
完整链表
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
Node head = new Node(1); // 创建链表的头节点
head.next = new Node(2); // 创建第二个节点并连接
head.next.next = new Node(3); // 创建第三个节点并连接特点：
动态大小：可以在运行时动态添加或删除节点。
非连续存储：节点在内存中可以分散存储。
优缺点：
优点：插入和删除操作快速，只需改变指针。
缺点：访问元素需要从头部开始遍历，访问时间长；相比数组，每个元素需要额外的空间存储指针。
使用场景：
适合元素数量不固定，频繁插入和删除的场景，如实现高效的队列和栈。
总结:
数据量较小，需要频繁增加，删除操作的场景，查询操作相对较少。
举例：
浏览器的前进和后退功能。
public class BrowserHistory {
private class Node {
String url;
Node prev, next;
public Node(String url) {
this.url = url;
}
}
private Node current;
public void visit(String url) {
Node newNode = new Node(url);
if (current != null) {
current.next = newNode;
newNode.prev = current;
}
current = newNode; // O(1) 时间复杂度
}
public String back() {
if (current == null || current.prev == null) return null;
current = current.prev; // O(1) 时间复杂度
return current.url;
}
public String forward() {
if (current == null || current.next == null) return null;
current = current.next; // O(1) 时间复杂度
return current.url;
}
}
相关编程
栈（Stack）
概念：
栈是一种后进先出（LIFO）的数据结构，添加（推入）和删除（弹出）元素都发生在同一端，称为栈顶。
是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出从栈顶放入元素的操作叫入栈（压栈），取出元素叫出栈（弹栈）
入栈操作
出栈操作
import java.util.Stack;
Stack<Integer> stack = new Stack<>();
stack.push(1); // 推入元素
stack.push(2);
stack.push(3);
int topElement = stack.pop(); // 弹出元素，此时为3特点：
后进先出：最后添加的元素最先被移除。
一端操作：所有操作都在栈顶进行。
优缺点：
优点：操作简单，入栈和出栈操作快速。
缺点：不适合需要随机访问的场景。
使用场景：
适用于实现撤销操作、函数调用的记录等。
举例：
编辑器的撤销功能。
import java.util.Stack;
public class Editor {
private Stack<String> history = new Stack<>();
public void write(String text) {
history.push(text); // O(1) 时间复杂度
}
public String undo() {
return history.isEmpty() ? null : history.pop(); // O(1) 时间复杂度
}
}
相关编程
队列（Queue）
概念：队列是一种先进先出（FIFO）的数据结构，元素在队列的一端添加，在另一端移除。
队列与栈一样，也是一种线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。队列的特点是先进先出，从一端放入元素的操作称为入队，取出元素为出队。
import java.util.LinkedList;
import java.util.Queue;
Queue<Integer> queue = new LinkedList<>();
queue.add(1); // 入队
queue.add(2);
queue.add(3);
int headElement = queue.remove(); // 出队，此时为1特点：
先进先出：最先添加的元素最先被移除。
两端操作：一端用于添加元素，另一端用于移除元素。
优缺点：
优点：操作直观，适合处理按顺序到达的数据。
缺点：同栈一样，不适合随机访问。
使用场景：
适用于需要按顺序处理元素的场景，如打印任务管理。
举例：
银行或超市的排队系统。
import java.util.LinkedList;
import java.util.Queue;
public class CustomerQueue {
private Queue<String> queue = new LinkedList<>();
public void enqueue(String customer) {
queue.add(customer); // O(1) 时间复杂度
}
public String dequeue() {
return queue.isEmpty() ? null : queue.remove(); // O(1) 时间复杂度
}
}
相关编程
树（Tree）
概念：
树是一种分层的数据结构，由节点组成，每个节点有零个或多个子节点，但最多只有一个父节点，根节点没有父节点。
是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
1）每个节点有0个或多个子节点；
2）没有父节点的节点称为根节点；
3）每一个非根节点有且只有一个父节点；
4）除了根节点外，每个子节点可以分为多个不相交的子树；
5）右子树永远比左子树大，读取顺序从左到右；
树的分类有非常多种，平衡二叉树（AVL）、红黑树RBL（R-B Tree）、B树（B-Tree）、B+树（B+Tree）等，但最早都是由二叉树演变过去的；
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int item) {
data = item;
left = right = null;
}
}
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);特点：
分层结构：树形结构清晰地表示了数据的层次关系。
非线性：树结构中的元素可以有多个子元素。
优缺点：
优点：反映层次关系，非线性结构便于表示实际问题。
缺点：操作比线性数据结构复杂。
使用场景：
适用于需要表示层次关系的场景，如文件系统的目录结构。
举例：
组织机构图。
public class OrganizationTree {
private class Node {
String position;
List<Node> subordinates;
public Node(String position) {
this.position = position;
this.subordinates = new ArrayList<>();
}
}
private Node root;
public void addSubordinate(String superior, String subordinate) {
// 递归查找上级位置并添加下级
}
private Node findPosition(Node root, String position) {
// 递归搜索特定职位
}
}
每种数据结构都有其特定的用途和操作，选择正确的数据结构可以提高程序的效率和性能。在Java中，许多数据结构已经以库的形式实现，如`java.util.Stack`、`java.util.Queue`、`java.util.HashMap`等，可以直接使用。
图（Graph）
概念：
图是一种由节点（顶点）和连接这些节点的边组成的数据结构，顶点可以通过边相互连接。
图是一系列顶点（元素）的集合，这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
图分为有向图和无向图：
- 有向图：边不仅连接两个顶点，并且具有方向；
- 无向图：边仅仅连接两个顶点，没有其他含义；
import java.util.*;
class Graph {
private Map<Integer, List<Integer>> adjList;
public Graph(int vertices) {
adjList = new HashMap<>();
for (int i = 0; i < vertices; i++) {
adjList.put(i, new LinkedList<>());
}
}
public void addEdge(int src, int dest) {
adjList.get(src).add(dest);
adjList.get(dest).add(src); // 对于无向图
}
}
Graph graph = new Graph(3);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);特点：
顶点和边：图由顶点集合和边集合组成。
有向与无向：图的边可以是有方向的也可以是无方向的。
优缺点：
优点：能够表示复杂的关系，如网络。
缺点：算法通常比线性数据结构更复杂，存储空间可能更大。
使用场景：
适用于表示复杂关系的场景，如社交网络分析。
举例：
交通流量模拟。
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class TrafficGraph {
private class Node {
String intersection;
Set<Node> adjacent = new HashSet<>();
public Node(String intersection) {
this.intersection = intersection;
}
}
private Map<String, Node> graph = new HashMap<>();
public void addRoad(String from, String to) {
Node fromNode = graph.computeIfAbsent(from, Node::new);
Node toNode = graph.computeIfAbsent(to, Node::new);
fromNode.adjacent.add(toNode); // O(1) 时间复杂度
toNode.adjacent.add(fromNode); // O(1) 时间复杂度
}
// ... 进一步实现图的搜索和分析算法 ...
}
堆（Heap）
概念：
堆是一种特殊的完全二叉树，所有的节点都满足堆属性，即父节点的键值总是不大于或不小于其子节点的键值。
可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
import java.util.PriorityQueue;
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 最小堆
minHeap.add(3);
minHeap.add(1);
minHeap.add(2);
int minElement = minHeap.poll(); // 移除并返回最小元素，此时为1特点：
完全二叉树：堆是一种特殊的完全二叉树。
堆属性：最大堆中父节点的值大于子节点，最小堆则相反。
优缺点：
优点：快速找到最大或最小元素。
缺点：不支持快速的按序遍历。
使用场景：
适用于需要快速访问最大或最小元素的场景，如优先队列。
举例：
任务调度中的任务优先级队列。
import java.util.PriorityQueue;
public class TaskScheduler {
private PriorityQueue<Task> taskQueue = new PriorityQueue<>((task1, task2) -> task2.priority - task1.priority);
private class Task {
int priority;
String job;
public Task(int priority, String job) {
this.priority = priority;
this.job = job;
}
}
public void scheduleTask(int priority, String job) {
taskQueue.add(new Task(priority, job)); // O(log n) 时间复杂度
}
public Task getNextTask() {
return taskQueue.poll(); // O(log n) 时间复杂度
}
}
哈希表（HashMap）
哈希表是根据键（Key）直接访问内存存储位置的数据结构。它通过计算一个关于键的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
import java.util.HashMap;
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1); // 添加键值对
map.put("banana", 2);
int value = map.get("apple"); // 根据键获取值，此时为1散列表 (HashTable)
概念：
散列表是一种通过哈希函数将键映射到一个索引上，以实现快速查找的数据结构。
也叫哈希表，是根据键和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性，所以散列表其实是数组的一种扩展，由数组演化而来。
特点：
快速查找：通过哈希函数可以快速定位元素位置。
键值映射：每个值都有一个唯一的键与之对应。
优缺点：
优点：平均情况下查找、插入和删除的时间复杂度接近O(1)。
缺点：哈希冲突解决不当会影响性能；顺序遍历困难。
使用场景：
适用于需要快速查找、插入和删除的场景，如数据库索引。
举例：
用户名和用户信息的映射。
import java.util.HashMap;
import java.util.Map;
public class UserDirectory {
private Map<String, String> directory = new HashMap<>();
public void addUser(String username, String info) {
directory.put(username, info); // 平均 O(1) 时间复杂度
}
public String getUserInfo(String username) {
return directory.get(username); // 平均 O(1) 时间复杂度
}
}
参考: 数据结构：八种数据结构大全
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
22
0- 0
已为社区贡献15条内容
所有评论(0)