Skip list
- Date
- 1989 · confidence high
- Place
- College Park, Maryland, United States
- Credited to
- William Pugh
- Field
- Knowledge & symbols
What it is
Computer scientist William Pugh introduced the skip list in 1989 at the University of Maryland, a probabilistic data structure combining several hierarchical linked lists to achieve average logarithmic-time search and insertion, as a simpler alternative to balanced trees.
What it led to
- Implementation in databases such as Redis and LevelDB
- Practical alternative to AVL and red-black trees
- Lock-free concurrent data structures