# Skip List

August 8, 2014
Author：Eric
Source：http://blog.wjin.org/posts/skiplist.html

# 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:

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

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

// 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_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
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
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)
{
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;
}
``````