导入
线性与非线性数据结构概述
在本节课中，我们将回顾已学习的数据结构的时间复杂度，并将它们分类为线性数据结构和非线性数据结构。
现在我们已经介绍了所有常见的数据结构，接下来看看哪些是线性数据结构，哪些是非线性数据结构。了解这一点有助于在设计算法时选择合适的数据结构。
线性数据结构
在线性数据结构中，每个元素最多与一个（下一个元素）或两个（前一个和后一个）其他元素相连。遍历这些结构时是线性的，因此搜索操作的时间复杂度为 O(n)；插入和删除的复杂度则取决于具体结构和操作位置（例如链表头插为 O(1)）。
数组、链表、栈 和 队列 都是线性数据结构的典型例子。
非线性数据结构
线性数据结构的反面是非线性数据结构。在非线性数据结构中，每个元素可以连接到多个其他元素。遍历不是线性的，因此搜索、插入和删除操作的时间复杂度可以达到 O(log n)，甚至 O(1)。
树、图 和 哈希表 都是非线性数据结构。
时间与空间复杂度速查表
以下是本课程所学数据结构的复杂度总结，帮助你在不同场景下比较它们的性能表现。
注意： 表中 n 表示结构中存储的元素总数。
| 数据结构 | 插入 | 删除 | 搜索 | 空间复杂度 |
|---|---|---|---|---|
| 数组 | O(n) | O(n) | O(n) | O(n) |
| 单向链表 | O(1)（头插） | O(1)（删除头节点） | O(n) | O(n) |
| 双向链表 | O(1)（头插） | O(1)（删除头节点） | O(n) | O(n) |
| 带尾指针的双向链表 | O(1)（头插或尾插） | O(1)（删除头节点或尾节点） | O(n) | O(n) |
| 栈 | O(1)（入栈） | O(1)（出栈） | O(n) | O(n) |
| 队列 | O(1)（入队） | O(1)（出队） | O(n) | O(n) |
| 二叉堆 | O(lg n) | O(lg n)（删除最小值或最大值） | O(n) | O(n) |
| 二叉树 | O(n) | O(n) | O(n) | O(n) |
| 二叉搜索树 | O(n) | O(n) | O(n) | O(n) |
| 红黑树 / AVL 树 / 2-3 树 | O(lg n) | O(lg n) | O(lg n) | O(n) |
| 哈希表 | O(n)：最坏情况；O(1)：均摊 | O(n)：最坏情况；O(1)：均摊 | O(n)：最坏情况；O(1)：均摊 | O(n) |
字典树（字母表大小为 d，最长单词长度为 n） | O(n) | O(n) | O(n) | O(d^n) |
图的操作复杂度
以下是包含 n 个顶点和 m 条边的图中常见操作的时间与空间复杂度。
| 操作 | 邻接表 | 邻接矩阵 |
|---|---|---|
| 添加顶点 | O(n) | O(n^2) |
| 删除顶点 | O(m+n) | O(n^2) |
| 添加边 | O(1) | O(1) |
| 删除边 | O(n) | O(1) |
| 深度优先/广度优先搜索 | O(m+n) | O(n^2) |
| 空间复杂度 | O(m+n) | O(n^2) |