今天要介绍一个这样的数据结构:
单向链接
有序保存
支持添加、删除和检索操作
链表的元素查询接近线性时间
——跳跃表 Skip List
一、普通链表
对于普通链接来说,越靠前的节点检索的时间花费越低,反之则越高。而且,即使我们引入复杂算法,其检索的时间花费依然为O(n)。为了解决长链表结构的检索问题,一位名叫William Pugh的人于1990年提出了跳跃表结构。基本思想是——以空间换时间。
二、简单跳跃表(Integer结构)
跳跃表的结构是多层的,通过从最高维度的表进行检索再逐渐降低维度从而达到对任何元素的检索接近线性时间的目的O(logn)。