概述
跳跃表(SkipList)是链表加多级索引组成的数据结构。链表的数据结构的查询复条度是 O(N)。为了提高查询效率，可以在链表上加多级索引来实现快速查询。跳跃表不仅能提高搜索性能。也能提高插入和删除操作的性能。索引的层数也叫作跳跃表的高度
查找
在跳跃表的结构中会首先从顶层开始查找，当顶层不存在时向下一层查找，重复此查找过程直到跳跃到原始链表。如图所示，在 [1,3,4,10,1,20] 的链表中查找 10，首先从二级索引中查找，由于 1 和 4 都比 10 小，因此接着在一级索引查找，由于 10 大于 4 小于 11，因此接着向下查找，原始链表中 4 的下一个节点 10 便是需要查找的数据
插入
首先按照查找流程找到待插入元素的前驱和后继，然后按照随机算法生成一个高度值 height，最后将待插入的节点按照高度值生成一个垂直节点（这个节点的层数正好等于高度值），并将其插人跳跃表的多条链表中。如果高度值 heigh 大于插入前跳跃表的高度，那么跳跃表的高度被提升为 height，同时需要更新头节点和尾节点的指针指向。如果 height 小于或等于跳跃表的高度，那么需要更新待插入元素的前驱和后继的指针指向。在 [1,3,4.10,11,20] 的跳跃表中插入 18 的过程如图所示
删除
在删除节点时首先需要找到待删除的节点在每一层的前驱和后继，接着将其前驱节点的后继替换为待删除的节点的后继，删除 4 的过程如图所示
代码实现
import java.util.Random; import java.util.Stack; class SkipNode<T> { int key; T value; SkipNode right,down;//左右上下四个方向的指针 public SkipNode (int key,T value) { this.key=key; this.value=value; } } public class SkipList <T> { SkipNode headNode;//头节点，入口 int highLevel;//层数 Random random;// 用于投掷硬币 final int MAX_LEVEL = 32;//最大的层 SkipList(){ random=new Random(); headNode=new SkipNode(Integer.MIN_VALUE,null); highLevel=0; } public SkipNode search(int key) { SkipNode team=headNode; while (team!=null) { if(team.key==key){ return team; } else if(team.right==null) { //右侧没有了，只能下降 team=team.down; } else if(team.right.key>key) { //需要下降去寻找 team=team.down; } else { //右侧比较小向右 team=team.right; } } return null; } public void delete(int key) { //删除不需要考虑层数 SkipNode team=headNode; while (team!=null) { if (team.right == null) { //右侧没有了，说明这一层找到，没有只能下降 team=team.down; } else if(team.right.key==key) { //找到节点，右侧即为待删除节点 team.right=team.right.right;//删除右侧节点 team=team.down;//向下继续查找删除 } else if(team.right.key>key) { //右侧已经不可能了，向下 team=team.down; } else { //节点还在右侧 team=team.right; } } } public void add(SkipNode node) { int key=node.key; SkipNode findNode=search(key); if(findNode!=null) { //如果存在这个key的节点 findNode.value=node.value; return; } Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点，这些节点可能在右侧插入节点 SkipNode team=headNode;//查找待插入的节点 找到最底层的哪个节点。 while (team!=null) {//进行查找操作 if(team.right==null) { //右侧没有了，只能下降 stack.add(team);//将曾经向下的节点记录一下 team=team.down; } else if(team.right.key>key) { //需要下降去寻找 stack.add(team);//将曾经向下的节点记录一下 team=team.down; } else { //向右 team=team.right; } } int level=1;//当前层数，从第一层添加(第一层必须添加，先添加再判断) SkipNode downNode=null;//保持前驱节点(即down的指向，初始为null) while (!stack.isEmpty()) { //在该层插入node team=stack.pop();//抛出待插入的左侧节点 SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建 nodeTeam.down=downNode;//处理竖方向 downNode=nodeTeam;//标记新的节点下次使用 if(team.right==null) {//右侧为null 说明插入在末尾 team.right=nodeTeam; } //水平方向处理 else {//右侧还有节点，插入在两者之间 nodeTeam.right=team.right; team.right=nodeTeam; } //考虑是否需要向上 if(level>MAX_LEVEL)//已经到达最高级的节点啦 break; double num=random.nextDouble();//[0-1]随机数 if(num>0.5)//运气不好结束 break; level++; if(level>highLevel) { //比当前最大高度要高但是依然在允许范围内 需要改变head节点 highLevel=level; //需要创建一个新的节点 SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null); highHeadNode.down=headNode; headNode=highHeadNode;//改变head stack.add(headNode);//下次抛出head } } } public void printList() { SkipNode teamNode=headNode; int index=1; SkipNode last=teamNode; while (last.down!=null){ last=last.down; } while (teamNode!=null) { SkipNode enumNode=teamNode.right; SkipNode enumLast=last.right; System.out.printf("%-8s","head->"); while (enumLast!=null&&enumNode!=null) { if(enumLast.key==enumNode.key) { System.out.printf("%-5s",enumLast.key+"->"); enumLast=enumLast.right; enumNode=enumNode.right; } else { enumLast=enumLast.right; System.out.printf("%-5s",""); } } teamNode=teamNode.down; index++; System.out.println(); } } } 
