Skip List
· One min read
A skip list is essentially a linked list that allows for binary search. It achieves this by adding extra nodes that enable you to "skip" parts of the linked list. Given a random number generator to create these extra nodes, a skip list has O(log n) complexity for search, insert, and delete operations.
Use Cases
- LevelDB MemTable
- Redis Sorted Set
- Lucene Inverted Index
![[object Object]](/dog.jpg)