数据结构是数据组织、存储和管理的方式，也就是把数据聚合在一起，以便进行加工整理。不同的数据结构会决定数据的访问、操作和处理的效率。
-
数据结构 数据结构主要分为以下两大类：
- 线性结构：数据元素按顺序排列，元素之间存在一对一的关系。例如数组、链表、栈、队列等。
- 非线性结构：数据元素之间没有固定的顺序关系，元素之间可能是一对多或多对多的关系。例如树、图等。
-
数据类型与数据结构
- 数据类型是对数据的一种分类，例如整型、字节、浮点、字符、和布尔等。不同的数据类型具有不同的取值范围和操作方式。
- 数据类型是数据结构的基础，数据结构将多个数据按类型和规则组织起来，提供更高效的操作方式。
- 数组（Array），聚合数据的集合，可以实现线性和非线性。
- 链表（Linked List），线性结构，数据以链式结构存储。
- 栈（Stack），线性结构，后进先出。
- 队列（Queue），线性结构，先进先出。
- 树（Tree），非线性结构，模拟树状结构性质的数据集合，一个顶点。
- 堆（Heap），非线性结构，特殊的树形数据结构，一般指完全二叉树。
- 图（Graph），非线性结构，节点相互连接，每个节点都可以作为顶点。
- 散列（Hash），线性结构，根据键访问储存位置的数据结构。
| 数据结构 | 类型 | 结构特点 | 存储方式 | 主要操作 | 时间复杂度（平均） | 优点 | 缺点 | 应用场景 |
|---|---|---|---|---|---|---|---|---|
| 数组 | 线性 | 聚合数据的集合，可实现线性和非线性 | 连续内存块 | 插入、查找、删除 | 查找：O(1) 插入/删除：O(n) | 快速访问，通过索引可以直接访问元素 | 插入删除时需要移动元素 | 常用于存储已知大小和不频繁修改的元素 |
| 链表 | 线性 | 数据以链式结构存储，每个元素包含指向下一个元素的指针 | 由节点组成，每个节点包含数据和指针 | 插入、删除 | 查找：O(n) 插入/删除：O(1) | 动态内存分配，不需要预留空间 | 查找操作慢，不适合随机访问 | 实现队列、栈，动态数据存储等 |
| 栈 | 线性 | 后进先出（LIFO） | 通过链表或数组实现 | 入栈、出栈 | 入栈/出栈：O(1) | 直观、简单，适合递归问题的解决 | 限制较多，仅适用于LIFO场景 | 递归调用、函数调用栈、撤销操作等 |
| 队列 | 线性 | 先进先出（FIFO） | 通过链表或数组实现 | 入队、出队 | 入队/出队：O(1) | 高效的先进先出操作 | 仅支持FIFO，功能较单一 | 任务调度、进程管理、缓存等 |
| 树 | 非线性 | 层级结构，每个节点有一个父节点和多个子节点 | 节点通过指针链接，每个节点有多个子节点 | 查找、插入、删除 | 查找、插入、删除：O(log n) | 适合分层存储和检索 | 复杂度较高，不适用于所有场景 | 文件系统、数据库索引、表达式树等 |
| 堆 | 非线性 | 特殊的树形结构，一般为完全二叉树，最大堆或最小堆 | 完全二叉树 | 插入、删除最大/最小元素 | 插入/删除：O(log n) | 高效的优先级操作，适用于排序和队列 | 查找、更新任意元素不方便 | 优先级队列、堆排序、图算法等 |
| 图 | 非线性 | 节点相互连接，每个节点都可以作为顶点 | 节点与边通过指针或数组存储 | 查找、遍历 | 查找/遍历：O(V + E) | 灵活建模，表示复杂关系 | 复杂度较高，尤其是图较大时 | 社交网络、交通网络、搜索引擎等 |
| 散列 | 线性 | 根据键访问存储位置的数据结构 | 数组结合哈希函数映射 | 插入、查找、删除 | 查找：O(1) 插入/删除：O(1) | 高效的查找，插入和删除操作 | 可能出现哈希冲突，性能下降 | 数据库索引、缓存、字典等 |
| 列表 | 线性 | 顺序存储数据，可以包含重复元素 | 顺序集合，如链表或数组 | 插入、删除、查找 | 查找：O(n) 插入/删除：O(1) | 灵活、支持重复元素，适合遍历 | 查找不够高效，内存开销较大 | 数据存储、任务调度、操作日志等 |
| 结构体 | 线性 | 组合多种数据类型的集合，适合存储不定量的数据 | 通过连续存储位置组合不同数据类型 | 访问字段、修改字段 | 访问字段：O(1) | 灵活组合多种数据类型，支持多样化 | 存储开销较大，字段固定不灵活 | 记录数据、定义对象、组织信息等 |
1. 数组（Array）
数组是相同类型数据元素的有序集合，每个元素通过索引访问。数组在内存中是连续存储的，因此访问速度非常快，但插入和删除操作的效率较低。
应用场景：
- 存储一组固定大小的数据。
- 需要快速随机访问元素的场景。
特点：
- 内存连续，访问速度快。
- 大小固定，插入和删除效率低。
链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表在内存中是非连续存储的，因此可以动态添加或删除元素。
应用场景：
- 需要频繁插入和删除的场景。
- 实现栈、队列等数据结构。
特点：
- 内存非连续，插入和删除效率高。
- 随机访问效率低。
3. 栈（Stack）
栈是一种遵循 后进先出（LIFO） 原则的数据结构。元素只能在栈顶插入（压栈）或删除（弹栈）。
应用场景：
- 函数调用栈。
- 表达式求值（如括号匹配）。
- 递归算法。
特点：
- 操作受限，只能在栈顶进行插入和删除。
- 简单高效。
4. 队列（Queue）
队列是一种遵循 先进先出（FIFO） 原则的数据结构。元素从队尾添加（入队），从队头删除（出队）。
应用场景：
- 任务调度。
- 消息队列。
- 广度优先搜索（BFS）。
特点：
- 操作受限，只能在队尾添加，队头删除。
- 适用于排队场景。
5. 树（Tree）
树是一种层次化的数据结构，由一个根节点和若干个子节点组成。每个子节点可能有自己的子节点，形成树状结构。
应用场景：
- 文件系统。
- 数据库索引（如B树、B+树）。
- 组织数据（如家谱、组织结构）。
特点：
- 非线性结构，适合表示层次关系。
- 常见的树结构包括二叉树、平衡树、红黑树等。
6. 堆（Heap）
堆是一种特殊的树形数据结构，通常是一个完全二叉树。堆分为最小堆和最大堆，最小堆的每个节点的值都小于或等于其子节点的值，最大堆则相反。
应用场景：
- 优先队列。
- 堆排序。
- 算法优化（如Dijkstra算法）。
特点：
- 快速查找最大或最小元素。
- 插入和删除操作的时间复杂度为O(log n)。
7. 图（Graph）
图由节点（顶点）和边组成，表示对象之间的关系。节点可以代表实体，边可以代表实体之间的关联。
应用场景：
- 社交网络。
- 网络拓扑。
- 路径搜索（如最短路径问题）。
特点：
- 非线性结构，适合表示复杂关系。
- 常见的图算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。
8. 散列（Hash）
散列是一种通过哈希函数将数据映射到哈希值的技术，以便快速
一种树形数据结构，每个节点最多有两个子节点，包括普通二叉树、满二叉树、完全二叉树和平衡二叉树等。
应用：广泛应用于算法、数据结构、搜索和排序等领域。二叉搜索树适用于快速查找、添加和删除操作。
一种不允许重复元素的数据结构。主要用于集合操作，如添加、删除、查询等。
应用：集合适用于没有重复数据的场景，提供集合运算，如并集、交集和差集等。
存储键-值对，并允许通过键快速查找对应的值。键必须唯一，但值可以重复。
应用：映射用于高效的数据检索、数据关联以及数据结构之间的关联。如缓存实现、数据库索引、负载均衡等。
一种高效的数据结构，使用哈希函数将键映射到对应的值。提供快速的查找、插入和删除操作。
应用：哈希表用于快速查找、插入和删除数据的场景，例如字典、映射、缓存等。
- HashMap：一种哈希表实现，不是线程安全的，适用于单线程或自行管理同步的场景。
- HashTable：一种线程安全的哈希表，适用于多线程环境，但由于同步机制，性能可能较低。
优先队列是一种特殊的队列，元素的顺序根据优先级排列，而非插入顺序。
应用：优先队列常用于实现任务调度、事件驱动、路径搜索等场景。
一种数据结构，用于组合一组相关的数据，以便将它们作为一个整体来处理。结构体在许多编程语言中都有支持，struct与class有点类似，struct见于C、C++、Go、Rust等语言。class用于Java和C#、JS、Python、PHP等。
应用： 用于创建具有特定属性的复杂数据类型，封装相关数据，还可用于数据包或消息的结构以及定义内存中的数据存储结构。