Skip List Data Structure
Skip list is an efficient data structure to store sorted elements. Skip list augments the normal linked list with more metadata to provide better time complexity. Like balanced trees, skip list provides O(logN) time complexity for search/insert/delete. In this post, we review the skip list data structure and see how we can optimize its operation with finger search. We present a simple C++ implementation and provide some experimental results with this implementation. We compare skip list with balanced search trees, and see how for concurrent programs skip list is the clear winner.