Skip List (M3.1)

•  A skip list is a probabilistic data structure. 
• The skip list is used to store a sorted list of elements or data with a linked list. 
• It allows the process of the elements or data to view efficiently. 
• In one single step, it skips several elements of the entire list, which is why it is known as a skip list.
• The skip list is an extended version of the linked list. 
• It allows the user to search, remove, and insert the element very quickly. 
• It consists of a base list that includes a set of elements which maintains the link hierarchy of the subsequent elements.

A skip list starts with a basic, ordered, linked list. This list is sorted, but we can't do a binary search on it because it is a linked list and we cannot index into it.

Then, another layer is added on top of the bottom list. This new layer will include any given element from the previous layer with probability $p\mathrm{}$ This probability can vary, but oftentimes $\frac12$ is used. Additionally, the first node in the linked list is often always kept, as a header for the new layer.

Properties

• It has a height of $h$ which is the number of linked lists in it. It has a number of distinct elements, $n.$ And it has a probability $p,$ which is usually $\frac12.$
• $$The highest element (one that appears in the most lists) will appear in $\log_\frac{1}{p}(n)$ lists, on average, This, if we use $p = \frac12$, there are $\log_2(n)$ lists. This is the average value of $h$. Another way of saying "Every element in a linked list is in the linked list below it" is "Every element in level $S_{i+1}$ exists in level $S_i.$"
• Each element in the skip list has four pointers. It points to the node to its left, its right, its top, and its bottom. These quad-nodes will allow us to efficiently search through the skip list.

Skip List Basic Operations

There are the following types of operations in the skip list.

• Insertion operation: It is used to add a new node to a particular location in a specific situation.
• Deletion operation: It is used to delete a node in a specific situation.
• Search Operation: The search operation is used to search a particular node in a skip list.

Advantages of the Skip list

1. If you want to insert a new node in the skip list, then it will insert the node very fast because there are no rotations in the skip list.
2. The skip list is simple to implement as compared to the hash table and the binary search tree.
3. It is very simple to find a node in the list because it stores the nodes in sorted form.
4. The skip list algorithm can be modified very easily in a more specific structure, such as indexable skip lists, trees, or priority queues.
5. The skip list is a robust and reliable list.

Disadvantages of the Skip list

1. It requires more memory than the balanced tree.
2. Reverse searching is not allowed.
3. The skip list searches the node much slower than the linked list.

Applications of the Skip list

1. It is used in distributed applications, and it represents the pointers and system in the distributed applications.
2. It is used to implement a dynamic elastic concurrent queue with low lock contention.
3. It is also used with the QMap template class.
4. The indexing of the skip list is used in running median problems.
5. The skip list is used for the delta-encoding posting in the Lucene search.

---