跳表(java代码实现)

看《数据结构与算法之美》练手写了一下跳表
一开始自己只看了思路，写了一晚上还是有两个小bug
所以第二次写参考了一下别的博客

跳表的java实现

算是写出了个能用的吧(应该)

import java.util.*;




public class SkipList{
    
    private class Node{
        //前后上下
        private Node next,pre,up,down;
        private Integer key;
        private T value;
        public Node(int key,T value){
            this.key = key;
            this.value = value;
        }

        public Node getNext() { return next; }

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

        public Node getPre() { return pre; }

        public void setPre(Node pre) { this.pre = pre; }

        public Node getUp() { return up; }

        public void setUp(Node up) { this.up = up; }

        public Node getDown() { return down; }

        public void setDown(Node down) { this.down = down; }

        public int getKey() { return key; }

        public void setKey(int key) { this.key = key; }

        public T getValue() { return value; }

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

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value='" + value + ''' +
                    '}';
        }
    }

    //使tail有哨兵作用
    private static final int MAX_KEY = Integer.MAX_VALUE;
    //使head有哨兵作用
    private static final int MIN_KEY = Integer.MIN_VALUE;
    //掷骰子
    private static final Random random = new Random();
    //当前跳表内索引层的最大值
    private int currentMaxLevel = 1;
    //头尾结点，两个哨兵
    private Node head,tail;
    //当前跳表内存储了多少个元素(不包括索引结点)
    private int size = 0;

    public SkipList(){ clear(); }

    
    public void clear(){
        //重置层数
        setCurrentMaxLevel(1);
        //设置头尾
        setHead(new Node(MIN_KEY,null));
        setTail(new Node(MAX_KEY,null));
        //连接头尾
        horizontallink(getHead(),getTail());
    }

    //掷骰子，1即可以向上，否则不行
    private boolean canUpgrade(){
        return getRandom().nextInt(2)==1;
    }

    
    private void verticallink(Node down,Node up){
        down.setUp(up);
        up.setDown(down);
    }


    
    private void horizontallink(Node pre,Node next){
        pre.setNext(next);
        next.setPre(pre);
    }

    
    private void insertAfter(Node pre,Node cur){
        Node next = pre.getNext();
        horizontallink(pre,cur);
        horizontallink(cur,next);
    }

    
    private Node findNode(int key){
        Node node = getHead();
        while(true){
            while (node.getNext().getKey()<=key&&node.getNext().getKey() != MAX_KEY){
                node = node.getNext();
            }
            if(node.getDown() != null){
                node = node.getDown();
            }else {
                break;
            }
        }
        return node;
    }

    
    public void put(int key,T value){
        Node node = findNode(key);
        if(node.getKey() == key){
            node.setValue(value);
        }else{
            //1.创建出节点
            Node cur = new Node(key,value);
            //2.插入节点
            insertAfter(node,cur);
            //用作判定是否超过现有的层数
            int currentLevel = 1;
            //3.判定需不需要进行升层，使用抛硬币的方法,1/2的概率
            boolean canUpGradeFlag=canUpgrade();
            Node pre=node;
            while(canUpGradeFlag){
                //1.currentLevel
                if(currentLevel>=getCurrentMaxLevel()){
                    //2.此时先提高层数
                    setCurrentMaxLevel(getCurrentMaxLevel()+1);
                    //3.创建出两端
                    Node newHead = new Node(MIN_KEY,null);
                    Node newTail = new Node(MAX_KEY,null);
                    //4.水平上的连接
                    horizontallink(newHead,newTail);
                    //5.上下的承接
                    verticallink(getHead(),newHead);
                    verticallink(getTail(),newTail);
                    //6.赋值
                    setHead(newHead);
                    setTail(newTail);
                }
                //7.找到上方该插入位置的前后结点
                while(pre.getUp() == null){
                    pre = pre.getPre();
                }
                //得到上一层要插入位置的前一个结点
                pre = pre.getUp();
                 //8.新建关于当前插入节点的上层节点
                Node up = new Node(key, null);
                //插入节点
                insertAfter(pre,up);
                //层次关系
                verticallink(cur,up);
                //迭代更新下方结点，方便垂直连接该插入结点的各索引层
                cur = up;
                //更新flag
                canUpGradeFlag = canUpgrade();
                //当前结点的索引层数加一
                currentLevel++;
            }
            //节点数加一
            setSize(getSize()+1);
        }
    }

    
    public boolean remove(int key){
        Node node = findNode(key);
        if(node.getKey()!=key){ return false; }
        else{
            int currentLevel=0;
            while(node != null){
                Node pre = node.getPre();
                Node next = node.getNext();
                //水平方向断开该结点
                horizontallink(pre,next);
                //当该层除头尾结点外无结点时，说明该层包括以上层都可以舍弃了,进行一个新的更
                //结点的销毁是GC的事，我们只需要断开连接
                if(pre.getNext().getKey() == MAX_KEY && pre.getKey() == MIN_KEY&&getCurrentMaxLevel()>1){
                    setHead(pre.getDown());
                    setTail(next.getDown());
                    getHead().setUp(null);
                    getTail().setUp(null);
                    //记得拿当前的层数更新跳表层数
                    setCurrentMaxLevel(currentLevel);
                    break;
                }
                node = node.getUp();
                currentLevel++;
            }
            //节点数减一
            setSize(getSize()-1);
            return true;
        }
    }

    public T get(int key){
        Node node=findNode(key);
        if(node.getKey()!=key){
            return null;
        }
        return node.getValue();
    }

    
    public List> getRangeByKey(int start, int end){
        Node node=findNode(start);
        if(node.getKey()!=start){ node=node.getNext(); }
        List> list=new linkedList<>();
        while(node.key<=end){
            Map map=new HashMap<>();
            map.put(node.getKey(),node.getValue());
            list.add(map);
            node=node.getNext();
        }
        return list;
    }

    
    @Override
    public String toString(){
        StringBuilder sb=new StringBuilder();
        sb.append("SkipList:{n");
        sb.append("tlevel:"+this.currentMaxLevel+",n");
        sb.append("t{n");
        Node tempHead=getHead();
        while(tempHead!=null){
            sb.append("tt"+tempHead.getKey()+"t");
            Node tempNode=tempHead.getNext();
            while(tempNode.getKey()!=getTail().getKey()){
                sb.append(tempNode.getKey()+"t");
                tempNode=tempNode.getNext();
            }
            sb.append(tempNode.key+"n");
            tempHead=tempHead.getDown();
        }
        sb.append("t}n");
        sb.append("}n");
        return sb.toString();
    }

    public int getCurrentMaxLevel() { return currentMaxLevel; }

    private void setCurrentMaxLevel(int currentMaxLevel) { this.currentMaxLevel = currentMaxLevel; }

    private Node getHead() { return head; }

    private void setHead(Node head) { this.head = head; }

    private Node getTail() { return tail; }

    private void setTail(Node tail) { this.tail = tail; }

    private Random getRandom() { return random; }

    private int getSize() { return size; }

    private void setSize(int size) { this.size = size; }
}


class Demo{
    public static void main(String[] args) {
        SkipList skipList=new SkipList<>();
        skipList.put(1,1);
        skipList.put(2,2);
        skipList.put(2,3);
        System.out.println(skipList);
        skipList.remove(2);
        System.out.println(skipList);
        skipList.put(3,3);
        skipList.put(0,0);
        skipList.put(2,2);
        System.out.println(skipList.getRangeByKey(0,5));
    }
}

写了两晚上算是整出来了，好爽
当个ylg推荐一下最近喜欢的说唱捏
丁真进军说唱圈，《Zood》空降B榜