一、跳表的前传
1、一个有序链表搜索、添加、删除的平均时间复杂度是多少（重要，竟然理解还是不到位）？
- O(n)
image.png
2、能否利用二分搜索优化有序链表，将搜索、添加、删除的平均时间复杂度降低至O(logn)？
- 不行
- 链表没有想数据那样的
高效随机访问（O(1)时间复杂度），所以不能像有序数组那样直接进行二分搜索优化
3、那有没有其他办法让有序链表搜素、添加、删除的平均时间复杂度降低至 O(logn)？
- 有 ，使用跳表（SkipList）
image.png
二、跳表介绍
1、跳表的英文名是什么？在 xxx 基础上，增加了 xxx 功能？
- 跳表(SkipList)：在
有序链表的基础上增加了“跳跃”的功能
2、跳表的设计初衷是什么？对比平衡树有什么优点吗？
-
初衷：为了取代平衡树（比如红黑树） -
对比平衡树优点：①跳表的实现和维护会更加简单②跳表的搜索、删除、添加的平均时间复杂度是 O(logn)
image.png
3、使用跳表优化链表的思想？
image.png
- 如上图所示，如果要访问 25 要怎么走？
- 如上图所示，如果要访问 18 要怎么走？
4、跳表的添加和删除思路（把下面这张图记牢了，跳表的精髓也就掌握了）？
image.png
网友评论