Skip List

August 8, 2014
Author:Eric
Source:http://blog.wjin.org/posts/skiplist.html
Declaration: this work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Creative Commons License

Introduction

Skip List is a data structure that allows fast search within an ordered sequence of elements.

Fast search is made possible by maintaining a linked hierarchy of subsequences, each skipping over fewer elements. The elements that are skipped over may be chosen probabilistically.

Here is an overview of this data structure:

img

And this gif pic is pretty useful to understand its implementation:

img

Note: both pics are from wiki, see reference.

Complexity

You may have known about AVL tree and Red-Black tree, both get O(log n) in worst case. However, it may be hard to implement them in a short time, especially for AVL tree.

Now, you have an another choice, that is Skip List, it works well in practice. And the most important is that it is easy to implement. See my code below.

And in Redis source code, it uses skip list in its implementation of ordered set.

Name Average Worst case
Space O(n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Find O(log n) O(n)

Code Practice

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// simple skiplist implementation
// 1) do not consider duplicate data
// 2) no backward pointer in the node

class SkipList
{
private:
    struct skiplistNode {
        int data; // node's data
        vector<skiplistNode*> level; // level array

        skiplistNode(int d, int l) : data(d), level(l)
        {
        }
    };

    int m_maxlevel; // max level of skip list
    int m_curlevel; // current level of skip list
    int m_len; // number of nodes
    const double m_prob; // probability

    skiplistNode head; // dumb head

    // get random level for a node
    int RandomLevel()
    {
        int level = 1;
        // m_prob probability to reach to upper level
        while ((random() & 0xFFFF) < (m_prob * 0xFFFF))
            level += 1;

        return (level < m_maxlevel) ? level : m_maxlevel;
    }

public:

    SkipList(const int ml = 32, const double p = 0.25) :
        m_maxlevel(ml), m_prob(p), head(INT_MIN, m_maxlevel)
    {
        m_curlevel = 1; // only one level when initialization
        m_len = 0;
    }

    bool Insert(int data)
    {
        // Considering a single linked list, when inserting
        // an element, we need to get the previous pointer

        // As for skiplist, each level is a list, so we need
        // to keep a previous pointer for each level

        vector<skiplistNode*> prev(m_maxlevel);

        // traverse each level to get prev array
        skiplistNode *x = &head;
        for (int i = m_curlevel - 1; i >= 0; i--) {
            // minus i : move towards bottom
            // forward x : move towards right
            while (x->level[i] && x->level[i]->data < data) {
                x = x->level[i];
            }
            prev[i] = x; // update current level's previous pointer
        }

        // duplicate data
        if (x->level[0] && x->level[0]->data == data) return false;

        int level = RandomLevel();
        // increase skiplist's level
        if (level > m_curlevel) {
            for (int i = m_curlevel; i < level; i++) {
                prev[i] = &head; // update prev array
            }
            m_curlevel = level; // update level
        }

        // insert new node
        x = new skiplistNode(data, level);
        if (x == nullptr) return false; // no memory
        for (int i = 0; i < level; i++) {
            // insert x after pointer prev[i]
            x->level[i] = prev[i]->level[i];
            prev[i]->level[i] = x;
        }

        m_len++;
        return true;
    }

    bool Delete(int data)
    {
        // again, we need to keep previous pointer as
        // single linked list delete operation
        vector<skiplistNode*> prev(m_maxlevel);

        // traverse each level to get prev array
        skiplistNode *x = &head;
        for (int i = m_curlevel - 1; i >= 0; i--) {
            while (x->level[i] && x->level[i]->data < data) {
                x = x->level[i];
            }

            prev[i] = x; // update current level's previous pointer
        }

        x = x->level[0];
        if (x == nullptr || x->data != data) return false; // not exist

        // delete
        for (int i = 0; i < m_curlevel; i++) {
            if (prev[i]->level[i] == x) {
                prev[i]->level[i] = x->level[i]; // delete node
            }
        }
        delete x;
        x = nullptr;

        while(m_curlevel > 1 && head.level[m_curlevel - 1] == NULL)
            m_curlevel--; // delete null list on the top

        m_len--; // update length
        return true;
    }

    bool Find(int data)
    {
        skiplistNode *x = &head;
        for (int i = m_curlevel - 1; i >= 0; i--) {
            while (x->level[i] && x->level[i]->data < data) {
                x = x->level[i];
            }

            if (x->level[i] && x->level[i]->data == data) return true;
        }
        return false;
    }
};

struct Test {
    void orderedTest()
    {
        SkipList sl;

        cout << "*************Ordered Test*************" << endl;

        cout << "Insert Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            cout << "Insert: " << i << "  Result: " << sl.Insert(i);
            cout << endl;
        }

        cout << "Find Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            cout << "Find: " << i << "  Result: " << sl.Find(i);
            cout << endl;
        }

        cout << "Delete Node: 50  ";
        cout << "Reseult: " << sl.Delete(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;

        cout << "Insert Node : 50  ";
        cout << "Result: " << sl.Insert(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;
    }

    void randomTest()
    {
        SkipList sl;

        cout << "*************Random Test*************" << endl;

        cout << "Insert Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            int r = random() % 20;
            cout << "Insert: " << r << "  Result: " << sl.Insert(r);
            cout << endl;
        }

        cout << "Find Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            int r = random() % 20;
            cout << "Find: " << r << "  Result: " << sl.Find(r);
            cout << endl;
        }

        cout << "Delete Node: 50  ";
        cout << "Reseult: " << sl.Delete(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;

        cout << "Insert Node : 50  ";
        cout << "Result: " << sl.Insert(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;
    }
};

int main(int argc, const char *argv[])
{
    Test t;

    srand(time(nullptr));

    t.orderedTest();
    t.randomTest();

    return 0;
}

Reference