导入
线性与非线性数据结构概述
在本节课中，我们将回顾所学所有数据结构的时间复杂度，并将它们分类为线性数据结构和非线性数据结构。
在介绍完所有常用的数据结构后，我们来看看哪些是线性数据结构，哪些是非线性数据结构。这些信息在为算法选择合适的数据结构时非常有用。
线性数据结构
在线性数据结构中，每个元素最多连接一个（下一个元素）或两个（前一个和后一个）其他元素。这类结构的遍历方式是线性的，因此插入、删除和查找操作的时间复杂度通常为 O(n)。
列表、链表、栈 和 队列 都属于线性数据结构的典型例子。
非线性数据结构
非线性数据结构与线性结构正好相反。在非线性结构中，每个元素可以连接多个其他元素。其遍历过程不是线性的，因此查找、插入和删除操作可以在 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)（push） | O(1)（pop） | O(n) | O(n) |
| 队列 | O(1)（入队） | O(1)（出队） | O(n) | O(n) |
| 二叉堆 | O(lg n) | O(lg n)（removeMin()） | 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) |
字典树（Trie）（字母表大小 d，最长单词长度 n） | O(n) | O(n) | O(n) | O(d^n) |
图的操作复杂度
对于包含 n 个顶点和 m 条边的图，一些常见操作的时间复杂度如下：
| 操作 | 邻接表 | 邻接矩阵 |
|---|---|---|
| 添加顶点 | O(1) | O(1) |
| 删除顶点 | 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) |