跳表的概念

对链表建立n级索引，例如每两个结点提取一个节点到上一层，称之为索引层。
图中的down表示down指针，指向下一级结点


跳表的时间复杂度

跳表的高度

跳表的高度是log2n

跳表的时间复杂度

跳表中查询某个数据的时间复杂度是O(logn)

跳表的空间复杂度及优化

跳表的空间复杂度

跳表的空间复杂度为O(n)

优化时间复杂度

如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，

虽然跳表的空间复杂度仍然是O(n)，但和每2个节点抽取一次相比占用的内存空间少了很多。

高效的动态插入和删除

时间复杂度

跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，

但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时。

在跳表中查找操作的时间复杂度是O(logn)，因此跳表的插入和删除操作的是时间复杂度也是O(logn)。

跳表索引动态更新

当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，

可以通过随机函数来决定将这个节点插入到哪几级索引中，比如随机函数生成了值K，那就可以把这个节点添加到第1级到第K级索引中。

跳表代码实现

参考