Skip List Algorithm

A skip list is a probabilistic algorithm for maintaining a sorted sequence of elements that supports fast search, insertion and deletion by layering several linked lists on top of one another, where the bottom layer holds every element in order and each higher layer holds a randomly chosen, progressively sparser subset of the elements below it, acting as an express lane over the layer beneath it. A search starts at the top, sparsest layer and moves forward along it until the next element would overshoot the target, then drops down a layer and repeats the process, continuing down through the layers until the target is found or shown to be absent, so most of a search's distance is covered quickly in the sparse upper layers. Each element's height, meaning how many layers it appears in, is decided independently at random when it is inserted, commonly with each additional layer only half or a quarter as likely as the one below it, which is what removes the need for any deliberate rebalancing after an insertion or deletion. William Pugh invented the skip list in 1989, presenting it explicitly as an alternative to balanced trees that reaches the same expected logarithmic time bounds with a simpler implementation; its layered, largely independent structure also makes it comparatively easy to adapt for concurrent access by multiple threads.