SkipList

有序数组可以快速索引，但是增删困难
链表可以快速增删，但是索引困难
结合两者的优点，以时间换空间，用数组索引部分数据，链表存数据，索引还可以多层，或者直接用链表多层索引，就是跳表。

经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。目前开源软件 Redis 和 LevelDB 都有用到它，
它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单。
跳跃表的性质；

由很多层结构组成；
每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点；
最底层的链表包含了所有的元素；
如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；
链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；
搜索
其基本原理就是从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。

插入
既然要插入，首先需要确定插入的层数，这里有不一样的方法。1. 看到一些博客写的是抛硬币，只要是正面就累加，直到遇见反面才停止，最后记录正面的次数并将其作为要添加新元素的层；2. 还有就是一些博客里面写的统计概率，先给定一个概率p，产生一个0到1之间的随机数，如果这个随机数小于p，则将高度加1，直到产生的随机数大于概率p才停止，根据给出的结论，当概率为1/2或者是1/4的时候，整体的性能会比较好（其实当p为1/2的时候，也就是抛硬币的方法）。

当确定好要插入的层数以后，则需要将元素都插入到从最底层到第k层。

删除
在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。