数据结构与算法 / 跳表
一、诞生原因
解决链表查询时耗时过长的问题。
二、基本信息
英文全称：Skip List 。
链表 + 多级索引（链表） = 跳表
三、原理说明
顾名思义，跳表的查询是在多个链表之间跳跃查询的，其路线类似于走台阶，如下图所示：
举个栗子：
某一时刻，想查询代号为 8 的节点的数据，按照常规链表查询，需要从最左侧挨个查询至最右侧，遍历次数为 8 ，时间复杂度为 O(n) 。
若添加一级索引，遍历次数为 5；若再添加二级索引，遍历次数为 4，遍历路线犹如下台阶一跳一跳的，故该结构名为跳表。
跳表实际上是典型的空间换时间的思想。
时间复杂度：跳表可以说是利用多级链表实现的二分查找，如图所示，故 时间复杂度为 O(logn) 。
参考：极客时间《数据结构与算法之美》王争
这门课真心推荐，内容很经典、栗子很形象，里面还包含了很多面试题目。真是居家旅行必备良药。
（SAW：Game Over！）