《数据结构与算法-王争》学习笔记，记录备查

基本概念

跳表，在有序链表基础上加了多级索引的数据结构。是一种动态的数据结构。

跳表是一种用空间来换时间的典型存储结构。除了正常链表节点外，还需要额外的空间来存储索引的数据。在实际的应用中，节点的数据对象往往都会非常大，而索引中并不会存储节点的所有数据，仅仅是存储了指针，这样当节点数据远远大于索引占用空间的时候，索引的空间也就可以忽略了。

操作

查找

跳表查找的时间复杂度是O(logn)。

插入和删除

跳表的插入和删除，主要的时间耗费在查找上，所以时间复杂度都是O(logn)

索引的动态更新

当跳表的某两个索引之间的数据节点插入过多的时候，整个跳表便会变的不均衡，即第一级索引之间的原始节点数不一样。极端情况下，可能退化为单链表。此时，便需要及时的更新索引。

跳表是靠一个随机函数的返回值来决定将插入的值，添加到那几级索引的。例如，随机函数返回2，那么将插入的新加点，同时插入到第1和第2级索引中。随机函数即是和跳表的索引构建策略有关，并不是拍脑袋想出来的。

参考

• 静态数据结构：存储空间在程序执行过程中不能加以改变，定义好之后变由系统分配了固定大小的存储空间。
• 动态数据结构：不确定总的数据存储量，会根据数据元素的多少，而发生变化。

扩展阅读

• https://cloud.tencent.com/developer/article/1353762
• https://github.com/wangzheng0822/algo