【 学习笔记】数组、链表、跳表的基本实现和特性
数组，链表，跳表的基本实现和特性
- 数组（Array)
list = [ ]
| 操作 | 复杂度 |
|---|---|
| prehead | O(1) |
| append | O(1) |
| lookup | O(1) |
| insert | O(n) |
| delete | O(n) |
P.S:
- lookup 指的是 随机访问数组里面的一个元素
- 正常情况下数组的prehead的时间复杂度是 O(1),但是可以优化到 O(1),采取的是申请稍大的内存空间，预留一部分给数组的开头
- 链表（linked list)
分类：
- 单链表
- 双向链表（Double linked list)
- 循环链表
| 操作 | 复杂度 |
|---|---|
| prehead | O(1) |
| append | O(1) |
| lookup | O(n) |
| insert | O(1) |
| delete | O(1) |
P.S: LRUCache 里面采用了 Linked List的数据结构
3. 跳表（skip list)
P.S:
- 跳表适合于链表里的元素有序的情况
- 跳表是一种插入\删除\搜索的时间复杂度都是 O(logn)的数据结构
为了提高链表线性查找的效率，采用了升维的办法，用空间换时间的办法，以此类推，增加多级索引
P.S:Skip List 在 Redis 里面的应用
总之，跳表中查询任意数据的时间复杂度就是 O(logn),空间复杂度为 O(n)
算法优化的办法：
- 升维
- 空间换时间