M.DAI'M²

今天要介绍一个这样的数据结构：

1. 单向链接
2. 有序保存
3. 支持添加、删除和检索操作
4. 链表的元素查询接近线性时间

——跳跃表 Skip List

一、普通链表

对于普通链接来说，越靠前的节点检索的时间花费越低，反之则越高。而且，即使我们引入复杂算法，其检索的时间花费依然为O(n)。为了解决长链表结构的检索问题，一位名叫William Pugh的人于1990年提出了跳跃表结构。基

 最近看了一种数据结构叫做skipList，redis和levelDB都是用了它。Skip List是在有序链表的基础上进行了扩展，解决了有序链表结构查找特定值困难的问题，查找特定值的时间复杂度为O(logn)，他是一种可以代替平衡树的数据结构。

    下面是skipList的一个介绍，转载来的，源地址：http://kenby.iteye.com/blog/1187303，为防