Skip List

Skip List

A Skip List is a data structure based on parallel linked lists. It achieves fast search, insertion, and deletion operations with a time complexity of O(log n) by adding multi-level indexes. The Skip List can be seen as an alternative to binary search trees, offering relatively simple implementation and stable performance.

I. Basic Concepts of Skip List

Imagine a sorted linked list where searching requires traversal from head to tail with O(n) time complexity. The core idea of a Skip List is "trading space for time": it accelerates search by establishing multi-level indexes (i.e., additional sorted linked lists), where each level skips a portion of nodes.

II. Structure of Skip List

  1. Node Structure: Each node contains a value (key) and multiple pointers to subsequent nodes (often called a "forward" pointer array).
  2. Level: A Skip List has multiple levels. The bottom level (Level 0) is a sorted linked list containing all elements.
  3. Index Levels: From bottom to top, each index level is a subset of the level below it, with the node spacing gradually increasing.

III. Search Operation Process

Take searching for the value "23" in a Skip List as an example (assuming the list contains 1, 3, 7, 12, 19, 23, 26, 30, 35, 39):

  1. Start from the highest index level: Assume the highest level is Level 3.
  2. Traverse right: Move right within the current level, comparing node values with the target value.
    • If the next node's value ≤ the target value, continue moving right.
    • If the next node's value > the target value or is NULL, descend one level.
  3. Descend level by level: Repeat step 2 until reaching the bottom level (Level 0).
  4. Final check: If the node value found at the bottom level equals the target value, the search succeeds.

Example search path:

  • Level 3: Start from the head node, find the next node value (19) < 23, move right.
  • Level 3: The next node value (35) > 23, descend to Level 2.
  • Level 2: Start from 19, the next node value (35) > 23, descend to Level 1.
  • Level 1: Start from 19, the next node value (26) > 23, descend to Level 0.
  • Level 0: Start from 19, the next node value (23) = 23, search successful.

IV. Insertion Operation Process

The insertion operation involves two steps: finding the insertion position and determining the level of the new node.

  1. Find predecessor nodes:

    • Start from the highest level, record the last node less than the insertion value (predecessor node) at each level.
    • The pointers of these predecessor nodes need to be updated to point to the new node.

  2. Randomly determine level:

    • Use a random method (like coin tossing) to decide the new node's level.
    • Starting from Level 1, there's a 50% chance to increase the level each time, up to a maximum level limit.
    • This randomness ensures the balance of the Skip List.

  3. Update pointers:

    • From Level 0 to the new node's highest level, update the predecessor nodes' pointers.
    • Set the new node's pointers to point to the successor nodes of the original predecessor nodes.

V. Deletion Operation Process

The deletion operation is similar to insertion:

  1. Find the target node: Simultaneously record the last node less than the target value at each level.
  2. Update pointers: Update pointers at each level that point to the target node to point to the target node's successor.
  3. Free memory: If the target node is found, release its allocated memory.

VI. Complexity Analysis

  1. Space Complexity: O(n). The approximate number of index nodes is n/2 + n/4 + n/8 + ... ≈ n.
  2. Time Complexity:
    • Search: O(log n)
    • Insertion: O(log n) (includes search time)
    • Deletion: O(log n) (includes search time)

VII. Advantages of Skip List

  1. Implementation is simpler compared to balanced binary trees like Red-Black Trees.
  2. Supports range queries (after finding the starting point, traverse the bottom-level linked list sequentially).
  3. Easier to implement thread safety in concurrent environments.

Skip Lists are widely used in various systems. For example, Redis's Sorted Sets and LevelDB's MemTable use Skip Lists as their underlying data structure.