本文档提供了算法问题解决中常用数据结构的全面概述。它涵盖了各种数据结构的基本概念、实现细节和实际应用，作为理解 LeetCode 仓库中算法构建块的参考指南。有关使用这些数据结构的特定算法的信息，请参阅 算法。
数据结构根据数据组织方式可分为两大类
来源： thinkings/basic-data-structure.md7-12
线性数据结构按顺序组织元素，其中每个元素（第一个和最后一个除外）恰好有一个前驱和一个后继。
数组将元素存储在连续的内存位置中，允许按索引进行 O(1) 时间访问。
主要特性
实际应用：React Hooks 内部使用数组来管理组件状态
来源： thinkings/basic-data-structure.md13-68
栈遵循后进先出 (LIFO) 原则，元素只能从顶部添加或移除。
关键操作
应用程序
来源： thinkings/basic-data-structure.md128-178
队列遵循先进先出 (FIFO) 原则，元素在队尾添加，在队头移除。
关键操作
实际应用：HTTP 请求处理 HTTP/1.1 中的“队首阻塞”问题是由于同一 TCP 连接的请求按顺序处理造成的。HTTP/2 通过多路复用解决了这个问题
来源： thinkings/basic-data-structure.md70-127
链表由节点组成，每个节点包含数据和指向下一个节点的引用。
类型
关键操作
实际应用：React Fiber React Fiber 使用基于链表的架构来实现虚拟组件树
来源： thinkings/basic-data-structure.md182-245
非线性数据结构将元素组织成层级或网络结构，允许元素拥有多个前驱和后继。
树是具有根节点和由边连接的子节点的层级结构。
关键术语
重要属性
来源： thinkings/basic-data-structure.md246-276
二叉树是每个节点最多有两个子节点的树，通常称为左子节点和右子节点。
类型
二叉树遍历
实现方法
来源： thinkings/binary-tree-traversal.md1-214 thinkings/basic-data-structure.md277-306
二叉搜索树是满足以下排序属性的二叉树：
关键操作
重要特征：二叉搜索树的中序遍历按排序顺序产生元素（1, 3, 4, 6, 7, 8, 10, 14）。
来源： thinkings/basic-data-structure.md330-355
平衡二叉树是 BST，旨在保持对数高度，确保操作性能为 O(log n)。
类型
重新平衡操作
来源： thinkings/basic-data-structure.md356-382
堆是基于树的专用数据结构，它满足堆属性
关键操作
二叉堆通常实现为数组，其中索引 i 处的节点
应用程序
来源： thinkings/basic-data-structure.md307-329
Trie（发音同 "try"）是一种优化的树状数据结构，用于字符串操作，特别是前缀搜索。
关键操作
实现
应用程序
来源： thinkings/trie.md1-296 problems/208.implement-trie-prefix-tree.md1-196
图由顶点（节点）和连接它们的边组成，表示对象之间的关系。
类型
图的表示
图的遍历
常用图算法
| 数据结构 | 访问 | 搜索 | 插入 | 删除 | Space键 |
|---|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| 栈 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 队列 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 二叉搜索树（平衡） | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| 二叉搜索树（不平衡） | O(n) | O(n) | O(n) | O(n) | O(n) |
| 堆 | O(1)** | O(n) | O(log n) | O(log n) | O(n) |
| Trie树 | O(m) | O(m) | O(m) | O(m) | O(n×m) |
| 图（邻接表） | O(n) | O(n) | O(1) | O(n+e) | O(n+e) |
| 图（邻接矩阵） | O(1) | O(1) | O(1) | O(1) | O(n²) |
*引用节点 **仅用于获取最小值/最大值 n：元素数量，m：键长，e：边数
来源：合并多个文件
选择正确的数据结构取决于所需的操作及其频率。
来源：合并多个文件
| 数据结构 | 应用程序 |
|---|---|
| 数组 | 存储和访问顺序数据、矩阵运算、动态规划 |
| 栈 | 函数调用管理、表达式求值、撤销机制、浏览器历史记录 |
| 队列 | 任务调度、CPU 调度、打印机队列、HTTP 请求处理 |
| 链表 | React Fiber 实现、音乐播放列表、Web 浏览器缓存、撤销功能 |
| 树 | 文件系统、组织层级、HTML DOM、数据库索引 |
| BST | 数据库索引、关联数组实现、数据优先级排序 |
| 堆 | 优先队列、调度算法、堆排序、图算法 |
| Trie 树 | 自动补全系统、拼写检查器、IP 路由、搜索引擎建议 |
| 图 | 社交网络、地图和导航、依赖项解析、网络路由 |
来源：合并多个文件
此仓库实现了 LeetCode 问题中常用的各种数据结构操作
通过理解这些基本的数据结构及其操作，您将能够有效地解决各种算法问题。