Pixiv - Miracle
2-数据结构-绪论
856 字
4 分钟
2-数据结构-绪论
算法
大端整数闭区间的长度b - a + 1 中端整数半开区间的长度b - a 小端整数开区间的长度b - a - 1
时间复杂度
渐进上界
渐进同阶
数据结构
逻辑结构的粒度只到线性结构和非线性结构，十分粗糙，剩下的属于是ADT
graph TB
DS["数据结构"]
SS["存储结构"]
LS["逻辑结构"]
DC["数据运算"]
LinearS["线性结构(线性表)"]
NLinearS["非线性结构"]
SqSto["顺序存储"]
ChainSto["链式存储"]
IndexSto["索引存储"]
HashSto["散列存储"]
LinearList["一般线性表"]
String["串"]
Stack["栈"]
Queue["队列"]
Array["数组"]
Graf["图状结构"]
Tree["树形结构"]
DS -------> SS
DS --> LS
DS ----> DC
LS --> LinearS
LS --> NLinearS
LinearS --> LinearList
LinearS --> String
LinearS --> Stack
LinearS --> Queue
LinearS --> Array
NLinearS --> Graf
NLinearS --> Tree
SS --> SqSto
SS --> ChainSto
SS --> IndexSto
SS --> HashSto
链表
头结点指的是哑结点
不带头结点循环链表的头结点变化要改变尾结点的指针域，带头结点的不需要，如果没有表尾指针则需要O(n)
| 单双 | 头结点 | 循环 | 表头结点指针 | 表尾结点指针 | 头插 | 头删 | 尾插 | 尾删 |
|---|---|---|---|---|---|---|---|---|
| 单链表 | 无 | 不循环 | 无 | 无 | - | - | - | - |
| 单链表 | 无 | 不循环 | 无 | 有 | - | - | - | - |
| 单链表 | 无 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 单链表 | 无 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 无 | 循环 | 无 | 无 | - | - | - | - |
| 单链表 | 无 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 无 | 循环 | 有 | 无 | O(n) | O(n) | O(n) | O(n) |
| 单链表 | 无 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 有 | 不循环 | 无 | 无 | - | - | - | - |
| 单链表 | 有 | 不循环 | 无 | 有 | - | - | - | - |
| 单链表 | 有 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 单链表 | 有 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 有 | 循环 | 无 | 无 | - | - | - | - |
| 单链表 | 有 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(n) |
| 单链表 | 有 | 循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 单链表 | 有 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(n) |
| 双链表 | 无 | 不循环 | 无 | 无 | - | - | - | - |
| 双链表 | 无 | 不循环 | 无 | 有 | O(n) | O(n) | O(1) | O(1) |
| 双链表 | 无 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 双链表 | 无 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 无 | 循环 | 无 | 无 | - | - | - | - |
| 双链表 | 无 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 无 | 循环 | 有 | (无) | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 无 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 不循环 | 无 | 无 | - | - | - | - |
| 双链表 | 有 | 不循环 | 无 | 有 | O(n) | O(n) | O(1) | O(1) |
| 双链表 | 有 | 不循环 | 有 | 无 | O(1) | O(1) | O(n) | O(n) |
| 双链表 | 有 | 不循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 循环 | 无 | 无 | - | - | - | - |
| 双链表 | 有 | 循环 | (无) | 有 | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 循环 | 有 | (无) | O(1) | O(1) | O(1) | O(1) |
| 双链表 | 有 | 循环 | 有 | 有 | O(1) | O(1) | O(1) | O(1) |
双链表性质
-
双链表当且仅当头尾指针都没有的时候没有意义
-
头结点对双链表没有时间优化作用
-
循环双链表全O(1)
-
不循环双链表有O(1)没O(n)
单链表性质
- 单链表当且仅当，没有头指针，且不是，有尾指针并且循环的情况，的时候没有意义
- 单链表头部操作当且仅当，无头结点且有头无尾且循环的时候为O(n)
- 任何情况的单链表的尾删全部O(n)
- 单链表当且仅当有尾指针的时候尾插O(1)，其他O(n)
总结
-
循环双链表全O(1)
-
不循环双链表有O(1)没O(n)
-
任何情况的单链表的尾删全部O(n)
-
单链表有尾指针尾插O(1)其他O(n)
-
只有无头结点有头无尾循环单链表头部操作为O(n)
栈
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
随机文章 随机推荐