Skip List

Skip List is a search data structure invented by William Pugh, supporting fast search, insertion, and deletion of data.

The expected space complexity of a skip list is \(O(n)\), and the expected time complexity for search, insertion, and deletion operations is \(O(\log n)\).

Basic Idea

As the name suggests, a skip list is a data structure similar to a linked list. More precisely, a skip list is an improvement over an ordered linked list.

For convenience, all subsequent ordered linked lists are assumed to be sorted in ascending order.

The search operation in an ordered linked list starts from the head and compares nodes one by one until the current node's value is greater than or equal to the target node's value. Clearly, the complexity of this operation is \(O(n)\).

A skip list introduces the concept of layers on top of an ordered linked list. First, each layer of a skip list is an ordered linked list, with the bottom layer being the original ordered linked list. Each node at layer \(i\) has a probability \(p\) of appearing at layer \(i+1\), where \(p\) is a constant.

Let \(L(n)\) denote the layer in a skip list with \(n\) nodes that is expected to contain \(\frac{1}{p}\) elements. It follows that \(L(n) = \log_{\frac{1}{p}}n\).

Searching in a skip list starts from layer \(L(n)\), horizontally comparing nodes until the next node is greater than or equal to the target node, then moving down to the next layer. This process repeats until reaching the first layer and no further operations can be performed. At this point, if the next node is the target node, the search is successful; otherwise, the element does not exist. This approach skips unnecessary comparisons, making skip list searches faster than those in ordered linked lists. It can be proven that the average complexity of skip list search is \(O(\log n)\).

Complexity Proof

Space Complexity

For a single node, the probability that its highest layer is \(i\) is \(p^{i-1}(1 - p)\). Therefore, the expected number of layers in a skip list is \(\sum_{i\ge 1} ip^{i - 1}(1-p) = \frac{1}{1 - p}\). Since \(p\) is a constant, the expected space complexity of a skip list is \(O(n)\).

In the worst case, each layer's ordered linked list is identical to the original ordered linked list, meaning the worst-case space complexity of a skip list is \(O(n \log n)\).

Time Complexity

Analyzing the search path from back to front, this process can be divided into two parts: climbing from the bottom layer to layer \(L(n)\) and subsequent operations. During analysis, it is assumed that a node's specific information is unknown before it is accessed.

Suppose we are currently at a node \(x\) at layer \(i\). We do not know the maximum layer of \(x\) or the maximum layer of nodes to the left of \(x\), only that \(x\)'s maximum layer is at least \(i\). If \(x\)'s maximum layer is greater than \(i\), the next step should be to move upward, with probability \(p\); if \(x\)'s maximum layer equals \(i\), the next step should be to move left, with probability \(1-p\).

Let \(C(i)\) be the expected cost of climbing \(i\) layers in an infinitely long skip list. Then:

\[ \begin{aligned} C(0) & = 0 \\ C(i) & = (1-p)(1+C(i)) + p(1+C(i-1)) \end{aligned} \]

Solving gives \(C(i)=\frac{i}{p}\).

Thus, in a skip list of length \(n\), the expected number of steps to climb from the bottom layer to layer \(L(n)\) is bounded above by \(\frac{L(n) - 1}{p}\).

Now, we only need to analyze how many more steps are required after reaching layer \(L(n)\). It is clear that after reaching layer \(L(n)\), the number of leftward steps will not exceed the total number of nodes at layer \(L(n)\) and above, whose expected value is \(\frac{1}{p}\). Therefore, the expected number of leftward steps after reaching layer \(L(n)\) is bounded above by \(\frac{1}{p}\). Similarly, the expected number of upward steps after reaching layer \(L(n)\) is bounded above by \(\frac{1}{p}\).

Thus, the expected number of search steps in a skip list query is \(\frac{L(n) - 1}{p} + \frac{2}{p}\). Since \(L(n)=\log_{\frac{1}{p}}n\), the expected time complexity of a skip list query is \(O(\log n)\).

In the worst case, each layer's ordered linked list is identical to the original ordered linked list, making the search process equivalent to querying the highest layer's ordered linked list. Therefore, the worst-case time complexity of a skip list query operation is \(O(n)\).

Insertion and deletion operations involve performing a search, recording nodes that need modification along the way, and finally applying the modifications. Since at most one node per layer needs modification and the expected number of layers in a skip list is \(\log_{\frac{1}{p}}n\), the expected time complexity of insertion and deletion is also \(O(\log n)\).

Implementation

Obtaining the Maximum Layer of a Node

Simulate adding layers with probability \(p\), then take the minimum with the upper limit.

int randomLevel() {
  int lv = 1;
  // MAXL = 32, S = 0xFFFF, PS = S * P, P = 1 / 4
  while ((rand() & S) < PS) ++lv;
  return min(MAXL, lv);
}

Search

Check if a node with key key exists in the skip list. Sentinel nodes can be used to reduce boundary condition discussions.

V& find(const K& key) {
  SkipListNode<K, V>* p = head;

  // Find the last node in this layer with key less than `key`, then move down
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
  }
  // Currently at less than, so need to move one step forward
  p = p->forward[0];

  // Successfully found the node
  if (p->key == key) return p->value;

  // Node does not exist, return INVALID
  return tail->value;
}

Insertion

Insert a node (key, value). The insertion process involves performing a search, recording which nodes the new node should be inserted after, and then performing the insertion. The last node with key less than key in each layer is the node that needs modification.

void insert(const K &key, const V &value) {
  // Record nodes that need modification
  SkipListNode<K, V> *update[MAXL + 1];

  SkipListNode<K, V> *p = head;
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
    // Node to modify at layer i is p
    update[i] = p;
  }
  p = p->forward[0];

  // If exists, update value
  if (p->key == key) {
    p->value = value;
    return;
  }

  // Get the maximum layer for the new node
  int lv = randomLevel();
  if (lv > level) {
    lv = ++level;
    update[lv] = head;
  }

  // Create new node
  SkipListNode<K, V> *newNode = new SkipListNode<K, V>(key, value, lv);
  // Insert new node at layers 0~lv
  for (int i = lv; i >= 0; --i) {
    p = update[i];
    newNode->forward[i] = p->forward[i];
    p->forward[i] = newNode;
  }

  ++length;
}

Deletion

Delete the node with key key. The deletion process involves performing a search, recording which nodes the node to delete is after, and then performing the deletion. The last node with key less than key in each layer is the node that needs modification.

bool erase(const K &key) {
  // Record nodes that need modification
  SkipListNode<K, V> *update[MAXL + 1];

  SkipListNode<K, V> *p = head;
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
    // Node to modify at layer i is p
    update[i] = p;
  }
  p = p->forward[0];

  // Node does not exist
  if (p->key != key) return false;

  // Delete from bottom layer upward
  for (int i = 0; i <= level; ++i) {
    // If p is not in this layer, deletion is complete
    if (update[i]->forward[i] != p) {
      break;
    }
    // Disconnect p
    update[i]->forward[i] = p->forward[i];
  }

  // Free memory
  delete p;

  // Deletion may reduce the maximum level
  while (level > 0 && head->forward[level] == tail) --level;

  // Decrease skip list length
  --length;
  return true;
}

Complete Code

The following code implements a map using a skip list. It is for reference only and has not been rigorously tested.

Reference Code

#include <cassert>
#include <climits>
#include <ctime>
#include <iostream>
#include <map>
using namespace std;

template <typename K, typename V>
struct SkipListNode {
  int level;
  K key;
  V value;
  SkipListNode **forward;

  SkipListNode() {}

  SkipListNode(K k, V v, int l, SkipListNode *nxt = NULL) {
    key = k;
    value = v;
    level = l;
    forward = new SkipListNode *[l + 1];
    for (int i = 0; i <= l; ++i) forward[i] = nxt;
  }

  ~SkipListNode() {
    if (forward != NULL) delete[] forward;
  }
};

template <typename K, typename V>
struct SkipList {
  static constexpr int MAXL = 32;
  static constexpr int P = 4;
  static constexpr int S = 0xFFFF;
  static constexpr int PS = S / P;
  static constexpr int INVALID = INT_MAX;

  SkipListNode<K, V> *head, *tail;
  int length;
  int level;

  SkipList() {
    srand(time(nullptr));

    level = length = 0;
    tail = new SkipListNode<K, V>(INVALID, 0, 0);
    head = new SkipListNode<K, V>(INVALID, 0, MAXL, tail);
  }

  ~SkipList() {
    delete head;
    delete tail;
  }

  int randomLevel() {
    int lv = 1;
    while ((rand() & S) < PS) ++lv;
    return MAXL > lv ? lv : MAXL;
  }

  void insert(const K &key, const V &value) {
    SkipListNode<K, V> *update[MAXL + 1];

    SkipListNode<K, V> *p = head;
    for (int i = level; i >= 0; --i) {
      while (p->forward[i]->key < key) {
        p = p->forward[i];
      }
      update[i] = p;
    }
    p = p->forward[0];

    if (p->key == key) {
      p->value = value;
      return;
    }

    int lv = randomLevel();
    if (lv > level) {
      lv = ++level;
      update[lv] = head;
    }

    SkipListNode<K, V> *newNode = new SkipListNode<K, V>(key, value, lv);
    for (int i = lv; i >= 0; --i) {
      p = update[i];
      newNode->forward[i] = p->forward[i];
      p->forward[i] = newNode;
    }

    ++length;
  }

  bool erase(const K &key) {
    SkipListNode<K, V> *update[MAXL + 1];
    SkipListNode<K, V> *p = head;

    for (int i = level; i >= 0; --i) {
      while (p->forward[i]->key < key) {
        p = p->forward[i];
      }
      update[i] = p;
    }
    p = p->forward[0];

    if (p->key != key) return false;

    for (int i = 0; i <= level; ++i) {
      if (update[i]->forward[i] != p) {
        break;
      }
      update[i]->forward[i] = p->forward[i];
    }

    delete p;

    while (level > 0 && head->forward[level] == tail) --level;
    --length;
    return true;
  }

  V &operator[](const K &key) {
    V v = find(key);
    if (v == tail->value) insert(key, 0);
    return find(key);
  }

  V &find(const K &key) {
    SkipListNode<K, V> *p = head;
    for (int i = level; i >= 0; --i) {
      while (p->forward[i]->key < key) {
        p = p->forward[i];
      }
    }
    p = p->forward[0];
    if (p->key == key) return p->value;
    return tail->value;
  }

  bool count(const K &key) { return find(key) != tail->value; }
};

int main() {
  SkipList<int, int> L;
  map<int, int> M;

  clock_t s = clock();

  for (int i = 0; i < 1e5; ++i) {
    int key = rand(), value = rand();
    L[key] = value;
    M[key] = value;
  }

  for (int i = 0; i < 1e5; ++i) {
    int key = rand();
    if (i & 1) {
      L.erase(key);
      M.erase(key);
    } else {
      int r1 = L.count(key) ? L[key] : 0;
      int r2 = M.count(key) ? M[key] : 0;
      assert(r1 == r2);
    }
  }

  clock_t e = clock();
  cout << "Time elapsed: " << (double)(e - s) / CLOCKS_PER_SEC << endl;
  // about 0.2s

  return 0;
}

Random Access Optimization for Skip Lists

Accessing the \(k\)-th node in a skip list is equivalent to accessing the \(k\)-th node in the original ordered linked list. Clearly, this operation has a time complexity of \(O(n)\), which is not efficient enough.

Random access optimization for skip lists involves maintaining the length of each forward pointer. Suppose \(A\) and \(B\) are nodes in the skip list, where \(A\) is the \(a\)-th node and \(B\) is the \(b\)-th node \((a < b)\). If at a certain layer, \(A\)'s forward pointer points to \(B\), then the length of this forward pointer is \(b - a\).

Now, to access the \(k\)-th node in the skip list, start from the top layer and traverse horizontally until the current node's position plus the length of its forward pointer at that layer is greater than or equal to \(k\), then move down to the next layer. Repeat this process until reaching the first layer and no further operations can be performed. At this point, the current node is the \(k\)-th node in the skip list.

This allows fast access to the \(k\)-th element of the skip list. It can be proven that the time complexity of this operation is \(O(\log n)\).

References

1. Skip Lists: A Probabilistic Alternative to Balanced Trees
2. Skip List
3. A Skip List Cookbook

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用