DEV Community

Guangjie Chen
Guangjie Chen

Posted on

write a skiplist by java


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;
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Billboard image

The fastest way to detect downtimes

Join Vercel, CrowdStrike, and thousands of other teams that trust Checkly to streamline monitoring.

Get started now

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay