Data Modelling & AI Data Structure & Algorithm

Skip List | Set 2 (Insertion)

21 June 2025

0

We have already discussed the idea of Skip list and how they work in Skip List | Set 1 (Introduction). In this article, we will be discussing how to insert an element in Skip list.

Deciding nodes level

Each element in the list is represented by a node, the level of the node is chosen randomly while insertion in the list. Level does not depend on the number of elements in the node. The level for node is decided by the following algorithm –

randomLevel()
lvl := 1
//random() that returns a random value in [0...1)
while random() < p and lvl < MaxLevel do
lvl := lvl + 1
return lvl

MaxLevel is the upper bound on number of levels in the skip list. It can be determined as – $L(N) = log_{p/2}{N}$ . Above algorithm assure that random level will never be greater than MaxLevel. Here p is the fraction of the nodes with level i pointers also having level i+1 pointers and N is the number of nodes in the list.

Node Structure

Each node carries a key and a forward array carrying pointers to nodes of a different level. A level i node carries i forward pointers indexed through 0 to i.

Insertion in Skip List

We will start from the highest level in the list and compare the key of the next node of the current node with the key to be inserted. The basic idea is If –

Key of next node is less than key to be inserted then we keep on moving forward on the same level
Key of next node is greater than the key to be inserted then we store the pointer to current node i at update[i] and move one level down and continue our search.

At the level 0, we will definitely find a position to insert the given key. Following is the pseudo-code for the insertion algorithm –

Insert(list, searchKey)
local update[0...MaxLevel+1]
x := list -> header
for i := list -> level downto 0 do
    while x -> forward[i] -> key  forward[i]
update[i] := x
x := x -> forward[0]
lvl := randomLevel()
if lvl > list -> level then
for i := list -> level + 1 to lvl do
    update[i] := list -> header
    list -> level := lvl
x := makeNode(lvl, searchKey, value)
for i := 0 to level do
    x -> forward[i] := update[i] -> forward[i]
    update[i] -> forward[i] := x

Here update[i] holds the pointer to node at level i from which we moved down to level i-1 and pointer of node left to insertion position at level 0. Consider this example where we want to insert key 17 –

Following is the code for insertion of key in Skip list –

C++

// C++ code for inserting element in skip list
 
#include <bits/stdc++.h>
using namespace std;
 
// Class to implement node
class Node
{
public:
    int key;
 
    // Array to hold pointers to node of different level 
    Node **forward;
    Node(int, int);
};
 
Node::Node(int key, int level)
{
    this->key = key;
 
    // Allocate memory to forward 
    forward = new Node*[level+1];
 
    // Fill forward array with 0(NULL)
    memset(forward, 0, sizeof(Node*)*(level+1));
};
 
// Class for Skip list
class SkipList
{
    // Maximum level for this skip list
    int MAXLVL;
 
    // P is the fraction of the nodes with level 
    // i pointers also having level i+1 pointers
    float P;
 
    // current level of skip list
    int level;
 
    // pointer to header node
    Node *header;
public:
    SkipList(int, float);
    int randomLevel();
    Node* createNode(int, int);
    void insertElement(int);
    void displayList();
};
 
SkipList::SkipList(int MAXLVL, float P)
{
    this->MAXLVL = MAXLVL;
    this->P = P;
    level = 0;
 
    // create header node and initialize key to -1
    header = new Node(-1, MAXLVL);
};
 
// create random level for node
int SkipList::randomLevel()
{
    float r = (float)rand()/RAND_MAX;
    int lvl = 0;
    while (r < P && lvl < MAXLVL)
    {
        lvl++;
        r = (float)rand()/RAND_MAX;
    }
    return lvl;
};
 
// create new node
Node* SkipList::createNode(int key, int level)
{
    Node *n = new Node(key, level);
    return n;
};
 
// Insert given key in skip list
void SkipList::insertElement(int key)
{
    Node *current = header;
 
    // create update array and initialize it
    Node *update[MAXLVL+1];
    memset(update, 0, sizeof(Node*)*(MAXLVL+1));
 
    /*    start from highest level of skip list
        move the current pointer forward while key 
        is greater than key of node next to current
        Otherwise inserted current in update and 
        move one level down and continue search
    */
    for (int i = level; i >= 0; i--)
    {
        while (current->forward[i] != NULL &&
              current->forward[i]->key < key)
            current = current->forward[i];
        update[i] = current;
    }
 
    /* reached level 0 and forward pointer to 
       right, which is desired position to 
       insert key. 
    */
    current = current->forward[0];
 
    /* if current is NULL that means we have reached
       to end of the level or current's key is not equal
       to key to insert that means we have to insert
       node between update[0] and current node */
    if (current == NULL || current->key != key)
    {
        // Generate a random level for node
        int rlevel = randomLevel();
 
        // If random level is greater than list's current
        // level (node with highest level inserted in 
        // list so far), initialize update value with pointer
        // to header for further use
        if (rlevel > level)
        {
            for (int i=level+1;i<rlevel+1;i++)
                update[i] = header;
 
            // Update the list current level
            level = rlevel;
        }
 
        // create new node with random level generated
        Node* n = createNode(key, rlevel);
 
        // insert node by rearranging pointers 
        for (int i=0;i<=rlevel;i++)
        {
            n->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = n;
        }
        cout << "Successfully Inserted key " << key << "\n";
    }
};
 
// Display skip list level wise
void SkipList::displayList()
{
    cout<<"\n*****Skip List*****"<<"\n";
    for (int i=0;i<=level;i++)
    {
        Node *node = header->forward[i];
        cout << "Level " << i << ": ";
        while (node != NULL)
        {
            cout << node->key<<" ";
            node = node->forward[i];
        }
        cout << "\n";
    }
};
 
// Driver to test above code
int main()
{
    // Seed random number generator
    srand((unsigned)time(0));
 
    // create SkipList object with MAXLVL and P 
    SkipList lst(3, 0.5);
 
    lst.insertElement(3);
    lst.insertElement(6);
    lst.insertElement(7);
    lst.insertElement(9);
    lst.insertElement(12);
    lst.insertElement(19);
    lst.insertElement(17);
    lst.insertElement(26);
    lst.insertElement(21);
    lst.insertElement(25);
    lst.displayList();
}

Java

// Java code for inserting element in skip list
 
class GFG {
 
    // Class to implement node
    static class Node {
        int key;
 
        // Array to hold pointers to node of different level
        Node forward[];
 
        Node(int key, int level)
        {
            this.key = key;
 
            // Allocate memory to forward
            forward = new Node[level + 1];
        }
    };
 
    // Class for Skip list
    static class SkipList {
        // Maximum level for this skip list
        int MAXLVL;
 
        // P is the fraction of the nodes with level
        // i pointers also having level i+1 pointers
        float P;
 
        // current level of skip list
        int level;
 
        // pointer to header node
        Node header;
 
        SkipList(int MAXLVL, float P)
        {
            this.MAXLVL = MAXLVL;
            this.P = P;
            level = 0;
 
            // create header node and initialize key to -1
            header = new Node(-1, MAXLVL);
        }
 
        int randomLevel()
        {
            float r = (float)Math.random();
            int lvl = 0;
            while (r < P && lvl < MAXLVL) {
                lvl++;
                r = (float)Math.random();
            }
            return lvl;
        }
 
        Node createNode(int key, int level)
        {
            Node n = new Node(key, level);
            return n;
        }
 
        // Insert given key in skip list
 
        void insertElement(int key)
        {
            Node current = header;
 
            // create update array and initialize it
            Node update[] = new Node[MAXLVL + 1];
 
            /* start from highest level of skip list
                    move the current pointer forward while
               key is greater than key of node next to
               current Otherwise inserted current in update
               and move one level down and continue search
            */
            for (int i = level; i >= 0; i--) {
                while (current.forward[i] != null
                       && current.forward[i].key < key)
                    current = current.forward[i];
                update[i] = current;
            }
 
            /* reached level 0 and forward pointer to
            right, which is desired position to
            insert key.
            */
            current = current.forward[0];
 
            /* if current is NULL that means we have reached
            to end of the level or current's key is not
            equal to key to insert that means we have to
            insert node between update[0] and current node
          */
            if (current == null || current.key != key) {
                // Generate a random level for node
                int rlevel = randomLevel();
 
                // If random level is greater than list's
                // current level (node with highest level
                // inserted in list so far), initialize
                // update value with pointer to header for
                // further use
                if (rlevel > level) {
                    for (int i = level + 1; i < rlevel + 1;
                         i++)
                        update[i] = header;
 
                    // Update the list current level
                    level = rlevel;
                }
 
                // create new node with random level
                // generated
                Node n = createNode(key, rlevel);
 
                // insert node by rearranging pointers
                for (int i = 0; i <= rlevel; i++) {
                    n.forward[i] = update[i].forward[i];
                    update[i].forward[i] = n;
                }
                System.out.println(
                    "Successfully Inserted key " + key);
            }
        }
 
        // Display skip list level wise
        void displayList()
        {
            System.out.println("\n*****Skip List*****");
            for (int i = 0; i <= level; i++) {
                Node node = header.forward[i];
                System.out.print("Level " + i + ": ");
                while (node != null) {
                    System.out.print(node.key + " ");
                    node = node.forward[i];
                }
                System.out.println();
            }
        }
    }
 
    // Driver to test above code
    public static void main(String[] args)
    {
        // create SkipList object with MAXLVL and P
        SkipList lst = new SkipList(3, 0.5f);
 
        lst.insertElement(3);
        lst.insertElement(6);
        lst.insertElement(7);
        lst.insertElement(9);
        lst.insertElement(12);
        lst.insertElement(19);
        lst.insertElement(17);
        lst.insertElement(26);
        lst.insertElement(21);
        lst.insertElement(25);
        lst.displayList();
    }
}
 
// This code is contributed by Lovely Jain

Python

# Python3 code for inserting element in skip list
 
import random
 
class Node(object):
    '''
    Class to implement node
    '''
    def __init__(self, key, level):
        self.key = key
 
        # list to hold references to node of different level 
        self.forward = [None]*(level+1)
 
class SkipList(object):
    '''
    Class for Skip list
    '''
    def __init__(self, max_lvl, P):
        # Maximum level for this skip list
        self.MAXLVL = max_lvl
 
        # P is the fraction of the nodes with level 
        # i references also having level i+1 references
        self.P = P
 
        # create header node and initialize key to -1
        self.header = self.createNode(self.MAXLVL, -1)
 
        # current level of skip list
        self.level = 0
     
    # create  new node
    def createNode(self, lvl, key):
        n = Node(key, lvl)
        return n
     
    # create random level for node
    def randomLevel(self):
        lvl = 0
        while random.random()<self.P and \
              lvl<self.MAXLVL:lvl += 1
        return lvl
 
    # insert given key in skip list
    def insertElement(self, key):
        # create update array and initialize it
        update = [None]*(self.MAXLVL+1)
        current = self.header
 
        '''
        start from highest level of skip list
        move the current reference forward while key 
        is greater than key of node next to current
        Otherwise inserted current in update and 
        move one level down and continue search
        '''
        for i in range(self.level, -1, -1):
            while current.forward[i] and \
                  current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current
 
        ''' 
        reached level 0 and forward reference to 
        right, which is desired position to 
        insert key.
        '''
        current = current.forward[0]
 
        '''
        if current is NULL that means we have reached
           to end of the level or current's key is not equal
           to key to insert that means we have to insert
           node between update[0] and current node
       '''
        if current == None or current.key != key:
            # Generate a random level for node
            rlevel = self.randomLevel()
 
            '''
            If random level is greater than list's current
            level (node with highest level inserted in 
            list so far), initialize update value with reference
            to header for further use
            '''
            if rlevel > self.level:
                for i in range(self.level+1, rlevel+1):
                    update[i] = self.header
                self.level = rlevel
 
            # create new node with random level generated
            n = self.createNode(rlevel, key)
 
            # insert node by rearranging references 
            for i in range(rlevel+1):
                n.forward[i] = update[i].forward[i]
                update[i].forward[i] = n
 
            print("Successfully inserted key {}".format(key))
 
    # Display skip list level wise
    def displayList(self):
        print("\n*****Skip List******")
        head = self.header
        for lvl in range(self.level+1):
            print("Level {}: ".format(lvl), end=" ")
            node = head.forward[lvl]
            while(node != None):
                print(node.key, end=" ")
                node = node.forward[lvl]
            print("")
 
# Driver to test above code
def main():
    lst = SkipList(3, 0.5)
    lst.insertElement(3)
    lst.insertElement(6)
    lst.insertElement(7)
    lst.insertElement(9)
    lst.insertElement(12)
    lst.insertElement(19)
    lst.insertElement(17)
    lst.insertElement(26)
    lst.insertElement(21)
    lst.insertElement(25)
    lst.displayList()
 
main()

C#

// C# code for inserting element in skip list
using System;
 
// Class to implement node
public class Node {
  public int key;
 
  // Array to hold pointers to node of different level
  public Node[] forward;
  public Node(int key, int level)
  {
    this.key = key;
 
    // Allocate memory to forward
    forward = new Node[level + 1];
 
    // Fill forward array with 0(NULL)
    Array.Clear(forward, 0, level + 1);
  }
}
 
// Class for Skip list
public class SkipList {
  // Maximum level for this skip list
  int MAXLVL;
 
  // P is the fraction of the nodes with level
  // i pointers also having level i+1 pointers
  float P;
 
  // current level of skip list
  int level;
 
  // pointer to header node
  Node header;
  public SkipList(int MAXLVL, float P)
  {
    this.MAXLVL = MAXLVL;
    this.P = P;
    level = 0;
 
    // create header node and initialize key to -1
    header = new Node(-1, MAXLVL);
  }
 
  // create random level for node
  int RandomLevel()
  {
    float r = (float)new Random().Next() / int.MaxValue;
    int lvl = 0;
    while (r < P && lvl < MAXLVL) {
      lvl++;
      r = (float)new Random().Next() / int.MaxValue;
    }
    return lvl;
  }
 
  // create new node
  Node CreateNode(int key, int level)
  {
    Node n = new Node(key, level);
    return n;
  }
 
  // Insert given key in skip list
  public void InsertElement(int key)
  {
    Node current = header;
 
    // create update array and initialize it
    Node[] update = new Node[MAXLVL + 1];
    Array.Clear(update, 0, MAXLVL + 1);
 
    /*    start from highest level of skip list
            move the current pointer forward while key
            is greater than key of node next to current
            Otherwise inserted current in update and
            move one level down and continue search
        */
    for (int i = level; i >= 0; i--) {
      while (current.forward[i] != null
             && current.forward[i].key < key)
        current = current.forward[i];
      update[i] = current;
    }
 
    /* reached level 0 and forward pointer to
           right, which is desired position to
           insert key.
        */
    current = current.forward[0];
 
    /* if current is NULL that means we have reached
           to end of the level or current's key is not equal
           to key to insert that means we have to insert
           node between update[0] and current node */
    if (current == null || current.key != key) {
      // Generate a random level for node
      int rlevel = RandomLevel();
 
      // If random level is greater than list's
      // current level (node with highest level
      // inserted in list so far), initialize update
      // value with pointer to header for further use
      if (rlevel > level) {
        for (int i = level + 1; i < rlevel + 1; i++)
          update[i] = header;
 
        // Update the list current level
        level = rlevel;
      }
 
      // create new node with random level generated
      Node n = CreateNode(key, rlevel);
 
      // insert node by rearranging pointers
      for (int i = 0; i <= rlevel; i++) {
        n.forward[i] = update[i].forward[i];
        update[i].forward[i] = n;
      }
      Console.WriteLine("Successfully Inserted key "
                        + key);
    }
  }
 
  // Display skip list level wise
  public void DisplayList()
  {
    Console.WriteLine("\n*****Skip List*****");
    for (int i = 0; i <= level; i++) {
      Node node = header.forward[i];
      Console.Write("Level " + i + ": ");
      while (node != null) {
        Console.Write(node.key + " ");
        node = node.forward[i];
      }
      Console.WriteLine();
    }
  }
 
  // Driver to test above code
  public static void Main(string[] args)
  {
    // Seed random number generator
    Random r = new Random(Guid.NewGuid().GetHashCode());
 
    // create SkipList object with MAXLVL and P
    SkipList lst = new SkipList(3, 0.5f);
 
    lst.InsertElement(3);
    lst.InsertElement(6);
    lst.InsertElement(7);
    lst.InsertElement(9);
    lst.InsertElement(12);
    lst.InsertElement(19);
    lst.InsertElement(17);
    lst.InsertElement(26);
    lst.InsertElement(21);
    lst.InsertElement(25);
    lst.DisplayList();
  }
}

Javascript

// JavaScript code for inserting element in skip list
 
// Class to implement node
class Node {
  constructor(key, level) {
    this.key = key;
 
    // Array to hold pointers to node of different level
    this.forward = new Array(level + 1).fill(null);
  }
}
 
// Class for Skip list
class SkipList {
  // Maximum level for this skip list
  MAXLVL;
 
  // P is the fraction of the nodes with level
  // i pointers also having level i+1 pointers
  P;
 
  // current level of skip list
  level;
 
  // pointer to header node
  header;
 
  constructor(MAXLVL, P) { 
    this.MAXLVL = MAXLVL;
    this.P = P;
    this.level = 0;
 
    // create header node and initialize key to -1
    this.header = new Node(-1, MAXLVL);
  }
 
  // create random level for node
  randomLevel() {
    let r = Math.random();
    let lvl = 0;
    while (r < this.P && lvl < this.MAXLVL) {
      lvl++;
      r = Math.random();
    }
    return lvl;
  }
 
  // create new node
  createNode(key, level) {
    let n = new Node(key, level);
    return n;
  }
 
  // Insert given key in skip list
  insertElement(key) {
    let current = this.header;
 
    // create update array and initialize it
    let update = new Array(this.MAXLVL + 1).fill(null);
 
    /*    start from highest level of skip list
        move the current pointer forward while key
        is greater than key of node next to current
        Otherwise inserted current in update and
        move one level down and continue search
    */
    for (let i = this.level; i >= 0; i--) {
      while (current.forward[i] != null && current.forward[i].key < key) {
        current = current.forward[i];
      }
      update[i] = current;
    }
 
    /* reached level 0 and forward pointer to
       right, which is desired position to
       insert key.
    */
    current = current.forward[0];
 
    /* if current is NULL that means we have reached
       to end of the level or current's key is not equal
       to key to insert that means we have to insert
       node between update[0] and current node */
    if (current == null || current.key != key) {
      // Generate a random level for node
      let rlevel = this.randomLevel();
 
      // If random level is greater than list's current
      // level (node with highest level inserted in
      // list so far), initialize update value with pointer
      // to header for further use
      if (rlevel > this.level) {
        for (let i = this.level + 1; i < rlevel + 1; i++) {
          update[i] = this.header;
        }
 
        // Update the list current level
        this.level = rlevel;
      }
 
      // create new node with random level generated
      let n = this.createNode(key, rlevel);
 
      // insert node by rearranging pointers
      for (let i = 0; i <= rlevel; i++) {
        n.forward[i] = update[i].forward[i];
        update[i].forward[i] = n;
      }
      console.log(`Successfully Inserted key ${key}`);
    }
  }
 
  // Display skip list level wise
  displayList() {
    console.log("\n*****Skip List*****");
    for (let i = 0; i <= this.level; i++) {
      let node = this.header.forward[i];
      console.log(`Level ${i}: `);
      while (node != null) {
        console.log(`${node.key} `);
        node = node.forward[i];
      }
      console.log("\n");
    }
  }
}
 
// Driver to test above code
let lst = new SkipList(3, 0.5);
 
lst.insertElement(3);
lst.insertElement(6);
lst.insertElement(7);
lst.insertElement(9);
lst.insertElement(12);
lst.insertElement(19);
lst.insertElement(17);
lst.insertElement(26);
lst.insertElement(21);
lst.insertElement(25);
lst.displayList();
 
// This code is contributed by ishankhandelwals.

Output

Successfully Inserted key 3
Successfully Inserted key 6
Successfully Inserted key 7
Successfully Inserted key 9
Successfully Inserted key 12
Successfully Inserted key 19
Successfully Inserted key 17
Successfully Inserted key 26
Successfully Inserted key 21
Successfully Inserted key 25

*****Skip List*****
Level 0: 3 6 7 9 12 17 19 21 25 26 
Level 1: 3 6 12 17 25 26 
Level 2: 3 6 12 25 
Level 3: 3 25

Note: The level of nodes is decided randomly, so output may differ.

Time complexity

Average: $O(log n)$
Worst: $O(n)$ In next article we will discuss searching and deletion in Skip List.

This article is contributed by Atul Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Skip List | Set 2 (Insertion)

C++

Java

Python

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

Bitdefender Black Friday & Cyber Monday Deals 2025 by Sam Boyd

Gemini arrives on Android Auto as your car’s new co-pilot

Quick Share needs this one thing to work with AirDrop

This Garmin powerhouse outclasses every ‘Ultra’ watch, and calling it a must-buy feels like an understatement

EDITOR PICKS

Bitdefender Black Friday & Cyber Monday Deals 2025 by Sam Boyd

Gemini arrives on Android Auto as your car’s new co-pilot

Quick Share needs this one thing to work with AirDrop

POPULAR POSTS

Bitdefender Black Friday & Cyber Monday Deals 2025 by Sam Boyd

Gemini arrives on Android Auto as your car’s new co-pilot

Quick Share needs this one thing to work with AirDrop

POPULAR CATEGORY

ABOUT US

FOLLOW US