Skip List (Go + Python)

from __future__ import annotations
import random
from typing import Optional
MAX_LEVEL = 16
P = 0.5
class Node:
    """One skip list entry. forward[i] points to the next node that also
    participates at level i -- level 0 is the full sorted list, higher
    levels are increasingly sparse "express lanes" over the same keys."""
    def __init__(self, key: int, value: int, level: int) -> None:
        self.key = key
        self.value = value
        self.forward: list[Optional["Node"]] = [None] * level
class SkipList:
    """Ordered map backed by a probabilistic multi-level linked list.
    Expected O(log n) search/insert/delete -- see the accompanying guide
    for why the randomized level distribution achieves that bound."""
    def __init__(self) -> None:
        # header is a sentinel present at every level; it never holds a
        # real key and always sorts before every real entry.
        self.header = Node(key=-1, value=-1, level=MAX_LEVEL)
        self.level = 1
    def _random_level(self) -> int:
        """Flip a coin (p=0.5) repeatedly, climbing one more level on each
        "heads", stopping on the first "tails" or at MAX_LEVEL. Geometric
        distribution: P(level == k) = p^(k-1) * (1-p)."""
        lvl = 1
        while lvl < MAX_LEVEL and random.random() < P:
            lvl += 1
        return lvl
    def search(self, key: int) -> Optional[int]:
        """Return the value for key, or None if key is not present."""
        x = self.header
        for i in range(self.level - 1, -1, -1):
            while x.forward[i] is not None and x.forward[i].key < key:
                x = x.forward[i]
        x = x.forward[0]
        if x is not None and x.key == key:
            return x.value
        return None
    def insert(self, key: int, value: int) -> None:
        """Insert key/value, or update value if key already exists."""
        # update[i] is the rightmost node at level i still left of the
        # insertion point -- exactly the pointers that need rewiring.
        update: list[Node] = [self.header] * MAX_LEVEL
        x = self.header
        for i in range(self.level - 1, -1, -1):
            while x.forward[i] is not None and x.forward[i].key < key:
                x = x.forward[i]
            update[i] = x
        x = x.forward[0]
        if x is not None and x.key == key:
            x.value = value
            return
        new_level = self._random_level()
        if new_level > self.level:
            # The coin flips climbed higher than any existing node -- the
            # header stands in as the update pointer for the new top levels.
            for i in range(self.level, new_level):
                update[i] = self.header
            self.level = new_level
        new_node = Node(key, value, new_level)
        for i in range(new_level):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
    def delete(self, key: int) -> bool:
        """Remove key if present. Returns whether it was found."""
        update: list[Node] = [self.header] * MAX_LEVEL
        x = self.header
        for i in range(self.level - 1, -1, -1):
            while x.forward[i] is not None and x.forward[i].key < key:
                x = x.forward[i]
            update[i] = x
        x = x.forward[0]
        if x is None or x.key != key:
            return False
        for i in range(self.level):
            if update[i].forward[i] is not x:
                break
            update[i].forward[i] = x.forward[i]
        # Shrink self.level if the top levels are now empty -- keeps
        # future searches from wasting steps on levels with nothing on them.
        while self.level > 1 and self.header.forward[self.level - 1] is None:
            self.level -= 1
        return True

package skiplist;
import java.util.concurrent.ThreadLocalRandom;
// MAX_LEVEL caps how tall the list can ever grow. 16 comfortably covers
// millions of entries at p=0.5 (2^16 is far more levels than log2(n) will
// ever demand in practice) without unbounded per-node memory.
// SkipList is an ordered map backed by a probabilistic multi-level linked
// list. header is a sentinel node present at every level that never holds
// a real key and always sorts before every real entry.
public class SkipList<K extends Comparable<K>, V> {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    // Node is one entry in the skip list. forward[i] points to the next
    // node that also participates at level i. Level 0 is the full sorted
    // list; higher levels are increasingly sparse "express lanes" over the
    // same keys.
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] forward;
        @SuppressWarnings("unchecked")
        Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            this.forward = new Node[level];
        }
    }
    private final Node<K, V> header;
    private int level;
    // New creates an empty skip list.
    @SuppressWarnings("unchecked")
    public SkipList() {
        this.header = new Node<>(null, null, MAX_LEVEL);
        this.level = 1;
    }
    // randomLevel flips a coin (p=0.5) repeatedly, climbing one more level on
    // each "heads", stopping on the first "tails" or at MAX_LEVEL. This is a
    // geometric distribution: P(level == k) = p^(k-1) * (1-p), so level 1 is
    // the most common outcome and each additional level is half as likely as
    // the one before it.
    private int randomLevel() {
        int lvl = 1;
        while (lvl < MAX_LEVEL && ThreadLocalRandom.current().nextDouble() < P) {
            lvl++;
        }
        return lvl;
    }
    // search returns the value stored for key, or null if it was not found.
    // It walks from the top level down: scan right while the next node's key
    // is still less than the target, then drop a level once the next node
    // would overshoot (or there is no next node at this level).
    public V search(K key) {
        Node<K, V> x = header;
        for (int i = level - 1; i >= 0; i--) {
            while (x.forward[i] != null && x.forward[i].key.compareTo(key) < 0) {
                x = x.forward[i];
            }
        }
        x = x.forward[0];
        if (x != null && x.key.compareTo(key) == 0) {
            return x.value;
        }
        return null;
    }
    // insert adds key/value, or updates value if key already exists.
    @SuppressWarnings("unchecked")
    public void insert(K key, V value) {
        // update[i] records the rightmost node at level i that is still to the
        // left of the insertion point -- exactly the nodes whose forward[i]
        // pointer needs to be rewired to splice the new node in.
        Node<K, V>[] update = new Node[MAX_LEVEL];
        Node<K, V> x = header;
        for (int i = level - 1; i >= 0; i--) {
            while (x.forward[i] != null && x.forward[i].key.compareTo(key) < 0) {
                x = x.forward[i];
            }
            update[i] = x;
        }
        x = x.forward[0];
        if (x != null && x.key.compareTo(key) == 0) {
            x.value = value;
            return;
        }
        int newLevel = randomLevel();
        if (newLevel > level) {
            // The coin flips climbed higher than any existing node. The header
            // itself becomes the "update" pointer for the new top levels since
            // nothing else reaches that high yet.
            for (int i = level; i < newLevel; i++) {
                update[i] = header;
            }
            level = newLevel;
        }
        Node<K, V> newNode = new Node<>(key, value, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }
    // delete removes key if present, returning whether it was found.
    @SuppressWarnings("unchecked")
    public boolean delete(K key) {
        Node<K, V>[] update = new Node[MAX_LEVEL];
        Node<K, V> x = header;
        for (int i = level - 1; i >= 0; i--) {
            while (x.forward[i] != null && x.forward[i].key.compareTo(key) < 0) {
                x = x.forward[i];
            }
            update[i] = x;
        }
        x = x.forward[0];
        if (x == null || x.key.compareTo(key) != 0) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            if (update[i].forward[i] != x) {
                break;
            }
            update[i].forward[i] = x.forward[i];
        }
        // Shrink level if the top levels are now empty -- keeps future
        // searches from wasting steps scanning levels with nothing on them.
        while (level > 1 && header.forward[level - 1] == null) {
            level--;
        }
        return true;
    }
}

import unittest
from skiplist import SkipList
class TestSkipList(unittest.TestCase):
    def test_search_found(self) -> None:
        sl = SkipList()
        sl.insert(3, 300)
        sl.insert(6, 600)
        sl.insert(9, 900)
        self.assertEqual(sl.search(6), 600)
    def test_search_missing(self) -> None:
        sl = SkipList()
        sl.insert(1, 10)
        self.assertIsNone(sl.search(99))
    def test_insert_updates_existing_key(self) -> None:
        sl = SkipList()
        sl.insert(5, 50)
        sl.insert(5, 999)
        self.assertEqual(sl.search(5), 999)
    def test_ordered_traversal_after_many_inserts(self) -> None:
        sl = SkipList()
        keys = [17, 3, 9, 1, 12, 5, 19, 7]
        for k in keys:
            sl.insert(k, k * 10)
        for k in keys:
            self.assertEqual(sl.search(k), k * 10)
    def test_delete_removes_key(self) -> None:
        sl = SkipList()
        sl.insert(1, 1)
        sl.insert(2, 2)
        sl.insert(3, 3)
        self.assertTrue(sl.delete(2))
        self.assertIsNone(sl.search(2))
        self.assertEqual(sl.search(1), 1)
        self.assertEqual(sl.search(3), 3)
    def test_delete_missing_key(self) -> None:
        sl = SkipList()
        sl.insert(1, 1)
        self.assertFalse(sl.delete(42))
if __name__ == "__main__":
    unittest.main()

package skiplist;
public class SkipListTest {
    public static void main(String[] args) {
        testSearchFound();
        testSearchMissing();
        testInsertUpdatesExistingKey();
        testOrderedTraversalAfterManyInserts();
        testDeleteRemovesKey();
        testDeleteMissingKey();
        System.out.println("All tests passed");
    }
    static void testSearchFound() {
        SkipList<Integer, Integer> sl = new SkipList<>();
        sl.insert(3, 300);
        sl.insert(6, 600);
        sl.insert(9, 900);
        Integer v = sl.search(6);
        if (v == null || v != 600) {
            throw new AssertionError("search(6) = " + v + "; want 600");
        }
    }
    static void testSearchMissing() {
        SkipList<Integer, Integer> sl = new SkipList<>();
        sl.insert(1, 10);
        if (sl.search(99) != null) {
            throw new AssertionError("search(99) should return null for a key that was never inserted");
        }
    }
    static void testInsertUpdatesExistingKey() {
        SkipList<Integer, Integer> sl = new SkipList<>();
        sl.insert(5, 50);
        sl.insert(5, 999);
        Integer v = sl.search(5);
        if (v == null || v != 999) {
            throw new AssertionError("search(5) = " + v + "; want 999 (update, not duplicate)");
        }
    }
    static void testOrderedTraversalAfterManyInserts() {
        SkipList<Integer, Integer> sl = new SkipList<>();
        int[] keys = {17, 3, 9, 1, 12, 5, 19, 7};
        for (int k : keys) {
            sl.insert(k, k * 10);
        }
        for (int k : keys) {
            Integer v = sl.search(k);
            if (v == null || v != k * 10) {
                throw new AssertionError("search(" + k + ") = " + v + "; want " + (k * 10));
            }
        }
    }
    static void testDeleteRemovesKey() {
        SkipList<Integer, Integer> sl = new SkipList<>();
        sl.insert(1, 1);
        sl.insert(2, 2);
        sl.insert(3, 3);
        if (!sl.delete(2)) {
            throw new AssertionError("delete(2) should return true for a present key");
        }
        if (sl.search(2) != null) {
            throw new AssertionError("key 2 should no longer be found after delete");
        }
        if (sl.search(1) == null) {
            throw new AssertionError("key 1 should be unaffected by deleting key 2");
        }
        if (sl.search(3) == null) {
            throw new AssertionError("key 3 should be unaffected by deleting key 2");
        }
    }
    static void testDeleteMissingKey() {
        SkipList<Integer, Integer> sl = new SkipList<>();
        sl.insert(1, 1);
        if (sl.delete(42)) {
            throw new AssertionError("delete(42) should return false for a key that was never inserted");
        }
    }
}