write a skiplist by java

Guangjie Chen — Sat, 25 Jan 2025 17:06:48 +0000

import java.util.ArrayList;

public class SkipList {
    // Node of the 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>>();
        }
    }

    // SkipList
    public static class SkipListMap<K extends Comparable<K>, V> {
        public static final double PROBABILITY = 0.5; // Probability for level generation
        public SkipListNode<K, V> head;
        public int maxLevel; // Maximum level in the SkipList
        public int size;

        public SkipListMap() {
            // The head is the leftmost "platform"
            this.head = new SkipListNode<>(null, null);
            head.nextNodes.add(null); // Level 0
            this.size = 0;
            this.maxLevel = 0;
        }

        // Add a node to the SkipList
        public void put(K key, V value) {
            if (key == null) {
                return;
            }
            // Check if the key already exists in the SkipList, update the value if so
            // Method: Find the rightmost node less than the key at the bottom level
            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 {
                // Generate a random level for the new node
                int newNodeLevel = 0;
                while (Math.random() < PROBABILITY) {
                    newNodeLevel++;
                }
                // If the new level exceeds the current max level, adjust the head levels and max level
                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) {
                    // Find the predecessor node at the current level
                    pre = mostRightLessNodeInLevel(pre, key, level);
                    // Insert the new node between the predecessor and its successor
                    if (level <= newNodeLevel) {
                        newNode.nextNodes.set(level, pre.nextNodes.get(level));
                        pre.nextNodes.set(level, newNode);
                    }
                    level--;
                }
                size++;
            }
        }

        // Remove a node from the SkipList
        public void remove(K key) {
            // Check if the key exists in the SkipList
            if (!containsKey(key)) {
                return;
            }
            size--;
            // Start from the top level, remove the node at each level until the bottom
            int level = maxLevel;
            SkipListNode<K, V> pre = head;
            while (level >= 0) {
                // Find the predecessor node at the current level
                pre = mostRightLessNodeInLevel(pre, key, level);
                // Remove the node
                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 a level has only the head node left, remove this level
                if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
                    head.nextNodes.remove(level);
                    maxLevel--;
                }
                level--;
            }
        }

        // Start from the top level and traverse down to find the rightmost node less than the key at level 0
        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;
        }

        // At a specific level, find the rightmost node less than the key
        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;
        }

        // Check if the SkipList contains the given key
        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: Guangjie Chen

write a skiplist by java
