Skip List (C)
Topics: data structures, ordered map, probabilistic balancing
Problem
Implement a skip list — a probabilistic ordered map of int -> int giving
O(log n) expected get/insert plus ordered range scans (the structure behind
Redis sorted sets and LevelDB's memtable). Nodes come from caller-provided
storage; there is no delete, so the pool fills by bumping count (no malloc).
#define SKIP_MAX_LEVEL 16
typedef struct SkipNode { int key, val; int level; struct SkipNode *next[SKIP_MAX_LEVEL]; } SkipNode;
typedef struct { SkipNode *nodes; size_t cap; size_t count; int level; SkipNode head; unsigned long long rng; } SkipList;
void sl_init(SkipList *s, SkipNode *storage, size_t cap);
bool sl_get(SkipList *s, int key, int *out);
void sl_insert(SkipList *s, int key, int val); // insert or update
size_t sl_range(SkipList *s, int lo, int hi, int *keys, int *vals, size_t maxout); // lo<=k<=hi, ascending
size_t sl_len(const SkipList *s);
- Each node has a random tower height (
rand_level is provided). Level l's
next pointers form an express lane skipping nodes shorter than l.
sl_insert updates the value if the key exists; otherwise links a new node into
every level of its tower. If the pool is exhausted, drop a new key silently.sl_range walks the base level from the first key >= lo while key <= hi.
Key concepts
- Search by descending levels: start at the top level of the sentinel
head;
at each level advance while the next key is < target, then drop a level. You
land just before the target on the base list.
- The
update[] array: during insert, record the last node visited at each
level — those are exactly the predecessors whose next pointers you splice.
- Randomized balance: tower heights (not rotations) keep it balanced in
expectation. Your code must be correct for any heights
rand_level returns —
the tests check behavior, never structure.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/skiplist && /tmp/skiplist
Sign in to submit your solution.