导入
线性与非线性数据结构概述
在本节课中，你将回顾所学所有数据结构的时间复杂度，并将它们分类为线性数据结构和非线性数据结构。
现在你已经学习了所有常见的数据结构，让我们来看看哪些是线性数据结构，哪些是非线性数据结构。了解这一点有助于你在设计算法时选择合适的数据结构。
线性数据结构
在线性数据结构中，每个元素最多与一个（下一个元素）或两个（前一个和下一个）其他元素相连。遍历这些结构时是线性的，因此插入、删除和查找操作的时间复杂度为 O(n)。
数组、链表、栈 和 队列 都是线性数据结构的例子。
非线性数据结构
非线性数据结构与线性数据结构正好相反。在非线性数据结构中，每个元素可以连接到多个其他元素。遍历不是线性的，因此查找、插入和删除操作的时间复杂度可以达到 O(log n)，甚至 O(1)。
树、图 和 哈希表 都是非线性数据结构的例子。
时间与空间复杂度速查表
以下是本课程所学数据结构的复杂度快速回顾表，帮助你在不同场景下比较它们的性能表现。
注意： 表中的 n 表示结构中存储的总元素数量。
| 数据结构 | 插入（平均/最坏） | 删除（平均/最坏） | 查找（平均/最坏） | 空间复杂度（最坏） |
|---|---|---|---|---|
| 数组 | O(n) | O(n) | O(n) | O(n) |
| 单向链表 | O(1) | O(n) | O(n) | O(n) |
| 双向链表 | O(1) | O(n) | O(n) | O(n) |
| 栈 | O(1) | O(1) | O(n) | O(n) |
| 队列 | O(1) | O(1) | O(n) | O(n) |
| 二叉堆 | O(log n) | O(log n)（removeMax() 或 removeMin()） | O(n) | O(n) |
| 二叉树 | O(n) | O(n) | O(n) | O(n) |
| 二叉搜索树 | O(log n) / O(n) | O(log n) / O(n) | O(log n) / O(n) | O(n) |
| 红黑树 | O(log n) | O(log n) | O(log n) | O(n) |
| AVL 树 | O(log n) | O(log n) | O(log n) | O(n) |
| 2-3 树 | O(log n) | O(log n) | O(log n) | O(n) |
| 哈希表 | O(1) / O(n) | O(1) / O(n) | O(1) / O(n) | O(n) |
| 字典树（Trie） | O(n) | O(n) | O(n) | O(n) |
图数据结构的复杂度
| 操作 | 邻接表 | 邻接矩阵 |
|---|---|---|
| 添加顶点 | O(1) | O(V²) |
| 删除顶点 | O(V + E) | O(V²) |
| 添加边 | O(1) | O(1) |
| 删除边 | O(E) | O(1) |
| 深度优先搜索 | O(V + E) | O(V²) |
| 广度优先搜索 | O(V + E) | O(V²) |
| 空间复杂度 | O(V + E) | O(V²) |