常见数据结构的时间复杂度比较
| 数组 | 单向链表 | 双向链表 | 队列 | 栈 | ||
|---|---|---|---|---|---|---|
| 访问 | 通过索引 | O(1) | 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(N) |
| 增加 | 最后一个节点后 | O(1) | O(1) | O(1) | O(1) | O(1) |
| 删除 | 第一个结点 | O(N) | O(1) | O(1) | O(1) | O(N) |
| 删除 | 指定结点 | O(1) | O(1) | O(1) | O(N) | O(N) |
| 删除 | 最后一个结点 | O(1) | O(N) | O(1) | O(N) | O(1) |
| 查找 | 指定结点 | O(N) | O(N) | O(N) | O(N) | O(N) |