链表虽然添加和删除操作比较快速，但是查询时却需要从起点遍历。所以，链表的查询操作影响性能。
跳跃表通过增加多层的排序链表，在查找时能显著提升效率。
本文介绍跳跃表数据结构以及添加、删除节点时详细过程。
方法/步骤
-
1
跳跃表结构：跳跃表是一个包含多层的顺序链表。其结构如下图所示：
-
2
每一层都是有序的，最后一层包含所有的数据，而中间每层只包含部分数据。如果一个数据出现在某一层，则往下每层都包含该数据。
由此，跳跃表其实就是类似一个十字链表结构。
-
3
跳跃表查找：跳跃表就是用来提高查找效率的，从最顶层开始查找，如果找到节点则返回。如果节点小，则继续在该层查找。如果未找到或找到节点大，则转向下一层继续查找。
比如下图中查找节点9，只需要3个步骤就能快速找到。如果是顺序链表，则需要9次。
-
4
添加节点：首先需要查找节点插入到合适位置，并且给该节点设置合适的层数。
计算节点添加到链表中哪一层是一个问题，因为层数分布的约稀疏其实对查找效率提升的更快。
一种算法是：抛硬币方式，添加节点默认在第一层，至于是否添加后后面几层，每层都执行一个随机算法决定。
-
5
在连续计算随机数得到节点跨越层数后，我们在每一层中更新链表结构。
如下图，添加节点4，其层数为3。则修改每一层4节点前后链表。
-
6
删除节点：已经知道节点跨越层数，所以删除该节点时，需要更新每一层的链表结构。具体过程与十字链表的更新类似。
如下，我们再将节点4删除后，跳跃表结构：
END
经验内容仅供参考，如果您需解决具体问题(尤其法律、医学等领域)，建议您详细咨询相关领域专业人士。
作者声明：本篇经验系本人依照真实经历原创，未经许可，谢绝转载。
展开阅读全部
文章评论