skipList - java

import java.util.ArrayList; public class SkipList { public static class SkipListNode { public K key; public V value; public ArrayList nextNodes; public SkipListNode(K key, V value) { this.key = key; this.value = value; nextNodes = new ArrayList(); } } public static class SkipListMap { public static final double PROBABILITY = 0.5; public SkipListNode 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 less = mostRightLessNodeInTree(key); //less.nextNodes.get(0) -- SkipListNode 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 newNode = new SkipListNode(key, value); for (int i = 0; i < newNodeLevel; i++) { newNode.nextNodes.add(null); } int level = maxLevel; SkipListNode pre = head; while (level >= 0) { pre = mostRightLessNodeInLevel(pre, key, level); if (level = 0) { pre = mostRightLessNodeInLevel(pre, key, level); SkipListNode 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 mostRightLessNodeInTree(K key) { if (key == null) { return null; } int level = maxLevel; SkipListNode cur = head; while (level >= 0) { cur = mostRightLessNodeInLevel(cur, key, level); level--; } return cur; } public SkipListNode mostRightLessNodeInLevel(SkipListNode cur, K key, int level) { if (key == null) { return null; } SkipListNode 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 less = mostRightLessNodeInTree(key); SkipListNode find = less.nextNodes.get(0); return find != null && find.key.compareTo(key) == 0; } } }

Mar 6, 2025 - 17:48


import java.util.ArrayList;

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

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

    public static class SkipListMap, V> {
        public static final double PROBABILITY = 0.5;
        public SkipListNode 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 less = mostRightLessNodeInTree(key);
            //less.nextNodes.get(0) --
            SkipListNode 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 newNode = new SkipListNode<>(key, value);
                for (int i = 0; i < newNodeLevel; i++) {
                    newNode.nextNodes.add(null);
                }
                int level = maxLevel;
                SkipListNode 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 pre = head;
            while (level >= 0) {
                pre = mostRightLessNodeInLevel(pre, key, level);
                SkipListNode 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 mostRightLessNodeInTree(K key) {
            if (key == null) {
                return null;
            }
            int level = maxLevel;
            SkipListNode cur = head;
            while (level >= 0) {
                cur = mostRightLessNodeInLevel(cur, key, level);
                level--;
            }
            return cur;
        }

        public SkipListNode mostRightLessNodeInLevel(SkipListNode cur, K key, int level) {
            if (key == null) {
                return null;
            }
            SkipListNode 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 less = mostRightLessNodeInTree(key);
            SkipListNode find = less.nextNodes.get(0);
            return find != null && find.key.compareTo(key) == 0;
        }
    }
}