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

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more