跳跃表(简称跳表)由美国计算机科学家William Pugh发明于1989年。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。
图形化探究跳表，先回顾链表。链表的优势就是更高效的插入、删除。痛点就是查询很慢很慢！每次查询都是一种O(n)复杂度的操作。
在查询某个节点的时候，首先会从上一层快速定位节点所在的一个范围，如果找到具体范围向下然后查找代价很小，当然在表的结构设计上会增加一个向下的索引(指针)用来查找确定底层节点。平均查找速度平均为O(n/2)。但是当节点数量很大的时候，它依旧很慢很慢。我们都知道二分查找是每次都能折半的去压缩查找范围，要是有序链表也能这么跳起来那就太完美了。没错跳表就能让链表拥有近乎的接近二分查找的效率的一种数据结构，其原理依然是给上面加若干层索引，优化查找速度。
特点和优势
- 快速查找：跳表支持以对数时间复杂度（O(log n)）进行查找操作。相比于普通链表的线性查找（O(n)），跳表通过多层索引实现了快速的二分查找。
- 高效插入和删除：跳表在插入和删除操作上也能够达到对数时间复杂度。通过灵活地调整索引层数和节点的连接关系，跳表能够保持平衡并保证有序性。
- 简单而高效：相比于平衡二叉树等复杂的数据结构，跳表的实现相对简单，并且在大多数情况下能够提供类似的性能。
- 无需自平衡：与自平衡的数据结构（如红黑树）相比，跳表的插入和删除操作无需进行复杂的平衡调整，使得实现和维护更加简单。