import java.util.Random;

public class SkipList {

    // My question is how the skip list make the whole structure balanced? Maybe it create index levels randomly, with
    // good chance the index keys are chosen randomly and equal distributed.

    public static void main(String[] args) {
        new SkipList().test();
    }

    public void test() {

        MySkipList<Integer, Integer> list = new MySkipList<>();

        for (int i = 0; i < 10000; i++) {
            list.put(i, new Random().nextInt(10000));
        }

        list.remove(100);
        System.out.println(list.get(2).value);
        System.out.println("Height: " + list.height + ", Size: " + list.size());
    }

    class MySkipList<K extends Comparable<K>, V> {

        // With smaller INDEX_EXPANDING_PROBABILITY, it is easy to create more inner index nodes, and there are
        // INDEX_EXPANDING_PROBABILITY^height probability that SkipList will generate a new level. The larger the
        // INDEX_EXPANDING_PROBABILITY is, the deeper the hierarchy is.
        private static final double INDEX_EXPANDING_PROBABILITY = 0.15;

        private SkipListNode<K, V> head;
        private SkipListNode<K, V> tail;

        private int size;
        private int height;

        private Random random;

        public MySkipList() {

            head = new SkipListNode(SkipListNode.HEAD_KEY, null);
            tail = new SkipListNode(SkipListNode.TAIL_KEY, null);

            head.next = tail;
            tail.prev = head;

            size = 0;
            height = 0;

            random = new Random();
        }

        public void put(K key, V value) {
            // find the proper position for insertion
            SkipListNode<K, V> pos = findInsertionPoint(key);

            // update it if exists
            if (pos.key.equals(key)) {
                pos.value = value;

                return;
            }

            // otherwise pos.key is smaller than the give key, but the most closest one.

            SkipListNode<K, V> newNode = new SkipListNode<>(key, value);

            // append newNode after pos first, then consider add level
            append(pos, newNode);

            // Do not forget to update the counter of list size.
            size++;

            int currentLevel = 0;
            while (random.nextDouble() < INDEX_EXPANDING_PROBABILITY) {
                // generate an empty level on the top of the current level only if current level is the top level.
                if (currentLevel >= height) {
                    generateLevel();
                }

                // is it possible following loop is a forever loop?
                // impossible! only pos on the top level will result in pos.up == null.
                // but if it is on the highest level, above adding empty level
                // logic will be triggered. So it will never happen.
                while (pos.up == null) {
                    pos = pos.prev;
                }

                pos = pos.up;

                // idxNode serves as the index node with pos's key, but with empty value.
                // All the non-bottom lists work like the lookup table.
                SkipListNode<K, V> idxNode = new SkipListNode(key, null);
                append(pos, idxNode);

                newNode.up = idxNode;
                idxNode.down = newNode;

                newNode = idxNode;

                // initially, the node is inserted on the bottom level, then move upwards.
                currentLevel++;
            }
        }

        private void append(SkipListNode<K, V> p, SkipListNode<K, V> q) {
            // append q after p

            // p<->a; q

            // q->a
            q.next = p.next;

            // p<-q
            q.prev = p;

            // q<->a
            q.next.prev = q;

            // p<->q
            p.next = q;

            // p<->q<->a
        }

        public SkipListNode<K, V> get(K key) {
            // if there is node binding with given key, below function will return it.
            SkipListNode<K, V> p = findInsertionPoint(key);

            if (p.key.equals(key)) {
                return p;
            }

            return null;
        }

        private SkipListNode<K, V> findInsertionPoint(K key) {
            // find out the position at which node binding with the given the key can insert. but
            // if the key is equal with the node at insertion position, it will return the node
            // binding with the given key. if not equal, it will return the node of closest key
            // which is <= given key.

            // if there are already node

            SkipListNode<K, V> p = head;

            while (true) {
                // if the node p.next.key >= key, do not move forward, leave it to the next level.
                // otherwise move forward to next node for much closer key.
                if (p.next != null && p.next.key.compareTo(key) <= 0) {
                    p = p.next;

                    continue;
                }

                // the lower level is more precise and with more specific ranges.
                // for example, top level MIN<->MAX; sub top level MIN<->20<->40<->MAX

                // p.down != null indicates current level is not the bottom level, dig down/descend to next level.
                if (p.down != null) {
                    p = p.down;

                    continue;
                }

                // reach the bottom level and find the proper slot for insertion, then break the loop
                // It can always find a proper insertion slot because even key is very large, it will can't be more
                // greater than Integer.MAX_VALUE which is the tail of the list.
                if (p.next != null && p.next.key.compareTo(key) > 0) {
                    break;
                }
            }

            return p;
        }

        public V remove(K key) {
            SkipListNode<K, V> p = get(key);
            if (p == null) {
                return null;
            }

            V value = p.value;

            while (p != null) {
                // a<->p<->b

                // a<-b
                p.next.prev = p.prev;

                // a<->b
                p.prev.next = p.next;

                // remove upper index nodes which contains p.val
                p = p.up;
            }

            size--;

            return value;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        public void generateLevel() {
            SkipListNode<K, V> p1 = new SkipListNode(SkipListNode.HEAD_KEY, null);
            SkipListNode<K, V> p2 = new SkipListNode(SkipListNode.TAIL_KEY, null);

            p1.next = p2;
            p2.prev = p1;

            p1.down = head;
            head.up = p1;

            p2.down = tail;
            tail.up = p2;

            // head.up and tail.up are always null
            // head and tail are promoted to the highest level finally.
            head = p1;
            tail = p2;

            height++;
        }
    }


    class SkipListNode<K extends Comparable<K>, V> {

        public static final int HEAD_KEY = Integer.MIN_VALUE;
        public static final int TAIL_KEY = Integer.MAX_VALUE;

        public K key;
        public V value;

        public SkipListNode<K, V> prev, next, up, down;

        public SkipListNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }

            if (o == null || !(o instanceof SkipListNode)) {
                return false;
            }

            SkipListNode<K, V> ent;

            try {
                ent = (SkipListNode<K, V>) o;
            } catch (ClassCastException ex) {
                return false;
            }

            return (ent.key.equals(key)) && (ent.value == value);
        }

        @Override
        public String toString() {
            return "key-value:" + key + "," + value;
        }
    }
}

References

  1. https://www.cnblogs.com/shoshana-kong/p/10798489.html
  2. https://en.wikipedia.org/wiki/Skip_list
  3. http://ticki.github.io/blog/skip-lists-done-right/
  4. https://www.geeksforgeeks.org/skip-list-set-3-searching-deletion/
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-22 14:20:55

results matching ""

    No results matching ""