Java跳表(SkipList)的实现

跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查操作。

package structs;

import java.util.Random;

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private int levelCount = 1;
    private Node head = new Node();
    private Random random = new Random();

    public Node find(int value){
        Node p = head;
        for(int i = levelCount - 1; i >= 0; i--){
            //如果在这一个level上存在下一个数据节点且下一个数据节点的值小于value，p往后挪一个
            //直到这一个level走完或者值在区间内，切换下一个层级
            while(p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
        }
        //到最下层依照上面的索引找到的位置往后找一位即可判断
        if(p.forwards[0] != null && p.forwards[0].data == value) return p.forwards[0];
        return null;
    }

    public void insert(int value){
        Node p = head;
        int level = randomLevel();
        Node node = new Node();
        node.data = value;
        node.maxLevel = level;
        //记录要更新的node
        Node update[] = new Node[level];
        //插入一个新的node，主要目标更新保存的forwards
        for(int i = level; i >= 0; i--){
            //在计算得到的level中依次找适合的位置
            while(p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
            update[i] = p;
        }
        //更新指向
        for(int i = 0; i < level; i++){
            node.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = node;
        }
        if(levelCount < level) levelCount = level;
    }

    public void delete(int value){
        Node[] deleteNode = new Node[MAX_LEVEL];
        Node p = head;
        for(int i = levelCount - 1; i >=0; i--){
            //确定每个层级中要删除的value对应的node
            while(p.forwards[i] != null && p.forwards[i].data < value){
                p = p.forwards[i];
            }
            //当前level中要删除的p，更新到node数组中
            deleteNode[i] = p;
        }
        //从底层扫，每层删除
        if(p.forwards[0] != null && p.forwards[0].data == value){
            //根据上面deleteNode[]中保存的要删除的node，更新前后的指向
            for(int i = levelCount - 1; i >= 0; i--){
                if(deleteNode[i] != null && deleteNode[i].forwards[i].data == value){
                    deleteNode[i].forwards[i] = deleteNode[i].forwards[i].forwards[i];
                }
            }
        }
    }

    public void printAll(){
        Node p = head;
        while(p.forwards[0] != null){
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }
    
    private int randomLevel() {
        int level = 0;
        for(int i = 0; i < MAX_LEVEL; i++){
            if(random.nextInt()%2 == 1){
                level++;
            }
        }
        return level;
    }

    class Node{
        private int data;
        //核心在这个forwards数组，他存放了各个level索引的下一个数据节点
        private Node[] forwards = new Node[MAX_LEVEL];
        private int maxLevel;

        public String toString(){
            StringBuilder sb = new StringBuilder();
            sb.append("{data: ");
            sb.append(data);
            sb.append("; level: ");
            sb.append(maxLevel);
            sb.append(" }");
            return sb.toString();
        }
    }


}