collections/skip_list_utils library

Skip list: a probabilistic ordered set — roadmap #502.

Keeps elements in sorted order with O(log n) expected search, insert, and delete, plus O(1) floor/ceiling neighbor lookups, without the rotation bookkeeping a balanced BST needs. Each node is linked at one or more levels; a node is promoted to the next level up with probability 1/2, so on average half the nodes appear at each higher level and a search can skip exponentially far ahead before dropping down — hence "skip list".

This is a SET: add returns false for a value already present (uniqueness is decided by the supplied Comparator returning 0). Promotion uses an injectable Random so tests can seed it for fully deterministic structure.

Classes

SkipList<T>

A probabilistic ordered set keyed by a Comparator.