What is a skip list data structure?

A skip list is an advanced data structure that incorporates the principles of a linked list, but with the addition of multiple layers that allow it to skip over elements from the previous layer. As a type of randomized data structure, skip lists offer efficient average-case performance for key operations such as insertion, search, and deletion. Before we explore these operations in detail, let’s take a closer look at the structure of a skip list.

Key takeaways:

• A skip list is a probabilistic data structure that allows for fast search, insertion, and deletion operations, utilizing multiple layers of linked lists.

• The insertion process involves finding the appropriate level for a new element and ensuring the list remains balanced by adjusting pointers accordingly.

• Skip lists enable efficient searching through a multi-level structure, allowing average-case time complexity of $O(\log n)$ for search operations.

• Deletion requires locating the target element and adjusting pointers to maintain the skip list's structure.

• Skip lists offer average time complexities of $O(\log n)$ for insertion, search, and deletion, which makes them competitive with other data structures like balanced trees.

In this skip list Answer, we will discuss the following functions in the skip list data structure:

• Insert a key

• Search for a key

• Delete a key

Skip list insertion operation

Now consider a case in which we want to insert $Key = 5$ in the above-illustrated skip list. We will start from the top layer, which is Layer 2. We will compare the key to the right of the current node. We will move down if the key is greater than or equal to the right of the current node value. Otherwise, we will move forward. If we reach layer 0, we will place the key instead of moving down and set the pointers accordingly.

When the key is inserted, we need to decide whether this key needs to be promoted to the upper layers. This criterion is determined based on a coin toss; we will promote the key to the upper layer if we encounter a head.

We will stop promoting the key only if we encounter a tail during the coin toss. Below is a diagram showing the insertion $Key = 5$ in the skip list.

So, $5$ will be placed between $2$ and $8$. To promote $5$ , we will perform a coin toss as illustrated below. We keep promoting $5$ to the next layer until the coin toss gives us a tail.

Skip list search operation

Follow the below-mentioned steps if you want to delete a key in the skip list.

1. Start from the top layer of the skip list.

2. Move forward until you find a node whose value is greater than the key. In case it is small, move down.

3. If the node’s value equals the key, return the node.

4. If not found, then repeat steps 2–3.

Skip list deletion operation

We'll apply the same steps in searching for a key. The only difference is that we'll keep track of the key found at the layer because we have to delete the key at every layer. We will delete the key with the value $20$ in the diagram below.

The resulting skip list is shown below after deleting the node with the value $20$.

Having discussed the insertion, deletion, and search operations in this skip list tutorial, if you’re looking for a programming implementation of skip lists, check out our Answer on Implementation of skip list in C++. It provides code for the skip list insertion operation, skip list deletion operation, and skip list search operation.

Time complexity analysis

Skip lists, as a type of randomized data structure, are designed to provide efficient average-case performance for insertion, search, and deletion operations. Here’s a breakdown of the time complexity for each operation:

• Insertion: The average time complexity for inserting an element into a skip list is $O(\log n)$. This is due to the logarithmic levels that allow the algorithm to skip over many elements in the list.

• Search: Similarly, the average time complexity for searching for an element is $O(\log n)$.

• Deletion: The average time complexity for deleting an element is also $O(\log n)$. This involves finding the element first (which takes $O(\log n)$) and then adjusting the pointers to remove it from the list.

In the worst case, all these operations can degrade to $O(n)$ if the list is unbalanced, but with proper maintenance of the skip list’s levels, the average-case performance remains efficient.

Conclusion

Skip lists are a powerful alternative to balanced trees that offer simplicity and flexibility with comparable performance in search, insertion, and deletion operations. Their probabilistic nature allows them to maintain efficiency across various use cases. If you want to learn more about skip list data structure, check out the "Data Structures with Generic Types in Python" course!