Skip Lists: The O(log n) Alternative to Balanced Trees

TL;DR: A skip list is a probabilistic data structure that upgrades a standard linked list's O(n) search time to O(log n). By layering multiple sorted "express lane" linked lists on top of each other,