一、跳跃链表的构建思路

跳表一般基于有序链表实现。首先是链表的排序问题，对于链表的来说，排序的问题其实等价于怎么找到新增节点的在有序链表中插入位置。

对于数组而言，只需要利用二分法查找到对应的位置，然后插入，并移动之后的元素，主要的开销在于拓展内存以及移动元素。

链表没法这么处理。链表的优势在于插入后无需移动后续元素，但无法跳跃查询，主要开销在于定位插入位置。

结合两者实际上就是跳表的基本思想：底层数据用有序链表维护，方便数据插入；在底层数据节点之上构建多层不同的稀疏索引（比如从上往下不断变密集），加速节点的查询，快速定位。

索引节点+数据节点就是跳表的核心，但这又有了另一个问题：怎么样便利的维护索引节点？

显然，将每层的分区的中点作为索引节点是不合适的，因为节点的增减是一种常见需求，每次数据节点的增减都会导致索引节点的变化，带来不少额外的开销。我们需要一种与数据节点数量无关的、确定索引节点位置的方法。

基本的思路就是使用随机化。在每次增加节点时确定是否需要此节点上建立索引节点。

延伸阅读：

二、跳表（Skip List）是什么

跳表（Skip List）是一种基于链表的数据结构，它允许快速地查找、插入和删除元素，其时间复杂度为O(log n)。

在跳表中，每个节点都有多个指针，这些指针分别指向同一层中的其他节点，具体地说，每个节点有一个指向下一个节点的指针，还有一个或多个指向下一层节点的指针。这些指针可以帮助我们在查找时跳过一些节点，从而减少查找的时间。

跳表中的节点通常按照升序排列，最底层的节点包含所有元素。每个节点还有一个随机的层数，用来确定它在哪些层中有指针。一般来说，每个节点的层数都是随机生成的，但是要满足一定的概率分布。这样可以确保跳表的高度不会太高，从而保证其时间复杂度的性能。

在跳表中，查找、插入和删除操作都是基于每个节点的指针进行的。具体来说，查找操作从较高层开始，按照升序查找节点，如果当前节点的下一个节点的值比要查找的值大，则跳到下一层，继续查找，直到找到目标节点或者到达最底层。插入和删除操作也是类似的，只需要在查找到目标节点后，修改其指针即可。

总之，跳表是一种简单而高效的数据结构，可以在O(log n)的时间复杂度内进行查找、插入和删除操作。虽然它在实际应用中并不像红黑树那样广泛使用，但在某些场景下，跳表可以提供比其他数据结构更好的性能表现。

上一篇

广义表和树有什么区别?

下一篇

为什么说双端队列比栈和队列灵活，但实际却没有后两者有用?