数据结构-链表之跳表SkipList

代码实现

public class SkipList {
    //允许的最大层数
    private static int maxLevel=16;
    //头结点，默认16层
    private Node head=new Node(-1,16);
    //当前跳表节点个数
    public int size=0;
    //当前跳表的层数
    public int levelCount=1;

    /**
     * 查找元素
     * @param value
     * @return
     */
    public Node find(int value){
        Node temp=head;
        for(int i=levelCount-1;i>=0;i--){
            while(temp.next[i]!=null&&temp.next[i].value<value){
                temp=temp.next[i];
            }
        }

        //判断是否有该元素存在
        if(temp.next[0]!=null&&temp.next[0].value==value){
            System.out.println(value+" 查找成功");
            return temp.next[0];
        }else{
            return null;
        }
    }

    public void insert(int value){
        int level=getLevel();
        Node cur=new Node(value,level);
        //记录新节点cur的前驱节点
        Node[] update=new Node[level];

        Node temp=head;
        for(int i=level-1;i>=0;i--){
            while(temp.next[i]!=null&&temp.next[i].value<value){
                temp=temp.next[i];
            }
            update[i]=temp;
        }

        //将插入节点的每一层连接起来
        for(int i=0;i<level;i++){
            if(update[i]==null){
                continue;
            }
            cur.next[i]=update[i].next[i];
            update[i].next[i]=cur;
        }

        //判断是否需要更新跳表的层数
        if(level>levelCount){
            levelCount=level;
        }
        size++;
        System.out.println(value+" 插入成功");
    }

    public void delete(int value){
        //找到value的节点，并且保存它的所有前驱节点
        Node[] update=new Node[levelCount];
        Node temp=head;
        for(int i=levelCount-1;i>=0;i--){
            while(temp.next[i]!=null&&temp.next[i].value<value){
                temp=temp.next[i];
            }
            update[i]=temp;
        }

        if(temp.next[0]!=null&&temp.next[0].value==value){
            size--;
            System.out.println(value + " 删除成功");
            for(int i=levelCount-1;i>=0;i--){
                if(update[i].next!=null&&update[i].next[i].value==value){
                    update[i].next[i]=update[i].next[i].next[i];
                }
            }
        }
    }

    public void printAllNode(){
        Node temp=head;
        while(temp.next[0]!=null){
            System.out.println(temp.next[0].value + "  ");
            temp = temp.next[0];
        }
    }

    //模拟抛硬币
    private int getLevel(){
        int level=1;
        while(true){
            int t=(int)(Math.random()*1000);
            if(t%2==0){
                level++;
            }else{
                break;
            }
        }
        /*
        if(level>16){
            level=16;
        }*/
        System.out.println("当前的level = " + level);
        return level;
    }
}

/**
 * 跳表节点
 */
public class Node {
    public int value;
    //跨越几层
    public int level;
    //
    public Node[] next;
    public Node(int value,int level){
        this.value=value;
        this.level=level;
        next=new Node[level];
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public int getLevel() {
        return level;
    }

    public void setLevel(int level) {
        this.level = level;
    }

    public Node[] getNext() {
        return next;
    }

    public void setNext(Node[] next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", level=" + level +
                ", next=" + Arrays.toString(next) +
                ‘}‘;
    }
}


public class SkipListTest {
    //测试数据
    public static void main(String[] args) {
        SkipList list = new SkipList();
        for (int i = 0; i < 15; i++) {
            list.insert(i);
        }
        list.printAllNode();
        list.delete(4);
        list.printAllNode();
        System.out.println(list.find(3));
        System.out.println(list.size + " " + list.levelCount);
    }
}

数据结构-链表之跳表SkipList

原文：https://www.cnblogs.com/maughamQ/p/14691477.html