~kjiwa

Skip List

June 2011

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees. (Pugh)

I based my implementation on the original paper, which you can download here. Java was my language of choice.

The source code is released under the MIT license and is also available on GitHub at github.com/kjiwa/java-skip-list.

SkipList.java
/*
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

import java.util.Random;

public class SkipList<T extends Comparable<T>, U> {
  private class Node {
    public T key;
    public U value;
    public long level;
    public Node next;
    public Node down;

    public Node(T key, U value, long level, Node next, Node down) {
      this.key = key;
      this.value = value;
      this.level = level;
      this.next = next;
      this.down = down;
    }
  }

  private Node _head;
  private Random _random;
  private long _size;
  private double _p;

  private long _level() {
    long level = 0;
    while (level <= _size && _random.nextDouble() < _p) {
      level++;
    }

    return level;
  }

  public SkipList() {
    _head = new Node(null, null, 0, null, null);
    _random = new Random();
    _size = 0;
    _p = 0.5;
  }

  public void add(T key, U value) {
    long level = _level();
    if (level > _head.level) {
      _head = new Node(null, null, level, null, _head);
    }

    Node cur = _head;
    Node last = null;

    while (cur != null) {
      if (cur.next == null || cur.next.key.compareTo(key) > 0) {
        if (level >= cur.level) {
          Node n = new Node(key, value, cur.level, cur.next, null);
          if (last != null) {
            last.down = n;
          }

          cur.next = n;
          last = n;
        }

        cur = cur.down;
        continue;
      } else if (cur.next.key.equals(key)) {
        cur.next.value = value;
        return;
      }

      cur = cur.next;
    }

    _size++;
  }

  public boolean containsKey(T key) {
    return get(key) != null;
  }

  public U remove(T key) {
    U value = null;

    Node cur = _head;
    while (cur != null) {
      if (cur.next == null || cur.next.key.compareTo(key) >= 0) {
        if (cur.next != null && cur.next.key.equals(key)) {
          value = cur.next.value;
          cur.next = cur.next.next;
        }

        cur = cur.down;
        continue;
      }

      cur = cur.next;
    }

    _size--;
    return value;
  }

  public U get(T key) {
    Node cur = _head;
    while (cur != null) {
      if (cur.next == null || cur.next.key.compareTo(key) > 0) {
        cur = cur.down;
        continue;
      } else if (cur.next.key.equals(key)) {
        return cur.next.value;
      }

      cur = cur.next;
    }

    return null;
  }
}