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

基本概念

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

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

操作

查找

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

插入和删除

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

索引的动态更新

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

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

参考

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

扩展阅读