Data Structures the Fun Way

14 Skip Lists

This chapter introduces the skip list, a sorted linked list with multiple pointers that allow us to occasionally jump forward to an element further ahead in the list during operations like search, insertion, or deletion. This potential to jump mitigates one of the major concerns with linked lists—that we have to scan through all the elements to find a single target. Skipping some elements saves precious time.

To envision how skip lists work, consider the strategy I employ every time I lose my place in a book. Determined to avoid spoilers, I do not use binary search, which may jump to parts of the text I haven’t read yet. Instead, ...