如何实现数据结构中的跳表算法？

本文共计3070个文字，预计阅读时间需要13分钟。

简介：有序数组可以使用二分查找快速检索一个数据，但链表没有此方法。对于一个单向链表来说，即使存储的数据是有序的，如果想要从中查找某个数据，也无法直接使用二分查找。

简介

有序的数组可以使用二分查找的方法快速检索一个数据，但是链表没有办法使用二分查找。

对于一个单向链表来说，即使链表中存储的是有序的数据，但如果想要从中查找某个数据时，也只能从头到尾遍历链表，其时间复杂度是 \(O(n)\)。

为了提高链表的查询效率，使其支持类似“二分查找”的方法，对链表进行多层次扩展，这样的数据结构就是跳表。跳表对标的是平衡树，是一种提升链表插入、删除、搜索效率的数据结构。

首先，跳表处理的是有序的链表，一般使用双向链表更加方便。

然后，每两个结点提取一个结点到上一级，提取的这一层被称作为索引层。

这时候，当想要查找 19 这个数字，可以先从索引层开始查找；当到达 17 时，发现下一个结点存储 21 这个数字，则可以确定，想要查找的 19 肯定是在 17 到 21 之间；这时候可以转到下一层（原始链表）中查找，快速从 17 开始检索，很快就可以查找出 19 这个数字。

加入一层索引之后，查找一个结点需要遍历的结点个数减少了，也就是查找效率提高了。