3.1.数组链表跳表
数组
时间复杂度:
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(1) |
| 插入 | O(n) |
| 删除 | O(n) |
链表
时间复杂度:
| 操作 | 时间复杂度 |
|---|---|
| 头部增加 | O(1) |
| 尾部增加 | O(1) |
| 查找 | O(n) |
| 插入 | O(1) |
| 删除 | O(1) |
思想:
- 空间换时间
- 升维
单链表
node节点有next
双链表
node节点有next和privious
循环链表
node节点的next指向头节点
跳表
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(logn) |
空间复杂度: O(n)
扩展阅读:
LRU Cache-Linked list
https://www.jianshu.com/p/b1ab4a170c3c
https://leetcode-cn.com/problems/lru-cache/
Redis-Skip List
https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
https://www.zhihu.com/question/20202931