数组、链表、跳表的基本实现和特性
数组-Array
时间复杂度
- prepend O(1)
- append O(n)
- lookup O(1)
- insert O(n)
- delete O(n)
链表-Link-List
时间复杂度
- prepend O(1)
- append O(1)
- lookup O(n)
- insert O(1)
- delete O(1)
跳表-skip-list
如何给有序的链表加速
一维数据的加速方式——升级为二维。
跳表查询的时间复杂度分析
小结
- 数组、链表、跳表的原理和实现
- 三者的时间复杂度、空间复杂度
- 跳表：升维思想 + 空间换时间
个人感受
学习了数组、链表、跳表三种数据结构的特点和时间复杂度分析，虽然项目中用的最多的还是数组，但后期如果优化的还是可以借鉴链表和跳表的设计思想。
课后作业
链接
简书_LRU缓存算法
leetcode-146. LRU 缓存机制
为啥 redis 使用跳表(skiplist)而不是使用 red-black？
