漫画：什么是 “跳表” ？

    实现代码：

    1. public class SkipList{
    3.     //结点“晋升”的概率
    4.     private static final double PROMOTE_RATE = 0.5;
    5.     private Node head,tail;
    6.     private int maxLevel;
    8.     public SkipList() {
    9.         head = new Node(Integer.MIN_VALUE);
    10.         tail = new Node(Integer.MAX_VALUE);
    11.         head.right = tail;
    12.         tail.left = head;
    13.     }
    15.     //查找结点
    16.     public Node search(int data){
    17.         Node p= findNode(data);
    18.         if(p.data == data){
    19.             System.out.println("找到结点：" + data);
    20.             return p;
    21.         }
    22.         System.out.println("未找到结点：" + data);
    23.         return null;
    24.     }
    26.     //找到值对应的前置结点
    27.     private Node findNode(int data){
    28.         Node node = head;
    29.         while(true){
    30.             while (node.right.data!=Integer.MAX_VALUE && node.right.data<=data) {
    31.                 node = node.right;
    32.             }
    33.             if (node.down == null) {
    34.                 break;
    35.             }
    36.             node = node.down;
    37.         }
    38.         return node;
    39.     }
    41.     //插入结点
    42.     public void insert(int data){
    43.         Node preNode= findNode(data);
    44.         //如果data相同，直接返回
    45.         if (preNode.data == data) {
    46.             return;
    47.         }
    48.         Node node=new Node(data);
    49.         appendNode(preNode, node);
    50.         int currentLevel=0;
    51.         //随机决定结点是否“晋升”
    52.         Random random = new Random();
    53.         while (random.nextDouble() < PROMOTE_RATE) {
    54.             //如果当前层已经是最高层，需要增加一层
    55.             if (currentLevel == maxLevel) {
    56.                 addLevel();
    57.             }
    58.             //找到上一层的前置节点
    59.             while (preNode.up==null) {
    60.                 preNode=preNode.left;
    61.             }
    62.             preNode=preNode.up;
    63.             //把“晋升”的新结点插入到上一层
    64.             Node upperNode = new Node(data);
    65.             appendNode(preNode, upperNode);
    66.             upperNode.down = node;
    67.             node.up = upperNode;
    68.             node = upperNode;
    69.             currentLevel++;
    70.         }
    71.     }
    73.     //在前置结点后面添加新结点
    74.     private void appendNode(Node preNode, Node newNode){
    75.         newNode.left=preNode;
    76.         newNode.right=preNode.right;
    77.         preNode.right.left=newNode;
    78.         preNode.right=newNode;
    79.     }
    81.     //增加一层
    82.     private void addLevel(){
    83.         maxLevel++;
    84.         Node p1=new Node(Integer.MIN_VALUE);
    85.         Node p2=new Node(Integer.MAX_VALUE);
    86.         p1.right=p2;
    87.         p2.left=p1;
    88.         p1.down=head;
    89.         head.up=p1;
    90.         p2.down=tail;
    91.         tail.up=p2;
    92.         head=p1;
    93.         tail=p2;
    94.     }
    96.     //删除结点
    97.     public boolean remove(int data){
    98.         Node removedNode = search(data);
    99.         if(removedNode == null){
    100.             return false;
    101.         }
    103.         int currentLevel=0;
    104.         while (removedNode != null){
    105.             removedNode.right.left = removedNode.left;
    106.             removedNode.left.right = removedNode.right;
    107.             //如果不是最底层，且只有无穷小和无穷大结点，删除该层
    108.             if(currentLevel != 0 && removedNode.left.data == Integer.MIN_VALUE && removedNode.right.data == Integer.MAX_VALUE){
    109.                 removeLevel(removedNode.left);
    110.             }else {
    111.                 currentLevel ++;
    112.             }
    113.             removedNode = removedNode.up;
    114.         }
    116.         return true;
    117.     }
    119.     //删除一层
    120.     private void removeLevel(Node leftNode){
    121.         Node rightNode = leftNode.right;
    122.         //如果删除层是最高层
    123.         if(leftNode.up == null){
    124.             leftNode.down.up = null;
    125.             rightNode.down.up = null;
    126.         }else {
    127.             leftNode.up.down = leftNode.down;
    128.             leftNode.down.up = leftNode.up;
    129.             rightNode.up.down = rightNode.down;
    130.             rightNode.down.up = rightNode.up;
    131.         }
    132.         maxLevel --;
    133.     }
    135.     //输出底层链表
    136.     public void printList() {
    137.         Node node=head;
    138.         while (node.down != null) {
    139.             node = node.down;
    140.         }
    141.         while (node.right.data != Integer.MAX_VALUE) {
    142.             System.out.print(node.right.data + " ");
    143.             node = node.right;
    144.         }
    145.         System.out.println();
    146.     }
    148.     //链表结点类
    149.     public class Node {
    150.         public int data;
    151.         //跳表结点的前后和上下都有指针
    152.         public Node up, down, left, right;
    154.         public Node(int data) {
    155.             this.data = data;
    156.         }
    157.     }
    159.     public static void main(String[] args) {
    160.         SkipList list=new SkipList();
    161.         list.insert(50);
    162.         list.insert(15);
    163.         list.insert(13);
    164.         list.insert(20);
    165.         list.insert(100);
    166.         list.insert(75);
    167.         list.insert(99);
    168.         list.insert(76);
    169.         list.insert(83);
    170.         list.insert(65);
    171.         list.printList();
    172.         list.search(50);
    173.         list.remove(50);
    174.         list.search(50);
    175.     }
    176. }