skipList - java

Terry Chen — Thu, 06 Mar 2025 16:23:03 +0000

import java.util.ArrayList;

public class SkipList {
    public static class SkipListNode<K extends Comparable<K>, V> {
        public K key;
        public V value;
        public ArrayList<SkipListNode<K, V>> nextNodes;

        public SkipListNode(K key, V value) {
            this.key = key;
            this.value = value;
            nextNodes = new ArrayList<SkipListNode<K, V>>();
        }
    }

    public static class SkipListMap<K extends Comparable<K>, V> {
        public static final double PROBABILITY = 0.5;
        public SkipListNode<K, V> head;
        public int maxLevel;
        public int size;

        public SkipListMap() {
            this.head = new SkipListNode<>(null, null);
            head.nextNodes.add(null);//0层
            this.size = 0;
            this.maxLevel = 0;
        }

        public void put(K key, V value) {
            if (key == null) {
                return;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            //less.nextNodes.get(0) --
            SkipListNode<K, V> find = less.nextNodes.get(0);
            if (find.key.compareTo(key) == 0) {
                find.value = value;
            } else {
                int newNodeLevel = 0;
                while (Math.random() < PROBABILITY) {
                    newNodeLevel++;
                }
                while (newNodeLevel > maxLevel) {
                    maxLevel++;
                    head.nextNodes.add(null);
                }
                SkipListNode<K, V> newNode = new SkipListNode<>(key, value);
                for (int i = 0; i < newNodeLevel; i++) {
                    newNode.nextNodes.add(null);
                }
                int level = maxLevel;
                SkipListNode<K, V> pre = head;
                while (level >= 0) {
                    pre = mostRightLessNodeInLevel(pre, key, level);
                    if (level <= newNodeLevel) {
                        newNode.nextNodes.set(level, pre.nextNodes.get(level));
                        pre.nextNodes.set(level, newNode);
                    }
                    level--;
                }
                size++;
            }
        }
        public void remove(K key) {
            if (!containsKey(key)) {
                return;
            }
            size--;
            int level = maxLevel;
            SkipListNode<K, V> pre = head;
            while (level >= 0) {
                pre = mostRightLessNodeInLevel(pre, key, level);
                SkipListNode<K, V> next = pre.nextNodes.get(level);
                if (next != null && next.key.compareTo(key) == 0) {
                    pre.nextNodes.set(level, next.nextNodes.get(level));
                }
                if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
                    head.nextNodes.remove(level);
                    maxLevel--;
                }
                level--;
            }
        }

        public SkipListNode<K, V> mostRightLessNodeInTree(K key) {
            if (key == null) {
                return null;
            }
            int level = maxLevel;
            SkipListNode<K, V> cur = head;
            while (level >= 0) {
                cur = mostRightLessNodeInLevel(cur, key, level);
                level--;
            }
            return cur;
        }

        public SkipListNode<K, V> mostRightLessNodeInLevel(SkipListNode<K, V> cur, K key, int level) {
            if (key == null) {
                return null;
            }
            SkipListNode<K, V> pre = null;
            cur = cur.nextNodes.get(level);
            while (cur.key.compareTo(key) < 0) {
                pre = cur;
                cur = cur.nextNodes.get(level);
            }
            return pre;
        }{% embed `` %}

        public Boolean containsKey(K key) {
            if (key == null) {
                return false;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> find = less.nextNodes.get(0);
            return find != null && find.key.compareTo(key) == 0;
        }
    }
}
DEV Community: Terry Chen

skipList - java
