跳跃列表 在计算机科学中跳跃列表是一种数据结构它使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是 O  log  n  displaystyle Olog n 优于数组的 O  n  displaystyle On 复杂度 快速的查询效果是通过维护一个多层次的链表实现的且与前一层下面一层链表元素的数量相比每一层链表中的元素的数量更少见右下角示意图一开始时算法在最稀疏的层次进行搜索直至需要查找的元素在该层两个相邻的元素中间这时算法将跳转到下一个层次重复刚才的搜索直到找到需要查找的元素为止跳过的元素的方法可以是随机性选择或确定性选择其中前者更为常见