Teachers: Skip List Data Structure

Wednesday, February 18, 2015

Skip List Data Structure

A skip list is a data structure that is used for storing a sorted list of items with a help of hierarchy of linked lists that connect increasingly sparse subsequences of the items. A skip list allows the process of item look up in efficient manner. The skip list data structure skips over many of the items of the full list in one step, that’s why it is known as skip list.

Skip List

Complexity

	Average Case	Worst Case
Space	O(n)	O(nlogn)
Search	O(logn)	O(n)
Insert	O(logn)	O(n)
Delete	O(logn)	O(n)

Structure of Skip List

A skip list is built up of layers. The lowest layer (i.e. bottom layer) is an ordinary ordered linked list. The higher layers are like ‘express lane’ where the nodes are skipped (observe the figure).

Searching Process

When an element is tried to search, the search begins at the head element of the top list. It proceeds horizontally until the current element is greater than or equal to the target. If current element and target are matched, it means they are equal and search gets finished.

If the current element is greater than target, the search goes on and reaches to the end of the linked list, the procedure is repeated after returning to the previous element and the search reaches to the next lower list (vertically).

Implementation Details

1. The elements used for a skip list can contain more than one pointers since they are allowed to participated in more than one list.

2. Insertion and deletion operations are very similar to corresponding linked list operations.

Insertion in Skip List

Applications of Skip List

1. Skip list are used in distributed applications. In distributed systems, the nodes of skip list represents the computer systems and pointers represent network connection.

2. Skip list are used for implementing highly scalable concurrent priority queues with less lock contention (struggle for having a lock on a data item).

Teachers