设计跳表

设计跳表

每一个新节点层数随机生成 通过最大层数与随机概率因子生成随即层数

通过currentLevel记录最大层数，头节点与尾节点对应最大高度

 class Skiplist{
    //最大层数
    private static int DEFAULT_MAX_LEVEL=32;
    private static double DEFAULT_P_FACTOR=0.25;

    //创建头节点
    Node head=new Node(null,DEFAULT_MAX_LEVEL);
    int currentLevel=1;

    public Skiplist(){}

    public boolean search(int target){
        Node searchNode=head;
        for(int i=currentLevel-1;i>=0;i--){
            searchNode=findClosest(searchNode,i,target);
            if(searchNode.next[i]!=null&&searchNode.next[i].value==target){
                return true;
            }
        }
        return false;
    }

    public void add(int num){
        int level=randomLevel();
        Node updateNode=head;
        Node newNode=new Node(num,level);
        for(int i=currentLevel-1;i>=0;i--){
            updateNode = findClosest(updateNode, i, num);
            if(i<level){
                if(updateNode.next[i]==null){
                    updateNode.next[i]=newNode;
                }else{
                    newNode.next[i]=updateNode.next[i];
                    updateNode.next[i]=newNode;
                }
            }
        }
        if(level>currentLevel){
            for(int i=currentLevel;i<level;i++){
                head.next[i]=newNode;
            }
            currentLevel=level;
        }
    }

    public boolean erase(int num){
        boolean flag=false;
        Node deleteNode=head;
        for(int i=currentLevel-1;i>=0;i--){
            deleteNode=findClosest(deleteNode,i,num);
            if(deleteNode.next[i]!=null&&deleteNode.next[i].value==num){
                deleteNode.next[i]=deleteNode.next[i].next[i];
                flag=true;
                continue;
            }
        }
        return flag;
    }

    //获得添加位置
    public Node findClosest(Node node,int level,int value){
        while(node.next[level]!=null&&value>node.next[level].value){
            node=node.next[level];
        }
        return node;
    }

    public int randomLevel(){
        int level=1;
        while(Math.random()<DEFAULT_P_FACTOR&&level<DEFAULT_MAX_LEVEL){
            level++;
        }
        return level;
    }

    class Node{
        Integer value;
        Node[] next;

        public Node(Integer value,int size){
            this.value=value;
            this.next=new Node[size];
        }
    }
}