03、数组、链表、跳表
2020-05-08 本文已影响0人
vannesspeng
数组
Array
Array
Array增加元素
Array增加元素
Array增加元素
Array增加元素
image.png
image.png
image.png
image.png
链表
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
跳表
链表的缺陷
如何给链表加速
添加一级索引
添加二级索引
添加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
总结
• 数组、链表、跳表的原理和实现
• 三者的时间复杂度、空间复杂度
• 工程运用
• 跳表：升维思想 + 空间换时间
