ds-skip-list-ranked
The implementation is a fully ranked skip list in Go with probabilistic level generation. Each node carries forward pointers and span integers at every level, where span[i] records how many nodes are skipped by the forward pointer at level i. This allows GetByRank(k) to find the k-th element in O(log n) expected time by accumulating span values as it descends.
Core data structures:
const MaxLevel = 32
const probability = 0.5
type Node struct {
key int
value interface{}
forward []*Node
span []int
}
type SkipList struct {
head *Node
level int
size int
rng *rand.Rand
}
Key algorithms:
| Operation | Approach | Complexity |
|---|---|---|
Insert(key, val) |
Track update[] nodes and rank[] at each level; generate random level; splice node and adjust spans (split old span into left+right parts) |
O(log n) expected |
Delete(key) |
Track update[]; remove node; merge span of removed node back into predecessor's span; shrink height if head's top level is empty |
O(log n) expected |
Search(key) |
Greedy descent from top level, following forward pointers while key < target |
O(log n) expected |
GetByRank(k) |
Start at head with rank=0; at each level, while rank+span[i] ≤ k, advance and accumulate rank; return node when level 0 reached |
O(log n) expected |
Level generation uses a geometric distribution with P(level up) = 0.5:
func (sl *SkipList) randomLevel() int {
lvl := 0
for lvl < MaxLevel-1 && sl.rng.Float64() < probability {
lvl++
}
return lvl
}
Insert span maintenance is the trickiest part. For each level i of the new node:
- newNode.span[i] = update[i].span[i] - (rank[0] - rank[i]) — the right portion of the split
- update[i].span[i] = (rank[0] - rank[i]) + 1 — the left portion (includes new node)
- For levels above the new node's height, increment update[i].span[i] by 1
All 13 tests pass, covering: | Test | What it verifies | |------|-----------------| | `TestInsertAndSearch` | Basic insert + search for existing and missing keys | | `TestUpdateExistingKey` | Insert on existing key replaces value, does not duplicate | | `TestDelete` | Delete existing, missing keys; size tracking; empty-after-delete | | `TestGetByRank` | Exact rank ordering for 7 elements inserted out of order | | `TestGetByRankAfterInsertDelete` | Mixed insert/delete operations maintain correct ranks | | `TestGetByRankSingleElement` | Single element, then empty after delete | | `TestLargeInsertAndGetByRank` | Sequential insert of 1000 elements, verify every rank | | `TestReverseInsertAndGetByRank` | Reverse-order insert of 500 elements, verify every rank | | `TestSearchNonExistent` | Search for keys less-than, between, and greater than existing | | `TestDeleteNonExistent` | Delete non-existent keys leaves size unchanged | | `TestEmptyList` | All operations on empty list return correct sentinel values | | `TestDuplicateKeyInsertBehavior` | Duplicate key insert updates value, size stays 1, rank works | | `TestLargeRandomOperations` | 2000 random inserts, verify all by rank, delete evens, verify odds remain in order | Edge cases tested: - **Empty list**: search, delete, get-by-rank all return false - **Single element**: get-by-rank works, delete empties correctly - **Duplicate keys**: value updated, no duplicate node, size unchanged - **Out-of-bounds rank**: `GetByRank(0)` and `GetByRank(size+1)` return false - **Head shrinkage**: after deleting all nodes at the highest level, `sl.level` shrinks gracefully - **Large scale**: 2000 random elements, then delete 1000, verify all remaining ranks ---
{"model": "gpt-4o", "problem_class": "ds-skip-list-ranked", "result": "passed", "tests": 13}