Skip to main content

Skip List

Learn Skip List (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Skip List: A Sorted List with Express Lanes A skip list is a sorted linked list with extra express lanes . Level 0 holds every element; level 1 holds about half of them, level 2 about a quarter, and so on. To search, start at the top level and move right while the next key is smaller, then drop down a level and repeat. When inserting, a coin flip decides how many levels the new element joins. It gives expected O(log n) search, insert and delete like a balanced tree, with far simpler code and no rotations. Redis uses it for sorted sets.

More lessons in Advanced Data Structures