Skip list
A probabilistic data structure which combines features of sorted array and a linked list; the skip list can be used as an alternative to balanced binary search trees. It is implemented as a collection of linked lists where each linked list will progressively contain more and more of the full data set.
| Pros |
Cons |
| Easier to implement than balanced binary search trees |
Non-deterministic performances |
| More flexible for concurrency |
Worst-case performances are worst than balanced BSTs |
|
Uses more space than balanced trees |
|
Similar to linked lists, skip trees can not be easily cached |
