AIOJ

A skip list is a search data structure invented by William Pugh that supports fast search, insertion, and deletion.

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

Basic Idea

As its name suggests, a skip list is a data structure similar to a linked list. More precisely, a skip list is an enhancement of an ordered linked list.

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

Searching an ordered linked list means comparing values one by one from the head until the current node's value is greater than or equal to the target value. Clearly, this operation has complexity $O(n)$ .

A skip list introduces the concept of levels on top of an ordered linked list. First, every level of a skip list is an ordered linked list; in particular, the bottom level is the original ordered linked list. Each node at level $i$ appears with probability $p$ at level $i+1$ , where $p$ is a constant.

In a skip list with $n$ nodes, let the level expected to contain $\frac{1}{p}$ elements be level $L(n)$ . It is easy to obtain $L(n) = \log_{\frac{1}{p}}n$ .

Searching a skip list starts at level $L(n)$ and compares nodes horizontally one by one until the next node of the current node is greater than or equal to the target, then moves down to the next level. This process is repeated until reaching the first level and being unable to continue. If the next node is the target, the search succeeds; otherwise, the element does not exist. In this way, the search skips unnecessary comparisons, so it is faster than searching an ordered linked list. It can be proved that the average complexity of skip-list search is $O(\log n)$ .

Complexity Analysis

Space Complexity

For a node, the probability that its highest level is $i$ is $p^{i-1}(1 - p)$ . Thus, the expected number of levels 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, every ordered linked list at every level is identical to the original ordered linked list, so the worst-case space complexity of a skip list is $O(n \log n)$ .

Time Complexity

Analyze the search path backwards. This process can be divided into two parts: climbing from the bottom level to level $L(n)$ , and the subsequent operations. In the analysis, assume that the specific information of a node is unknown until it is visited.

Suppose we are currently at a level- $i$ node $x$ . We do not know the maximum level of $x$ or the maximum level of the node to the left of $x$ ; we only know that the maximum level of $x$ is at least $i$ . If the maximum level of $x$ is greater than $i$ , the next step should go upward, which has probability $p$ ; if the maximum level of $x$ equals $i$ , the next step should go left, which has probability $1-p$ .

Let $C(i)$ be the expected cost of climbing $i$ levels 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}$ .

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

It remains to analyze how many more steps are needed after reaching level $L(n)$ . Clearly, the number of steps taken to the left after reaching level $L(n)$ is no greater than the total number of nodes at level $L(n)$ and above, whose expected total is $\frac{1}{p}$ . Thus, the expected number of leftward steps after reaching level $L(n)$ is bounded above by $\frac{1}{p}$ . Similarly, the expected number of upward steps after reaching level $L(n)$ is bounded above by $\frac{1}{p}$ .

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

In the worst case, every ordered linked list at every level is identical to the original ordered linked list. The search is then equivalent to searching the ordered linked list at the highest level, so the worst-case time complexity of skip-list search is $O(n)$ .

Insertion and deletion are each a search followed by a modification: record the nodes that need to be changed during the search, then complete the modification. At most one node needs to be changed at each level. Since the expected number of levels in a skip list is $\log_{\frac{1}{p}}n$ , the expected time complexity of insertion and modification is also $O(\log n)$ .

Implementation

Obtaining the Maximum Level of a Node

Simulate adding one level with probability $p$ , then take the minimum with the upper bound.

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

Search whether the skip list contains a node with key key. In a concrete implementation, two sentinel nodes can be used to reduce the number of boundary cases that need discussion.

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

  // Find the last node at this level whose key is less than key, then move to the next level
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
  }
  // The current key is smaller, so move forward one more step
  p = p->forward[0];

  // Node found successfully
  if (p->key == key) return p->value;

  // The node does not exist; return INVALID
  return tail->value;
}

Insertion

Insert the node (key, value). The insertion process first performs a search, recording the nodes after which the new node should be inserted, and then performs the insertion. At each level, the last node whose key is less than key is the node that needs to be modified.

void insert(const K &key, const V &value) {
  // Record the nodes that need to be modified
  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];
    }
    // The node to modify at level i is p
    update[i] = p;
  }
  p = p->forward[0];

  // Modify it if it already exists
  if (p->key == key) {
    p->value = value;
    return;
  }

  // Obtain the new node's maximum level
  int lv = randomLevel();
  if (lv > level) {
    lv = ++level;
    update[lv] = head;
  }

  // Create the new node
  SkipListNode<K, V> *newNode = new SkipListNode<K, V>(key, value, lv);
  // Insert the new node at levels 0 through 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 first performs a search, recording the nodes after which the node to be deleted occurs, and then performs the deletion. At each level, the last node whose key is less than key is the node that needs to be modified.

bool erase(const K &key) {
  // Record the nodes that need to be modified
  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];
    }
    // The node to modify at level i is p
    update[i] = p;
  }
  p = p->forward[0];

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

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

  // Reclaim the memory
  delete p;

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

  // Skip-list length
  --length;
  return true;
}

Complete Code

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

Reference implementation

#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 of a skip list is equivalent to accessing the $k$ -th node of the original ordered linked list, and clearly has time complexity $O(n)$ , which is not sufficiently efficient.

The random-access optimization for a skip list maintains, for each forward pointer, the length of that forward pointer as well. Suppose $A$ and $B$ are both nodes in a skip list, where $A$ is the $a$ -th node and $B$ is the $b$ -th node of the skip list $(a < b)$ , and in some level of the skip list the forward pointer of $A$ points to $B$ . The length of this forward pointer is $b - a$ .

To access the $k$ -th node of a skip list, start at the top level and traverse that level horizontally until the current node's position plus the length of its forward pointer at that level is greater than or equal to $k$ , then move down to the next level. Repeat this process until reaching the first level and being unable to continue. The current node is then the $k$ -th node of the skip list.

This makes it possible to access the $k$ -th element of a skip list quickly. It can be proved that the time complexity of this operation is $O(\log n)$ .

Skip List