Close Menu
Data Structures

Searching and Deleting Elements in Skip Lists: A Comprehensive Guide

By

In our previous discussion on Skip List Insertion, we explored the structure of skip nodes and the mechanism for inserting elements into a skip list. In this article, we will focus on the essential operations of searching and deleting elements in a skip list. These operations are critical for leveraging the efficiency and adaptability of skip lists in various applications.

Also Read:

Searching an Element in a Skip List

The process of searching for an element in a skip list is remarkably similar to the approach used for finding the appropriate position to insert an element. The search algorithm takes advantage of the hierarchical structure of the skip list, enabling rapid traversal across multiple levels to locate the desired key efficiently.

Searching Elements in Skip List
Searching Element with Key 17 in Skip List

Key Concepts of the Search Algorithm

  • Horizontal Traversal: At each level, if the key of the next node is smaller than the search key, the search continues by moving forward at the same level.
  • Vertical Movement: When the key of the next node is larger than the search key, the algorithm moves down one level and continues the search.
  • Final Verification: At the lowest level (level 0), the algorithm checks if the key of the next node matches the search key. If a match is found, the search is successful; otherwise, it concludes with failure.

The search algorithm ensures that at each step, the traversal avoids unnecessary comparisons, making it efficient for large datasets.

Pseudocode for Searching

Below is the pseudocode for the search operation:

Search(list, searchKey)
    x := list -> header
    for i := list -> level downto 0 do
        while x -> forward[i] -> key < searchKey do
            x := x -> forward[i]
    x := x -> forward[0]
    if x -> key = searchKey then 
        return x -> value
    else 
        return failure

Example: Searching for Key 17

Consider the following skip list, where we want to locate the key 17. The search begins at the topmost level:

  1. At level 3, the algorithm moves forward until it encounters a node with a key greater than 17, at which point it moves down to level 2.
  2. The process continues, level by level, until it reaches level 0.
  3. If the node with the key 17 exists, it is returned as the result; otherwise, the search fails.

Deleting an Element from a Skip List

The deletion operation is another fundamental aspect of maintaining a skip list. The process begins with locating the element to be deleted using the search algorithm. Once the target node is found, pointers are rearranged to remove the node, similar to the procedure in a singly linked list. The hierarchical nature of the skip list ensures that the deletion operation remains efficient.

Deleting Elements in Skip List
Deleting Element with Key 6 in Skip List

Key Concepts of the Deletion Algorithm

  • Locating the Target Node: The element to be deleted is located using the search operation.
  • Pointer Rearrangement: Starting from the lowest level, the pointers are adjusted to bypass the target node. This is repeated for each level where the node exists.
  • Level Adjustment: After deletion, if any levels become empty, they are removed by decrementing the level of the skip list.

Pseudocode for Deletion

Below is the pseudocode for the deletion operation:

Delete(list, searchKey)
    local update[0..MaxLevel+1]
    x := list -> header
    for i := list -> level downto 0 do
      while x -> forward[i] -> key < searchKey do
          x := x -> forward[i]
      update[i] := x
    x := x -> forward[0]
    if x -> key = searchKey then
      for i := 0 to list -> level do
          if update[i] -> forward[i] ≠ x then break
          update[i] -> forward[i] := x -> forward[i]
      free(x)
      while list -> level > 0 and list -> header -> forward[list -> level] = NIL do
          list -> level := list -> level – 1

Example: Deleting Element 6

Consider a skip list containing the keys 3, 6, 7, 9, 12, 17, 19, 21, 25, 26. The deletion of the key 6 proceeds as follows:

  1. Using the search algorithm, locate the node with the key 6.
  2. Rearrange the pointers at each level where the key 6 exists to bypass the node.
  3. After deletion, check if any levels are empty. In this case, level 3 becomes empty, so the level of the skip list is decremented by 1.

Code Implementation for Search and Delete Operation

Below is the complete implementation for searching and deleting elements in a skip list:

Search Operation

C Programming

Node* search(SkipList* list, int searchKey) {
    Node* x = list->header;
    for (int i = list->level; i >= 0; i--) {
        while (x->forward[i] != NULL && x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
    }
    x = x->forward[0];
    if (x != NULL && x->key == searchKey) {
        return x;
    }
    return NULL;
}

C++ Implementation

Node* search(SkipList* list, int searchKey) {
    Node* x = list->header;
    for (int i = list->level; i >= 0; i--) {
        while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
    }
    x = x->forward[0];
    if (x != nullptr && x->key == searchKey) {
        return x;
    }
    return nullptr;
}

C# Implementation

public Node Search(SkipList list, int searchKey) {
    Node x = list.Header;
    for (int i = list.Level; i >= 0; i--) {
        while (x.Forward[i] != null && x.Forward[i].Key < searchKey) {
            x = x.Forward[i];
        }
    }
    x = x.Forward[0];
    if (x != null && x.Key == searchKey) {
        return x;
    }
    return null;
}

Java Implementation

public Node search(SkipList list, int searchKey) {
    Node x = list.header;
    for (int i = list.level; i >= 0; i--) {
        while (x.forward[i] != null && x.forward[i].key < searchKey) {
            x = x.forward[i];
        }
    }
    x = x.forward[0];
    if (x != null && x.key == searchKey) {
        return x;
    }
    return null;
}

JavaScript Implementation

function search(list, searchKey) {
    let x = list.header;
    for (let i = list.level; i >= 0; i--) {
        while (x.forward[i] !== undefined && x.forward[i].key < searchKey) {
            x = x.forward[i];
        }
    }
    x = x.forward[0];
    if (x !== undefined && x.key === searchKey) {
        return x;
    }
    return null;
}

Python Implementation

def search(list, search_key):
    x = list.header
    for i in range(list.level, -1, -1):
        while x.forward[i] is not None and x.forward[i].key < search_key:
            x = x.forward[i]
    x = x.forward[0]
    if x is not None and x.key == search_key:
        return x
    return None

Each implementation

  • Traverses the skip list from the highest level to the lowest.
  • Moves forward at each level until it reaches a node whose key is not smaller than the searchKey.
  • Checks the next node at level 0 to see if it matches searchKey.
  • Returns the node if found, otherwise NULL/null/None (depending on the language).

Delete Operation

C Programming

void delete(SkipList* list, int searchKey) {
    Node* update[MaxLevel + 1];
    Node* x = list->header;
    for (int i = list->level; i >= 0; i--) {
        while (x->forward[i] != NULL && x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
        update[i] = x;
    }
    x = x->forward[0];
    if (x != NULL && x->key == searchKey) {
        for (int i = 0; i <= list->level; i++) {
            if (update[i]->forward[i] != x) break;
            update[i]->forward[i] = x->forward[i];
        }
        free(x);
        while (list->level > 0 && list->header->forward[list->level] == NULL) {
            list->level--;
        }
    }
}

C++ Implementation

void Delete(SkipList* list, int searchKey) {
    Node* update[MaxLevel + 1];
    Node* x = list->header;
    for (int i = list->level; i >= 0; i--) {
        while (x->forward[i] != nullptr && x->forward[i]->key < searchKey) {
            x = x->forward[i];
        }
        update[i] = x;
    }
    x = x->forward[0];
    if (x != nullptr && x->key == searchKey) {
        for (int i = 0; i <= list->level; i++) {
            if (update[i]->forward[i] != x) break;
            update[i]->forward[i] = x->forward[i];
        }
        free(x);
        while (list->level > 0 && list->header->forward[list->level] == nullptr) {
            list->level--;
        }
    }
}

C# Implementation

public void Delete(SkipList list, int searchKey) {
    Node[] update = new Node[MaxLevel + 1];
    Node x = list.Header;
    for (int i = list.Level; i >= 0; i--) {
        while (x.Forward[i] != null && x.Forward[i].Key < searchKey) {
            x = x.Forward[i];
        }
        update[i] = x;
    }
    x = x.Forward[0];
    if (x != null && x.Key == searchKey) {
        for (int i = 0; i <= list.Level; i++) {
            if (update[i].Forward[i] != x) break;
            update[i].Forward[i] = x.Forward[i];
        }
        x = null;
        while (list.Level > 0 && list.Header.Forward[list.Level] == null) {
            list.Level--;
        }
    }
}

Java Implementation

public void delete(SkipList list, int searchKey) {
    Node[] update = new Node[MaxLevel + 1];
    Node x = list.header;
    for (int i = list.level; i >= 0; i--) {
        while (x.forward[i] != null && x.forward[i].key < searchKey) {
            x = x.forward[i];
        }
        update[i] = x;
    }
    x = x.forward[0];
    if (x != null && x.key == searchKey) {
        for (int i = 0; i <= list.level; i++) {
            if (update[i].forward[i] != x) break;
            update[i].forward[i] = x.forward[i];
        }
        x = null;
        while (list.level > 0 && list.header.forward[list.level] == null) {
            list.level--;
        }
    }
}

JavaScript Implementation

function deleteElement(list, searchKey) {
    const update = new Array(MaxLevel + 1).fill(null);
    let x = list.header;
    for (let i = list.level; i >= 0; i--) {
        while (x.forward[i] && x.forward[i].key < searchKey) {
            x = x.forward[i];
        }
        update[i] = x;
    }
    x = x.forward[0];
    if (x && x.key === searchKey) {
        for (let i = 0; i <= list.level; i++) {
            if (update[i].forward[i] !== x) break;
            update[i].forward[i] = x.forward[i];
        }
        x = null;
        while (list.level > 0 && !list.header.forward[list.level]) {
            list.level--;
        }
    }
}

Python Implementation

def delete(list, search_key):
    update = [None] * (MaxLevel + 1)
    x = list.header
    for i in range(list.level, -1, -1):
        while x.forward[i] and x.forward[i].key < search_key:
            x = x.forward[i]
        update[i] = x
    x = x.forward[0]
    if x and x.key == search_key:
        for i in range(list.level + 1):
            if update[i].forward[i] != x:
                break
            update[i].forward[i] = x.forward[i]
        x = None
        while list.level > 0 and not list.header.forward[list.level]:
            list.level -= 1

Common Steps in All Implementations

  • Initialize update[]: Track the path to the node at each level for pointer updates.
  • Traverse the List: Use the forward pointers to locate the node to be deleted.
  • Remove the Node: Update the forward pointers to bypass the node.
  • Adjust Levels: If the top levels become empty, decrease the skip list’s level attribute.

Code Implementation In Multiple Programming Languages

Below is the Code implementation in multiple programming languages {Like: C Programming, C++ Programming, CSharp, Java Programming, JavaScript, and Python} of the skip list with search and delete functionality:

Deleting Elements in Skip Lists
Deleting Element with Key 19 in Skip List

C Programming

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Define the structure of a Node
typedef struct Node {
    int key;
    struct Node **forward; // Array to hold pointers to nodes of different levels
} Node;

// Define the structure of a SkipList
typedef struct SkipList {
    int MAXLVL;       // Maximum level of the skip list
    float P;          // Fraction of nodes with level i pointers also having level i+1 pointers
    int level;        // Current level of the skip list
    Node *header;     // Pointer to the header node
} SkipList;

// Function prototypes
Node* createNode(int key, int level);
SkipList* createSkipList(int MAXLVL, float P);
int randomLevel(SkipList *list);
void insertElement(SkipList *list, int key);
void deleteElement(SkipList *list, int key);
void searchElement(SkipList *list, int key);
void displayList(SkipList *list);

// Function to create a new node
Node* createNode(int key, int level) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->key = key;

    // Allocate memory for forward pointers
    n->forward = (Node **)malloc(sizeof(Node*) * (level + 1));

    // Initialize forward pointers to NULL
    for (int i = 0; i <= level; i++) {
        n->forward[i] = NULL;
    }
    return n;
}

// Function to create a new skip list
SkipList* createSkipList(int MAXLVL, float P) {
    SkipList *list = (SkipList *)malloc(sizeof(SkipList));
    list->MAXLVL = MAXLVL;
    list->P = P;
    list->level = 0;

    // Create header node
    list->header = createNode(-1, MAXLVL);
    return list;
}

// Function to generate a random level for a node
int randomLevel(SkipList *list) {
    float r = (float)rand() / RAND_MAX;
    int lvl = 0;
    while (r < list->P && lvl < list->MAXLVL) {
        lvl++;
        r = (float)rand() / RAND_MAX;
    }
    return lvl;
}

// Function to insert an element into the skip list
void insertElement(SkipList *list, int key) {
    Node *current = list->header;

    // Create an update array to hold pointers to nodes at each level
    Node *update[list->MAXLVL + 1];
    memset(update, 0, sizeof(Node*) * (list->MAXLVL + 1));

    // Traverse the skip list to find the correct position for the key
    for (int i = list->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    // Move to the next node at level 0
    current = current->forward[0];

    // If the key is not already present, insert it
    if (current == NULL || current->key != key) {
        // Generate a random level for the new node
        int rlevel = randomLevel(list);

        // Update the skip list level if the random level is higher
        if (rlevel > list->level) {
            for (int i = list->level + 1; i <= rlevel; i++) {
                update[i] = list->header;
            }
            list->level = rlevel;
        }

        // Create a new node
        Node *n = createNode(key, rlevel);

        // Rearrange pointers to insert the new node
        for (int i = 0; i <= rlevel; i++) {
            n->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = n;
        }
        printf("Successfully inserted key %d\n", key);
    }
}

// Function to delete an element from the skip list
void deleteElement(SkipList *list, int key) {
    Node *current = list->header;

    // Create an update array to hold pointers to nodes at each level
    Node *update[list->MAXLVL + 1];
    memset(update, 0, sizeof(Node*) * (list->MAXLVL + 1));

    // Traverse the skip list to find the node to be deleted
    for (int i = list->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    // Move to the next node at level 0
    current = current->forward[0];

    // If the node is found, delete it
    if (current != NULL && current->key == key) {
        for (int i = 0; i <= list->level; i++) {
            if (update[i]->forward[i] != current) {
                break;
            }
            update[i]->forward[i] = current->forward[i];
        }

        // Free the memory of the node
        free(current);

        // Remove levels with no elements
        while (list->level > 0 && list->header->forward[list->level] == NULL) {
            list->level--;
        }
        printf("Successfully deleted key %d\n", key);
    }
}

// Function to search for an element in the skip list
void searchElement(SkipList *list, int key) {
    Node *current = list->header;

    // Traverse the skip list to search for the key
    for (int i = list->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }

    // Move to the next node at level 0
    current = current->forward[0];

    // Check if the key is found
    if (current != NULL && current->key == key) {
        printf("Found key: %d\n", key);
    } else {
        printf("Key %d not found\n", key);
    }
}

// Function to display the skip list level by level
void displayList(SkipList *list) {
    printf("\n***** Skip List *****\n");
    for (int i = 0; i <= list->level; i++) {
        Node *node = list->header->forward[i];
        printf("Level %d: ", i);
        while (node != NULL) {
            printf("%d ", node->key);
            node = node->forward[i];
        }
        printf("\n");
    }
}

// Driver program to test the skip list
int main() {
    // Seed the random number generator
    srand((unsigned)time(0));

    // Create a skip list with maximum level 3 and probability 0.5
    SkipList *list = createSkipList(3, 0.5);

    // Insert elements into the skip list
    insertElement(list, 3);
    insertElement(list, 6);
    insertElement(list, 7);
    insertElement(list, 9);
    insertElement(list, 12);
    insertElement(list, 19);
    insertElement(list, 17);
    insertElement(list, 26);
    insertElement(list, 21);
    insertElement(list, 25);
    displayList(list);

    // Search for an element
    searchElement(list, 19);

    // Delete an element
    deleteElement(list, 19);
    displayList(list);

    return 0;
}

Explanation of Each Step

  • Structure Definitions:
    • Node: Represents a single element with a key and an array of forward pointers.
    • SkipList: Contains metadata about the skip list, including maximum level, probability, current level, and header node.
  • Node Creation:
    • Dynamically allocate memory for the node and its forward pointers.
  • Skip List Initialization:
    • Create a header node and initialize it with a key of -1.
  • Random Level Generation:
    • Generates a random level for a new node, following the given probability P.
  • Insertion:
    • Traverse the list to find the correct position for the new key.
    • Update pointers to insert the new node while maintaining the skip list structure.
  • Deletion:
    • Locate the target node using a similar traversal as insertion.
    • Rearrange pointers to bypass and remove the node.
  • Search:
    • Traverse the list to find the desired key. If found, print the result.
  • Display:
    • Traverse and print the elements of the skip list level by level.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// Node class to represent each element in the skip list
class Node {
public:
    int key; // The value of the node
    Node **forward; // Array of forward pointers for different levels

    Node(int key, int level);
};

// Constructor for Node class
Node::Node(int key, int level) {
    this->key = key;
    forward = new Node *[level + 1]; // Allocate memory for forward pointers
    memset(forward, 0, sizeof(Node *) * (level + 1)); // Initialize pointers to NULL
}

// SkipList class to implement the skip list
class SkipList {
    int MAXLVL;   // Maximum level for the skip list
    float P;      // Probability factor for level generation
    int level;    // Current highest level in the skip list
    Node *header; // Pointer to the header node

public:
    SkipList(int MAXLVL, float P);
    int randomLevel();
    Node *createNode(int key, int level);
    void insertElement(int key);
    void deleteElement(int key);
    void searchElement(int key);
    void displayList();
};

// Constructor for SkipList class
SkipList::SkipList(int MAXLVL, float P) {
    this->MAXLVL = MAXLVL;
    this->P = P;
    level = 0;
    header = new Node(-1, MAXLVL); // Create header node with key -1
}

// Generate a random level for a new 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 a new node with the given key and level
Node *SkipList::createNode(int key, int level) {
    return new Node(key, level);
}

// Insert a new element into the skip list
void SkipList::insertElement(int key) {
    Node *current = header;
    Node *update[MAXLVL + 1]; // Array to track the path to the node's position
    memset(update, 0, sizeof(Node *) * (MAXLVL + 1));

    // Find the position to insert the node
    for (int i = level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key)
            current = current->forward[i];
        update[i] = current;
    }

    current = current->forward[0];

    // If the key is not already in the list, insert it
    if (current == NULL || current->key != key) {
        int rlevel = randomLevel(); // Generate a random level

        if (rlevel > level) {
            for (int i = level + 1; i <= rlevel; i++)
                update[i] = header;
            level = rlevel; // Update the current level
        }

        Node *newNode = createNode(key, rlevel);

        // Rearrange pointers to insert the new node
        for (int i = 0; i <= rlevel; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
        cout << "Successfully inserted key " << key << "\n";
    }
}

// Delete an element from the skip list
void SkipList::deleteElement(int key) {
    Node *current = header;
    Node *update[MAXLVL + 1];
    memset(update, 0, sizeof(Node *) * (MAXLVL + 1));

    // Find the position of the node to delete
    for (int i = level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key)
            current = current->forward[i];
        update[i] = current;
    }

    current = current->forward[0];

    // If the node exists, delete it
    if (current != NULL && current->key == key) {
        for (int i = 0; i <= level; i++) {
            if (update[i]->forward[i] != current)
                break;
            update[i]->forward[i] = current->forward[i];
        }

        while (level > 0 && header->forward[level] == NULL)
            level--;

        cout << "Successfully deleted key " << key << "\n";
    }
}

// Search for an element in the skip list
void SkipList::searchElement(int key) {
    Node *current = header;

    // Traverse the list to find the key
    for (int i = level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key)
            current = current->forward[i];
    }

    current = current->forward[0];

    if (current != NULL && current->key == key)
        cout << "Found key: " << key << "\n";
    else
        cout << "Key not found: " << key << "\n";
}

// Display the skip list level by level
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";
    }
}

// Main function to test the skip list implementation
int main() {
    srand((unsigned)time(0));

    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();

    lst.searchElement(19);
    lst.deleteElement(19);
    lst.displayList();

    return 0;
}

Detailed Explanation of the Code

  • Node Class:
    • Represents an element in the skip list.
    • Contains:
      • key: Value of the node.
      • forward: Array of pointers to nodes on different levels.
  • SkipList Class:
    • Manages the operations of the skip list.
    • Contains:
      • MAXLVL: Maximum level for nodes.
      • P: Probability factor for determining levels.
      • level: Current maximum level.
      • header: Pointer to the header node.
  • Insert Operation:
    • Finds the correct position for the new node.
    • Generates a random level for the new node.
    • Adjusts the forward pointers to insert the node.
  • Delete Operation:
    • Locates the node to delete.
    • Updates pointers to bypass the node.
    • Reduces levels if they become empty.
  • Search Operation:
    • Traverses the skip list to find the node with the given key.
  • Display Operation:
    • Prints the skip list level by level for visualization.
  • Main Function:
    • Demonstrates insert, search, and delete operations.
    • Verifies the functionality by displaying the list before and after modifications.

C# Implementation

using System;

class Node
{
    // Represents a node in the skip list
    public int Key;
    public Node[] Forward;

    public Node(int key, int level)
    {
        Key = key;
        Forward = new Node[level + 1];
    }
}

class SkipList
{
    private const int MaxLevel = 3; // Maximum level of the skip list
    private readonly double Probability; // Probability for level generation
    private readonly Node Header; // Header node of the skip list
    private int CurrentLevel; // Current highest level in the skip list

    public SkipList(double probability)
    {
        Probability = probability;
        Header = new Node(-1, MaxLevel);
        CurrentLevel = 0;
    }

    // Create a new node
    private Node CreateNode(int level, int key)
    {
        return new Node(key, level);
    }

    // Generate a random level for a node
    private int RandomLevel()
    {
        int level = 0;
        Random random = new Random();
        while (random.NextDouble() < Probability && level < MaxLevel)
        {
            level++;
        }
        return level;
    }

    // Insert a new element into the skip list
    public void InsertElement(int key)
    {
        Node[] update = new Node[MaxLevel + 1];
        Node current = Header;

        // Locate the position to insert the new key
        for (int i = CurrentLevel; i >= 0; i--)
        {
            while (current.Forward[i] != null && current.Forward[i].Key < key)
            {
                current = current.Forward[i];
            }
            update[i] = current;
        }

        // Move to the next node at level 0
        current = current.Forward[0];

        // If the key does not already exist, insert it
        if (current == null || current.Key != key)
        {
            int randomLevel = RandomLevel();

            if (randomLevel > CurrentLevel)
            {
                for (int i = CurrentLevel + 1; i <= randomLevel; i++)
                {
                    update[i] = Header;
                }
                CurrentLevel = randomLevel;
            }

            Node newNode = CreateNode(randomLevel, key);
            for (int i = 0; i <= randomLevel; i++)
            {
                newNode.Forward[i] = update[i].Forward[i];
                update[i].Forward[i] = newNode;
            }

            Console.WriteLine($"Successfully inserted key {key}");
        }
    }

    // Delete an element from the skip list
    public void DeleteElement(int key)
    {
        Node[] update = new Node[MaxLevel + 1];
        Node current = Header;

        // Locate the position of the key to delete
        for (int i = CurrentLevel; i >= 0; i--)
        {
            while (current.Forward[i] != null && current.Forward[i].Key < key)
            {
                current = current.Forward[i];
            }
            update[i] = current;
        }

        current = current.Forward[0];

        if (current != null && current.Key == key)
        {
            for (int i = 0; i <= CurrentLevel; i++)
            {
                if (update[i].Forward[i] != current)
                {
                    break;
                }
                update[i].Forward[i] = current.Forward[i];
            }

            while (CurrentLevel > 0 && Header.Forward[CurrentLevel] == null)
            {
                CurrentLevel--;
            }

            Console.WriteLine($"Successfully deleted key {key}");
        }
    }

    // Search for a specific key in the skip list
    public void SearchElement(int key)
    {
        Node current = Header;

        for (int i = CurrentLevel; i >= 0; i--)
        {
            while (current.Forward[i] != null && current.Forward[i].Key < key)
            {
                current = current.Forward[i];
            }
        }

        current = current.Forward[0];

        if (current != null && current.Key == key)
        {
            Console.WriteLine($"Found key {key}");
        }
        else
        {
            Console.WriteLine($"Key {key} not found");
        }
    }

    // Display the skip list
    public void DisplayList()
    {
        Console.WriteLine("\n***** Skip List *****");
        for (int i = 0; i <= CurrentLevel; i++)
        {
            Node node = Header.Forward[i];
            Console.Write($"Level {i}: ");
            while (node != null)
            {
                Console.Write(node.Key + " ");
                node = node.Forward[i];
            }
            Console.WriteLine();
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        SkipList skipList = new SkipList(0.5);

        // Insert elements
        skipList.InsertElement(3);
        skipList.InsertElement(6);
        skipList.InsertElement(7);
        skipList.InsertElement(9);
        skipList.InsertElement(12);
        skipList.InsertElement(19);
        skipList.InsertElement(17);
        skipList.InsertElement(26);
        skipList.InsertElement(21);
        skipList.InsertElement(25);

        // Display the list
        skipList.DisplayList();

        // Search for an element
        skipList.SearchElement(19);

        // Delete an element
        skipList.DeleteElement(19);
        skipList.DisplayList();
    }
}

Explanation of Each Step

  • Node Class:
    • Represents individual nodes with a key and an array of forward pointers for different levels.
  • SkipList Class:
    • Maintains the skip list’s structure and implements operations like insertion, deletion, and search.
  • Insert Operation:
    • Finds the correct position for the key.
    • Generates a random level.
    • Updates forward pointers to insert the new node.
  • Delete Operation:
    • Locates the key.
    • Updates pointers to bypass the node being deleted.
    • Reduces the level of the list if needed.
  • Search Operation:
    • Traverses levels and nodes to locate the key.
    • Outputs whether the key is found.
  • Display Operation:
    • Prints the skip list level by level.

Java Implementation

import java.util.Random;

// Java code for inserting, deleting, and searching elements in a skip list
public class SkipListExample {

    // Node class representing each element in the skip list
    static class Node {
        int key; // Value stored in the node
        Node[] forward; // Array of pointers for each level

        Node(int key, int level) {
            this.key = key;
            forward = new Node[level + 1]; // Allocate space for forward pointers
        }
    }

    // SkipList class containing methods for operations
    static class SkipList {
        private static final int MAX_LEVEL = 3; // Maximum levels in the skip list
        private static final float P = 0.5f; // Probability for level generation
        private int level; // Current level of the skip list
        private final Node header; // Header node

        SkipList() {
            this.level = 0; // Initially, the skip list has level 0
            this.header = new Node(-1, MAX_LEVEL); // Header node with key -1
        }

        // Generate a random level for a new node
        private int randomLevel() {
            Random random = new Random();
            int lvl = 0;
            while (random.nextFloat() < P && lvl < MAX_LEVEL) {
                lvl++;
            }
            return lvl;
        }

        // Insert a new key into the skip list
        public void insertElement(int key) {
            Node current = header;

            // Create an update array to store pointers to nodes at each level
            Node[] update = new Node[MAX_LEVEL + 1];

            // Traverse the list to find the position for insertion
            for (int i = level; i >= 0; i--) {
                while (current.forward[i] != null && current.forward[i].key < key) {
                    current = current.forward[i];
                }
                update[i] = current;
            }

            // Move to the level 0 node
            current = current.forward[0];

            // If the key is not already present, insert the new node
            if (current == null || current.key != key) {
                int rlevel = randomLevel();

                // Update the list level if needed
                if (rlevel > level) {
                    for (int i = level + 1; i <= rlevel; i++) {
                        update[i] = header;
                    }
                    level = rlevel;
                }

                // Create the new node and rearrange pointers
                Node newNode = new Node(key, rlevel);
                for (int i = 0; i <= rlevel; i++) {
                    newNode.forward[i] = update[i].forward[i];
                    update[i].forward[i] = newNode;
                }
                System.out.println("Successfully inserted key " + key);
            }
        }

        // Delete a key from the skip list
        public void deleteElement(int key) {
            Node current = header;
            Node[] update = new Node[MAX_LEVEL + 1];

            // Traverse the list to locate the node to delete
            for (int i = level; i >= 0; i--) {
                while (current.forward[i] != null && current.forward[i].key < key) {
                    current = current.forward[i];
                }
                update[i] = current;
            }

            // Move to the level 0 node
            current = current.forward[0];

            // If the node exists, update pointers and remove it
            if (current != null && current.key == key) {
                for (int i = 0; i <= level; i++) {
                    if (update[i].forward[i] != current) break;
                    update[i].forward[i] = current.forward[i];
                }

                // Remove levels that are no longer used
                while (level > 0 && header.forward[level] == null) {
                    level--;
                }
                System.out.println("Successfully deleted key " + key);
            } else {
                System.out.println("Key " + key + " not found for deletion.");
            }
        }

        // Search for a key in the skip list
        public void search(int key) {
            Node current = header;

            // Traverse the list to locate the key
            for (int i = level; i >= 0; i--) {
                while (current.forward[i] != null && current.forward[i].key < key) {
                    current = current.forward[i];
                }
            }
            current = current.forward[0];

            // Check if the key is present
            if (current != null && current.key == key) {
                System.out.println("Key " + key + " found.");
            } else {
                System.out.println("Key " + key + " not found.");
            }
        }

        // Display the skip list level by level
        public 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 code to test the skip list implementation
    public static void main(String[] args) {
        SkipList skipList = new SkipList();

        // Insert elements
        skipList.insertElement(3);
        skipList.insertElement(6);
        skipList.insertElement(7);
        skipList.insertElement(9);
        skipList.insertElement(12);
        skipList.insertElement(19);
        skipList.insertElement(17);
        skipList.insertElement(26);
        skipList.insertElement(21);
        skipList.insertElement(25);

        // Display the skip list
        skipList.displayList();

        // Delete elements
        skipList.deleteElement(9);
        skipList.deleteElement(12);

        // Display after deletions
        skipList.displayList();

        // Search for an element
        skipList.search(9);
    }
}

JavaScript Implementation

// Node class
class Node {
    constructor(key, level) {
        this.key = key; // Value of the node
        this.forward = new Array(level + 1); // Array of pointers for each level
    }
}

// SkipList class
class SkipList {
    constructor(MAXLVL, P) {
        this.MAXLVL = MAXLVL; // Maximum number of levels
        this.P = P; // Probability for promoting nodes to higher levels
        this.level = 0; // Current highest level in the skip list
        this.header = new Node(-1, MAXLVL); // Header node with key -1
    }

    // Generate a random level for a new node
    randomLevel() {
        let lvl = 0;
        while (Math.random() < this.P && lvl < this.MAXLVL) {
            lvl++;
        }
        return lvl;
    }

    // Create a new node
    createNode(key, level) {
        return new Node(key, level);
    }

    // Insert a key into the skip list
    insertElement(key) {
        let current = this.header;
        const update = new Array(this.MAXLVL + 1);

        // Find the position to insert the new node
        for (let i = this.level; i >= 0; i--) {
            while (current.forward[i] && current.forward[i].key < key) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        // Move to the next node in level 0
        current = current.forward[0];

        // If the key is not already present, insert it
        if (!current || current.key !== key) {
            const rlevel = this.randomLevel();

            // Update the current level of the skip list
            if (rlevel > this.level) {
                for (let i = this.level + 1; i <= rlevel; i++) {
                    update[i] = this.header;
                }
                this.level = rlevel;
            }

            // Create the new node
            const newNode = this.createNode(key, rlevel);

            // Adjust pointers to insert the new node
            for (let i = 0; i <= rlevel; i++) {
                newNode.forward[i] = update[i].forward[i];
                update[i].forward[i] = newNode;
            }

            console.log(`Successfully inserted key ${key}`);
        }
    }

    // Delete a key from the skip list
    deleteElement(key) {
        let current = this.header;
        const update = new Array(this.MAXLVL + 1);

        // Find the node to delete
        for (let i = this.level; i >= 0; i--) {
            while (current.forward[i] && current.forward[i].key < key) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        // Move to the next node in level 0
        current = current.forward[0];

        // If the key is found, delete it
        if (current && current.key === key) {
            for (let i = 0; i <= this.level; i++) {
                if (update[i].forward[i] !== current) break;
                update[i].forward[i] = current.forward[i];
            }

            // Adjust levels if necessary
            while (this.level > 0 && !this.header.forward[this.level]) {
                this.level--;
            }

            console.log(`Successfully deleted key ${key}`);
        } else {
            console.log(`Key ${key} not found for deletion.`);
        }
    }

    // Search for a key in the skip list
    search(key) {
        let current = this.header;

        // Traverse the skip list to find the key
        for (let i = this.level; i >= 0; i--) {
            while (current.forward[i] && current.forward[i].key < key) {
                current = current.forward[i];
            }
        }

        // Move to the next node in level 0
        current = current.forward[0];

        // Check if the key is found
        if (current && current.key === key) {
            console.log(`Key ${key} found.`);
        } else {
            console.log(`Key ${key} not found.`);
        }
    }

    // Display the skip list
    displayList() {
        console.log("\n***** Skip List *****");
        for (let i = 0; i <= this.level; i++) {
            let node = this.header.forward[i];
            const levelKeys = [];
            while (node) {
                levelKeys.push(node.key);
                node = node.forward[i];
            }
            console.log(`Level ${i}: ${levelKeys.join(" ")}`);
        }
    }
}

// Driver code
const skipList = new SkipList(3, 0.5);

// Insert elements into the skip list
skipList.insertElement(3);
skipList.insertElement(6);
skipList.insertElement(7);
skipList.insertElement(9);
skipList.insertElement(12);
skipList.insertElement(19);
skipList.insertElement(17);
skipList.insertElement(26);
skipList.insertElement(21);
skipList.insertElement(25);

// Display the skip list
skipList.displayList();

// Delete elements
skipList.deleteElement(9);
skipList.deleteElement(12);

// Display after deletions
skipList.displayList();

// Search for a key
skipList.search(9);

Detailed Explanation

  • Insert a Key
    • Traverse the skip list from the highest level.
    • Keep track of the nodes (update[]) that will need their pointers updated.
    • Generate a random level for the new node.
    • Adjust pointers to insert the new node.
  • Delete a Key
    • Traverse the skip list to find the key.
    • Use the update[] array to rearrange pointers and bypass the node.
    • Adjust the skip list’s level if necessary (remove empty levels).
  • Search for a Key
    • Traverse each level of the skip list, moving right until the desired key is found or the end is reached.
  • Display the Skip List
    • Print all keys at each level of the skip list.

Python Implementation

import random

# Node class
class Node:
    def __init__(self, key, level):
        self.key = key  # Value of the node
        self.forward = [None] * (level + 1)  # Array of pointers for each level


# SkipList class
class SkipList:
    def __init__(self, max_level, p):
        self.MAXLVL = max_level  # Maximum number of levels
        self.P = p  # Probability for promoting nodes to higher levels
        self.level = 0  # Current highest level in the skip list
        self.header = self.create_node(-1, self.MAXLVL)  # Header node with key -1

    # Generate a random level for a new node
    def random_level(self):
        lvl = 0
        while random.random() < self.P and lvl < self.MAXLVL:
            lvl += 1
        return lvl

    # Create a new node
    def create_node(self, key, level):
        return Node(key, level)

    # Insert a key into the skip list
    def insert_element(self, key):
        current = self.header
        update = [None] * (self.MAXLVL + 1)

        # Traverse the skip list to find the position to insert the key
        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

        # Move to the next node in level 0
        current = current.forward[0]

        # If the key is not already present, insert it
        if not current or current.key != key:
            rlevel = self.random_level()

            # Update the current level of the skip list if the new node's level is higher
            if rlevel > self.level:
                for i in range(self.level + 1, rlevel + 1):
                    update[i] = self.header
                self.level = rlevel

            # Create the new node
            new_node = self.create_node(key, rlevel)

            # Adjust pointers to insert the new node
            for i in range(rlevel + 1):
                new_node.forward[i] = update[i].forward[i]
                update[i].forward[i] = new_node

            print(f"Successfully inserted key {key}")

    # Delete a key from the skip list
    def delete_element(self, key):
        current = self.header
        update = [None] * (self.MAXLVL + 1)

        # Traverse the skip list to find the key
        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

        # Move to the next node in level 0
        current = current.forward[0]

        # If the key is found, delete it
        if current and current.key == key:
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]

            # Adjust the skip list's level if necessary
            while self.level > 0 and not self.header.forward[self.level]:
                self.level -= 1

            print(f"Successfully deleted key {key}")
        else:
            print(f"Key {key} not found for deletion.")

    # Search for a key in the skip list
    def search_element(self, key):
        current = self.header

        # Traverse the skip list to find the key
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]

        # Move to the next node in level 0
        current = current.forward[0]

        # Check if the key is found
        if current and current.key == key:
            print(f"Found key: {key}")
        else:
            print(f"Key {key} not found.")

    # Display the skip list
    def display_list(self):
        print("\n***** Skip List *****")
        for i in range(self.level + 1):
            node = self.header.forward[i]
            print(f"Level {i}: ", end="")
            while node:
                print(node.key, end=" ")
                node = node.forward[i]
            print()


# Driver code
if __name__ == "__main__":
    # Seed for reproducibility
    random.seed(42)

    # Create a skip list with maximum level 3 and probability 0.5
    lst = SkipList(3, 0.5)

    # Insert elements
    lst.insert_element(3)
    lst.insert_element(6)
    lst.insert_element(7)
    lst.insert_element(9)
    lst.insert_element(12)
    lst.insert_element(19)
    lst.insert_element(17)
    lst.insert_element(26)
    lst.insert_element(21)
    lst.insert_element(25)

    # Display the skip list
    lst.display_list()

    # Search for an element
    lst.search_element(19)

    # Delete an element
    lst.delete_element(19)

    # Display after deletion
    lst.display_list()

Detailed Explanation

  • Initialization:
    • A Node class is used to represent individual nodes. Each node has a key and a list of forward pointers for each level.
    • The SkipList class initializes with a header node of maximum level and keeps track of the current highest level.
  • Insertion:
    • The skip list is traversed level by level, starting from the highest.
    • Nodes that need their forward pointers updated are stored in an update list.
    • A random level is generated for the new node, and the skip list’s current level is updated if necessary.
    • The new node is inserted, and pointers are adjusted accordingly.
  • Deletion:
    • Similar to insertion, the list is traversed, and nodes that require pointer updates are stored.
    • The key is removed, and levels are adjusted if they become empty.
  • Search:
    • The skip list is traversed to locate the desired key. If found, it is reported; otherwise, an appropriate message is displayed.
  • Display:
    • Each level of the skip list is printed with all its keys.

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: 6 12 17 21 
Level 2: 6 12 17 
Level 3: 6 12 
Found key: 19
Successfully deleted key 19

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

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

Time complexity

The time complexity of both searching and deletion is the same.

Time complexity Worst case:

  • Access: O(n)
  • Search: O(n)
  • Insert: O(n)
  • Space: O(nlogn)
  • Delete: O(n)

Advantages of Searching and Deleting in Skip Lists

The skip list is an innovative and efficient data structure that shines when it comes to operations like searching and deleting elements. Below are the key advantages of these operations:

  • Efficient Search and Deletion Times
    • Logarithmic Time Complexity: Both searching and deleting elements in a skip list have an expected time complexity of O(log n). This efficiency stems from the hierarchical structure of skip lists, which allows skipping over large portions of the data.
    • Quick Traversals: By leveraging multiple levels, the algorithm reduces the number of comparisons needed to locate or remove an element.
  • Probabilistic Balancing
    • Skip lists achieve balance through randomization rather than deterministic balancing algorithms (as seen in AVL trees or Red-Black trees). This eliminates the need for complex rotations or rebalancing.
    • The random level assignment ensures an even distribution of elements across the levels, maintaining efficiency even after multiple deletions.
  • Dynamic Level Management
    • Skip lists adjust their structure dynamically during deletion. If a level becomes empty after an element is removed, the highest level is dropped, conserving memory and maintaining a compact structure.
    • This feature is absent in many other data structures, which may leave unused nodes or levels.
  • Space-Efficient Design
    • Despite having multiple levels, the space overhead of a skip list is minimal. The probabilistic distribution ensures that higher levels contain fewer nodes, leading to logarithmic additional space usage.
    • Deletion operations free up memory immediately, ensuring no unnecessary memory consumption.
  • Simple Implementation
    • The algorithms for searching and deleting in skip lists are relatively simple compared to other balanced structures like B-trees or Red-Black trees. The pseudocode is intuitive, and the absence of rotations simplifies the implementation.
  • Flexibility
    • Skip lists are highly adaptable for various sizes of datasets. Unlike hash tables, which require resizing, or trees, which may need restructuring, skip lists gracefully handle dynamic insertion and deletion.
  • Predictable Behavior
    • Unlike hash tables, skip lists do not suffer from hash collisions. This predictability ensures stable performance, especially in applications with critical performance requirements.

Applications of Searching and Deleting Elements in Skip Lists

Skip lists are highly versatile and find applications in numerous fields, thanks to their efficient search and delete operations. Below are detailed examples of their applications:

  • Databases
    • Indexing: Skip lists are used to maintain sorted indices for efficient querying in databases.
    • Transaction Management: With dynamic operations like insertion and deletion, skip lists can quickly adjust indices in transactional systems.
    • Range Queries: The hierarchical traversal allows efficient range-based searches.
  • In-Memory Key-Value Stores
    • Redis: Skip lists are the backbone of Redis’s implementation of sorted sets. The efficient deletion mechanism ensures that removing keys is fast and does not degrade performance.
    • Caching Systems: Skip lists manage priority queues in caching algorithms like Least Recently Used (LRU).
  • Priority Queues
    • Efficient Management: Skip lists are ideal for implementing priority queues where elements frequently enter and leave the structure.
    • Dynamic Updates: Deletion operations are swift, allowing for real-time updates in priority-based systems.
  • Distributed Systems and Networking
    • Routing Tables: Skip lists are used in distributed hash tables (e.g., in systems like Chord) to maintain routing tables efficiently.
    • Load Balancing: Their dynamic nature makes them suitable for maintaining and updating task queues in load-balancing algorithms.
  • Online Gaming and Leaderboards
    • Ranked Data: Skip lists are excellent for maintaining and updating leaderboards dynamically, where players’ ranks change frequently.
    • Real-Time Updates: Searching and deleting operations ensure quick adjustments to scores and rankings.
  • Event Scheduling Systems
    • Efficient Management: Skip lists handle events dynamically, with operations like insertion, deletion, and searching happening in real-time.
    • Hierarchical Traversal: This allows systems to skip over irrelevant events and find the next scheduled event efficiently.
  • Search Engines
    • Index Optimization: Skip lists can optimize indexing and querying processes in search engines.
    • Dynamic Updates: They enable the efficient deletion of outdated links or documents, ensuring up-to-date search results.
  • Geographic Information Systems (GIS)
    • Spatial Indexing: Skip lists can be used to manage and query spatial data effectively.
    • Dynamic Adjustments: The ability to remove old or irrelevant data without performance degradation is critical in GIS applications.
  • Version Control Systems
    • Efficient Operations: Skip lists can be used to maintain version histories, where changes need to be quickly added or removed.
    • Hierarchical Representation: The multi-level structure allows for efficient traversal of versioned data.
  • Blockchain and Cryptocurrency
    • Ledger Management: Skip lists can maintain blockchain ledgers, especially in permissioned blockchains where transactions need dynamic insertion and deletion.
    • Efficient Lookups: Searching for specific transactions becomes faster, enabling real-time querying.

Conclusion

The search and delete operations in a skip list demonstrate the power and flexibility of this data structure. By leveraging its multi-level architecture, skip lists provide efficient mechanisms for locating and removing elements. These capabilities make skip lists a preferred choice for applications requiring fast and dynamic data access. With the above explanations, pseudocode, and implementations, you now have a thorough understanding of these essential operations.

  1. Skip List Introduction – Efficient Search, Insert, and Delete in Linked List
  2. Skip List Insertion: A Comprehensive Exploration
  3. Searching and Deleting Elements in Skip Lists: A Comprehensive Guide
  4. Searching an Element in a Skip List: A Detailed Exploration

Frequently Asked Questions (FAQs)

What is the main idea behind searching in a Skip List?

Searching in a skip list leverages its multi-level structure to quickly locate an element. The process starts at the highest level of the skip list and navigates through its nodes, making use of the following principles:

  • Horizontal Traversal: If the key of the next node is smaller than the search key, the algorithm moves forward at the same level.
  • Vertical Movement: If the key of the next node is greater than the search key, the algorithm moves down to the next lower level.
  • Final Verification: At the lowest level (level 0), the algorithm checks whether the node’s key matches the search key. If a match is found, the algorithm returns the corresponding node or value; otherwise, the search ends in failure.

This approach minimizes the number of comparisons by skipping over large sections of the list, which is the core strength of the skip list structure.

How does the Skip List ensure efficient searching compared to other data structures?

The skip list ensures efficiency by combining elements of linked lists and binary search trees:

  • Hierarchical Levels: Each level in a skip list acts as a “shortcut” to skip multiple nodes, reducing the traversal time.
  • Probabilistic Balancing: The levels in a skip list are determined probabilistically, maintaining a balanced structure without the need for complex rebalancing algorithms as seen in AVL trees or Red-Black trees.
  • Logarithmic Search Time: The expected time complexity for searching in a skip list is O(log n) due to the logarithmic number of levels and the efficient horizontal traversal at each level.

This makes skip lists ideal for applications requiring fast and dynamic data retrieval, such as databases and in-memory key-value stores.

Can you explain the pseudocode for the Skip List search operation?

Here’s a detailed explanation of the pseudocode:

Search(list, searchKey)
    x := list -> header
    for i := list -> level downto 0 do
        while x -> forward[i] -> key < searchKey do
            x := x -> forward[i]
    x := x -> forward[0]
    if x -> key = searchKey then 
        return x -> value
    else 
        return failure
  • Initialization: The search starts at the header node, which serves as the entry point for all levels of the skip list.
  • Top-to-Bottom Traversal: The algorithm iterates from the highest level down to level 0.
  • Forward Movement: At each level, the algorithm moves forward until the next node’s key is greater than or equal to the search key.
  • Final Check: At the lowest level, if the current node’s key matches the search key, the corresponding value is returned. Otherwise, the search ends in failure.

This pseudocode encapsulates the essence of hierarchical traversal, which is the hallmark of skip lists.

How do you delete an element from a Skip List?

Deleting an element from a skip list involves the following steps:

  • Locate the Node: Use the search algorithm to find the node to be deleted.
  • Pointer Adjustment: Starting from the lowest level, adjust the pointers of the preceding nodes to bypass the node being deleted.
  • Level Adjustment: After deletion, check if any levels have become empty. If so, decrement the level count of the skip list.

The algorithm ensures that the skip list remains compact and efficient after deletion, as empty levels are removed dynamically.

What is the pseudocode for the Delete operation in a Skip List?

Here’s the pseudocode for the delete operation:

Delete(list, searchKey)
    local update[0..MaxLevel+1]
    x := list -> header
    for i := list -> level downto 0 do
        while x -> forward[i] -> key < searchKey do
            x := x -> forward[i]
        update[i] := x
    x := x -> forward[0]
    if x -> key = searchKey then
        for i := 0 to list -> level do
            if update[i] -> forward[i] ≠ x then break
            update[i] -> forward[i] := x -> forward[i]
        free(x)
        while list -> level > 0 and list -> header -> forward[list -> level] = NIL do
            list -> level := list -> level – 1

The key aspects of this pseudocode are:

  • Update Array: Tracks the nodes whose pointers need adjustment during deletion.
  • Pointer Rearrangement: Ensures the target node is bypassed at every level where it exists.
  • Level Management: Removes any levels that become empty after the deletion operation.

What happens to empty levels after deleting an element?

After deleting an element, it is possible for some levels in the skip list to become empty. When this occurs:

  • The algorithm checks if the header node has no forward pointers at the highest level.
  • If no elements exist at a particular level, that level is removed by decrementing the level count of the skip list.

This dynamic level management ensures that the skip list maintains an optimal structure without wasting memory.

How does the Skip List compare to a Singly Linked List in deletion operations?

While both skip lists and singly linked lists use pointer rearrangement for deletion, skip lists offer significant advantages:

  • Multi-Level Traversal: Skip lists use hierarchical levels to quickly locate the node to be deleted, reducing traversal time to O(log n) compared to O(n) in a singly linked list.
  • Dynamic Level Adjustment: Skip lists automatically remove empty levels after deletion, maintaining their efficiency and compactness.
  • Scalability: Skip lists scale well for large datasets, whereas singly linked lists become inefficient as the size of the list grows.

What is the time complexity for searching and deleting in Skip Lists?

The time complexity for both searching and deleting in a skip list is O(log n) on average. This efficiency is achieved due to:

  • The logarithmic number of levels in the skip list.
  • The ability to skip over large sections of the list at each level.

In the worst case, the time complexity can degrade to O(n), but this is highly unlikely due to the probabilistic balancing of skip lists.

Why is the Skip List considered a probabilistic data structure?

The skip list is considered probabilistic because its structure is determined by randomization during insertion. Specifically:

  • Each node is assigned a level randomly, with the probability of a node having a higher level decreasing geometrically.
  • This randomness ensures that the skip list remains balanced without the need for explicit rebalancing algorithms.

This probabilistic nature gives skip lists their unique combination of simplicity and efficiency.

What are some real-world applications of Skip Lists?

Skip lists are widely used in applications requiring fast and efficient data access, such as:

  • Databases: For indexing and querying large datasets.
  • In-Memory Key-Value Stores: Like Redis, which uses skip lists for managing sorted sets.
  • Network Routing: In distributed systems, skip lists can be used to maintain routing tables.
  • Cache Systems: For efficiently managing priority queues and caches.

The combination of fast search, insertion, and deletion makes skip lists an excellent choice for these applications.

Share.
Examsmeta Logo

Examsmeta is your one-stop destination for comprehensive educational resources across a wide array of disciplines. At Examsmeta, we are dedicated to providing high-quality, topic-wise notes and articles that cater to students, educators, researchers, and lifelong learners. Our mission is to make learning accessible, engaging, and effective for everyone. Our mission is to empower learners by offering detailed, accurate, and up-to-date educational content. We strive to foster a love for learning and to support the academic and professional growth of our users. Whether you're preparing for exams, conducting research, or simply expanding your knowledge, Examsmeta is here to guide you every step of the way.