Skip to content
Back to Data StructuresAll lessons

Data Structures

Skip List

Search, insert, delete: O(log n) on average. Each level lets you skip over a chunk of items at once, instead of checking them one by one. Space: O(n), since higher levels only add a smaller number of extra shortcut pointers.

The idea, in plain English

A skip list is like a subway map with express trains stacked over the local line. The local line, the bottom level, stops at every single station, in order. This is slow to cross town. An express line above it skips over several stops at once. A super-express line above that skips even more. To find a station, ride the fastest line you can until you'd overshoot it. Then drop down one line and keep going. You land on your stop after just a handful of hops, instead of walking every local station.

How it works

  1. 1Store items in sorted order across several stacked linked levels.
  2. 2The bottom level is a complete, ordinary sorted linked list. Every item lives there.
  3. 3Higher levels hold only some of those same items, acting as 'express lanes' that skip over chunks of the level below.
  4. 4To search: start at the top level. Move forward while the next item is still less than the target. Drop down a level whenever moving forward would overshoot. Repeat until you land at the bottom.

When you'd use it

Use a skip list anywhere you want fast sorted-order search, insert, and delete, without the rebalancing logic a balanced tree needs. Redis's sorted sets are built on skip lists internally.

Common beginner mistakes

  • Don't assume a skip list is just a fancier array. It's really a stack of linked lists. The 'skipping' comes from having fewer items, and thus bigger jumps, at each level up.
  • Remember that every item must exist at the bottom level. Higher levels are just optional shortcuts on top of that complete base list, not separate storage.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Sorted: 10 20 30 40 50 60 70 80
Level sizes: 8 4 2 1
Has 40: yes
Has 45: no
Has 80: yes

Note: Real-world skip lists pick each node's level with a coin flip, a random process. This is what makes them 'probabilistically balanced.' This lesson picks levels with a fixed rule instead, purely so the example is repeatable. But the search and insert logic is exactly the same as a production skip list.

See it in motion

Ride the express laneSkip listfind 40Search, insert, delete: O(log n) on average. Each level lets you skip over a chunk of items at once, instead of checking them one by one. Space: O(n), since higher levels only add a smaller number of extra shortcut pointers.
L0L1L2L3HHHH101020304050606070707080808080

Search for 40: start at the head on the top express lane (level 3).

40
Target
0
Hops
1/9
Step
0.0s
Time
Cursor / hopWould overshootLane linkIdle node

Not sure this is the right topic? See the learning paths → or where this leads →