03、数组、链表、跳表

数组

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

总结

• 数组、链表、跳表的原理和实现
• 三者的时间复杂度、空间复杂度
• 工程运用
• 跳表：升维思想 + 空间换时间