数据结构与算法 - 线性表 - 跳表
约 517 字大约 2 分钟
数据结构与算法跳表
2023-09-08
《数据结构与算法-王争》学习笔记，记录备查
基本概念
跳表，在有序链表基础上加了多级索引的数据结构。是一种动态的数据结构。
跳表是一种用空间来换时间的典型存储结构。除了正常链表节点外，还需要额外的空间来存储索引的数据。在实际的应用中，节点的数据对象往往都会非常大，而索引中并不会存储节点的所有数据，仅仅是存储了指针，这样当节点数据远远大于索引占用空间的时候，索引的空间也就可以忽略了。
操作
查找
跳表查找的时间复杂度是O(logn)。
插入和删除
跳表的插入和删除，主要的时间耗费在查找上，所以时间复杂度都是O(logn)
索引的动态更新
当跳表的某两个索引之间的数据节点插入过多的时候，整个跳表便会变的不均衡，即第一级索引之间的原始节点数不一样。极端情况下，可能退化为单链表。此时，便需要及时的更新索引。
跳表是靠一个随机函数的返回值来决定将插入的值，添加到那几级索引的。例如，随机函数返回2，那么将插入的新加点，同时插入到第1和第2级索引中。随机函数即是和跳表的索引构建策略有关，并不是拍脑袋想出来的。
参考
- 静态数据结构：存储空间在程序执行过程中不能加以改变，定义好之后变由系统分配了固定大小的存储空间。
- 动态数据结构：不确定总的数据存储量，会根据数据元素的多少，而发生变化。
扩展阅读
- https://cloud.tencent.com/developer/article/1353762
- https://github.com/wangzheng0822/algo