线性数据结构之跳跃列表(Skip List)详解及其Java实现
一、跳跃列表(Skip List)简介
列表(List)是最基本的数据结构之一。与数组(Array)类似,它们都是相同元素的集合。然后列表的查找效率并不理想,与树形结构(在前面提到了相关的数据结构如和等查找效率都很高,但是需要旋转或者变色的等操作保持自平衡。)相比,列表虽然简单,但是对元素的查找需要比对列表中的每个元素,查找速度较慢。为了兼顾列表的简单易用,并提高查找效率,William Pugh在1990年发表了一篇论文(),提出了跳跃列表(Skip List)数据结构,以空间换时间的方式,构造了一个层次的列表为数据建立索引,以提高列表的查找效率。



