A skip list is a probabilistic, balanced ordered structure -- a multi-level linked list where higher levels are sparser "express lanes" that let a search skip over large stretches of the full bottom-level list in one hop. It supports expected O(log n) insert/search/delete, the same job this course's B-Tree exercise solves for an on-disk index -- but with NO rebalancing operation at all: instead of splitting/merging nodes to keep a tree balanced, each node's height is decided independently, once, by a coin flip at insert time. Because there's no shared rebalancing step touching multiple nodes at once, a skip list is a much simpler structure to make concurrent-friendly than a tree. RocksDB uses a skip list as its default memtable index for close to this reason: the memtable has to absorb an unbounded stream of single-key inserts (with lock-free concurrent readers) as cheaply as possible, and a skip list's insert only ever touches the handful of nodes immediately around the new key -- never a multi-node split cascading up through a tree.

SkipListNode and _random_level (the coin-flip level generator: keep climbing a level with probability p, capped at max_level) are done for you. Implement:

• insert(key, value, level=None): insert key with value, replacing the value if key is already present. level is normally left None (use _random_level(), like a real skip list) -- but the caller may pass an explicit level to force a specific height, which the tests use to build a known multi-level structure without relying on chance.
• search(key): return the value stored for key, or None if absent.
• delete(key): remove key if present (return True); return False if it wasn't there. Must unlink the node from EVERY level it appeared at, and shrink self.level while the topmost level(s) are now empty.

Example

sl = SkipList()
sl.insert(10, "ten")
sl.insert(20, "twenty")
sl.search(10)    # -> "ten"
sl.delete(10)     # -> True
sl.search(10)    # -> None (unlinked at every level it was on)

Constraints

• At every level, keys stay in ascending order.
• A node inserted at level L appears in the forward chain of every level from 0 to L -- level i + 1 is always a subsequence of level i.
• insert/search/delete must all use the same top-down, level-by-level walk to locate where a key belongs (or would belong): starting from self.head at self.level, follow forward[i] while the next node's key is still less than the target, then drop down a level and repeat. A linear scan of just level 0 defeats the entire point of the structure.

Real-world grounding

• RocksDB's skip-list memtable index: memtable/skiplist.h

Real skip lists (RocksDB's included) add more: lock-free concurrent reads via memory barriers on the forward pointers, a fixed branching table as an alternative to calling a random number generator on every insert, and (in RocksDB's specific case) no real delete at all -- a memtable is append-only for its whole lifetime, so a logical delete is written as a tombstone entry rather than unlinking a node. But "layered express lanes, each level a subsequence of the one below, walk down level by level" is the core idea underneath all of it.