数据结构与算法--跳表

跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。

跳表.png
这种链表加多级索引的结构，就是跳表。

跳表的查找、插入、删除操作的时间复杂度都是 O(logn)。
跳表的空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。

跳表的插入.png

参考:
极客时间：《数据结构与算法》王争, 17 | 跳表：为什么Redis一定要用跳表来实现有序集合？