wisconsin
Skip Lists

Skip Lists

Curated by Last modified: 3 min read

Skip lists are a data structure that allows for fast search, insertion, and deletion operations. They are built on top of linked lists and use multiple levels of linked lists to allow for faster traversal.

Structure of a Skip List

A skip list consists of multiple levels of linked lists, where each level is a subset of the level below it. The bottom level contains all the elements in the list, while each higher level contains a subset of the elements from the level below. The top level is typically much shorter than the bottom level.

Each node in a skip list contains:

  • A value.
  • A pointer to the next node at the same level.
  • Pointers to the nodes at the next level (if applicable).

Operations

Begin at the top-level head sentinel. Inspect the next node: move right while its key is smaller than the target; otherwise move down without passing the target. At the bottom level, test the next node for equality. Save predecessor positions when preparing to insert or remove.

Insertion

To insert a value into a skip list, follow these steps:

  1. Start at the top level and the leftmost node.
  2. Search for the position where the new value should be inserted using the search algorithm.
  3. Create a new node for the value.
  4. Insert the new node at the appropriate position in the bottom level.
  5. Randomly decide whether to promote the new node to higher levels based on a probability (e.g., 50% chance).
  6. If promoted, repeat the insertion process for each higher level until the top level is reached or the random promotion fails.
  7. Update the pointers of the nodes at the same level to include the new node.

Deletion

To delete a value from a skip list, follow these steps:

  1. Start at the top level and the leftmost node.
  2. Search for the value to be deleted using the search algorithm.
  3. If the value is found, remove the node from the bottom level.
  4. Update the pointers of the nodes at the same level to bypass the deleted node.
  5. If the deleted node is at higher levels, repeat the deletion process for each level until the top level is reached or the node is no longer present.
  6. If the node is not found, return an error or indication that the value was not present in the skip list.
  7. If the skip list becomes too sparse, consider removing empty levels to maintain efficiency.

Time Complexity

The average time complexity for search, insertion, and deletion operations in a skip list is O(log n), where n is the number of elements in the skip list. This is due to the multiple levels of linked lists that allow for faster traversal.

Randomization

With independent promotion probability 1/2, expected level sizes decrease geometrically: n, n/2, n/4, and so on. The number of populated levels is logarithmic in expectation. This supports expected O(log n) operations; it does not guarantee perfect balance, and worst-case operations can take O(n).

Connections

Obvious technical and formatting errors repaired.

Linked to this page