Updated March 30, 2023
Introduction to Skip list C++
The skip list in C++ is used to store the sorted list of elements with the linked list. The skip list is the version of the linked list. It skips multiple elements of the entire list in a single move, which is why it’s called a skip list. It enables the elements or data to be viewed efficiently.
The skip list enables the user to quickly search, delete, and insert the elements in the list. It is made up of a base list and a collection of elements that keep the relation hierarchy of the subsequent elements intact. Therefore, the worst-case running access, search, insert, and delete complexity of the skip list is O(n) and the average-case running access, search, insert, and delete complexity of the skip list is O(log(n)).
The algorithm for the skip list insert operation is –
skip_Insert( Ls, k)
local u [0...MxLevel + 1]
a = Ls → header
for x = Ls → level down to 0 do.
while a → f[x] → k f[x]
u[i] = a
a = a → f[0]
l = createLevel()
if l > Ls → level then
for x = Ls → level + 1 to l do
u[x] = Ls → header
Ls → level = l
a = createNode(l, k, value)
for x = 0 to level do
a → f[x] = u[x] → f[x]
u[x] → f[x] = aThe algorithm for the skip list search operation is –
Sip_Search (Ls, k)
a = Ls → header
loop invariant: a → key level down to 0 do.
while a → f[i] → key f[i]
a = a → f[0]
if a → key = k then return a → value
else return failThe algorithm for the skip list delete operation is –
Deletion (Ls, k)
local u [0... MxLevel + 1]
a = Ls → header
for x = Ls → level down to 0 do.
while a → f[x] → key f[x]
u[x] = a
a = a → f[0]
if a → key = k then
for x = 0 to Ls → lvl do
if u[x] → f[x] ? a then break
u[x] → f[x] = a → f[x]
free(a)
while Ls → header → f[Ls → lvl] = NIL and Ls → lvl > 0 do
Ls → lvl = Ls → lvl - 1Working of skip list in C++
It used several layers in order to bypass certain nodes. See the sample list below, which has 16 nodes and two layers.
List : [11, 21, 23, 24, 28, 31, 44, 46, 51, 55, 58, 59, 60, 63, 66, 68]
express lane : [11, 31, 58, 68]
normal lane : [11, 21, 23, 24, 28, 31, 44, 46, 51, 55, 58, 59, 60, 63, 66, 68]
The first layer performs as an “express lane,” connecting only the major outer elements, while the second layer performs as a “normal lane” connecting all elements. If we want to find 51, it’ll start at the first node of the “express path” and keep going until it finds a node with a next node that’s greater than 51. It switches to “normal lane” using pointer from this node and linearly check for 51 on “normal lane” once it finds such a node (as 31 is the node in the following example). So it begins at 31 on the “normal lane” and finds for the 51 with the help of linear search.
Examples of skip list in C++
Example of skip list in C++ to insert the elements into the list –
Code:
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
//create node
class Node
{
public:
int k;
Node **forward;
Node(int, int);
};
Node::Node(int k, int lvl)
{
this->k = k;
// for forward allocate memory
forward = new Node*[lvl+1];
// forward fill with null
memset(forward, 0, sizeof(Node*)*(lvl+1));
};
// create Skip list
class Skip_List
{
// skip list maximum level and current level
int MxLVL, lvl;
float P;
// pointer point to header node
Node *header;
public:
Skip_List(int, float);
int randomLvl()
{
float r = (float)rand()/RAND_MAX;
int lvl = 0;
while (r < P && lvl < MxLVL)
{
lvl++;
r = (float)rand()/RAND_MAX;
}
return lvl;
}
Node* createNode(int key, int lvl)
{
Node *n = new Node(key, lvl);
return n;
}
void insert(int k)
{
Node *current = header;
// create a local update array and initialize
Node *update[MxLVL+1];
memset(update, 0, sizeof(Node*)*(MxLVL+1));
for (int i = lvl; i >= 0; i--)
{
while (current->forward[i] != NULL &&
current->forward[i]->k < k)
current = current->forward[i];
update[i] = current;
}
current = current->forward[0];
if (current == NULL || current->k != k)
{
// create a random level for node
int rlevel = randomLvl();
if (rlevel > lvl)
{
for (int i=lvl+1;i<rlevel+1;i++)
update[i] = header;
// Update the list current level
lvl = rlevel;
}
// create new node with random level generated
Node* n = createNode(k, rlevel);
for (int i=0;i<=rlevel;i++)
{
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
cout << "The inserted key is : " << k << "\n";
}
}
void display()
{
cout<<"\n The skip list is : "<<"\n";
for (int i=0;i<=lvl;i++)
{
Node *node = header->forward[i];
cout << "Level : " << i << ": ";
while (node != NULL)
{
cout << node->k<<" ";
node = node->forward[i];
}
cout << "\n";
}
}
};
Skip_List::Skip_List(int MxLVL, float P)
{
this->MxLVL = MxLVL;
this->P = P;
lvl = 0;
// make header node and initialize key with -1
header = new Node(-1, MxLVL);
};
int main()
{
// Seed random number generator
srand((unsigned)time(0));
// create SkipList object with MAXLVL and P
Skip_List l(3, 0.5);
l.insert(10);
l.insert(40);
l.insert(20);
l.insert(19);
l.insert(21);
l.insert(78);
l.insert(47);
l.insert(26);
l.insert(89);
l.insert(26);
l.display();
}An output of the above code is –
As in the above program, the Node class is created to create the node, Skip_List class is created to define the variables and different functions. The skip_List define the randomLvl(), createNode(), insert() and display() functions which are performing the specific task. Finally, the main function is creating the skip_list object, inserting the elements, and display all the elements, as we can see in the above output.
Conclusion
The skip list in C++ is used to sorts the sorted list of elements with the linked list. The skip list allows the user to quickly search, delete, and insert the elements in the list.
Recommended Article
This is a guide to Skip list C++. Here we discuss the Working of skip list in C++ along with the example and output. You may also have a look at the following articles to learn more –
