we live in a world so obsessed with structure—so much so that we often forget how much of it depends on chance. we crave predictability—systems we can understand and control. but sometimes randomness isn’t a flaw; it’s a feature.
skiplists are exactly that kind of structure. in today’s post, we’ll explore how they work and build one step by step.
find the full code here.
so…what exactly is a skiplist?
wikipedia describes it as “a probabilistic data structure that allows \(O(\log n)\) average complexity for searches and insertions.”1