A skip list is a probabilistic data structure that operates similarly to a typical sorted list with the added benefit of O(log n) search complexity. Skip lists were first introduced by William Pugh in 1989. He had hoped that this data structure would supplant balanced binary trees as the implementation method of choice for many applications as skip lists have the same time complexity for insertion/deletion and searching while also being much simpler to implement.


At its core a skip list is a sorted linked list with multiple levels. Level 0 contains all of the values in the list and…

Conner Ozenne

Computer Science major at Southern Methodist University

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store