Close Menu
Data Structures

Deleting an Element from a Skip List: A Detailed Exploration

By

The Skip List is a fascinating and efficient data structure that balances simplicity and performance for dynamic operations such as insertion, search, and deletion. In this guide, we focus on the deletion operation, which is a critical aspect of maintaining the integrity and efficiency of the skip list. Below, we delve into the principles, processes, and implementation details of deleting an element from a skip list, making this guide a thorough resource for learners and practitioners alike.

Also Read:

Understanding the Deletion Operation in Skip Lists

The deletion operation in a skip list is designed to remove a specified element while preserving the structure and efficiency of the list. Thanks to the hierarchical arrangement of nodes and levels, the skip list ensures that deletions are performed in logarithmic time on average. The procedure involves locating the target node, adjusting pointers, and managing the levels of the skip list.

Key Concepts of the Deletion Algorithm

  • Locating the Target Node
    • The first step in the deletion process is to find the node containing the key to be deleted. This is achieved using the search algorithm, which utilizes the forward pointers at different levels to locate the desired element efficiently.
  • Pointer Rearrangement
    • Once the target node is located, the forward pointers at all levels where the node exists are adjusted to bypass it. This step is analogous to pointer manipulation in a singly linked list, but it occurs across multiple levels in the skip list.
  • Level Adjustment
    • After removing the node, it is essential to ensure that the levels in the skip list remain valid. If a level becomes empty (i.e., no nodes have forward pointers at that level), the skip list’s maximum level is decremented, maintaining an optimal structure.

Detailed Explanation of the Deletion Process

Let’s break down the deletion operation into its core components, providing an in-depth understanding of each step:

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

Step 1: Locating the Target Node

The process begins by searching for the element to be deleted. This involves traversing the forward pointers from the topmost level of the skip list down to the bottom level. A temporary array, commonly referred to as update, is used to store the pointers to the nodes at each level that precede the target node. This array facilitates efficient pointer rearrangement in the next step.

For Example: If the skip list contains the elements 3, 6, 7, 9, 12, 17, 19, 21, 25, and 26, and we want to delete 6, we use the search algorithm to locate the node containing 6. The update array stores the preceding nodes at each level.

Step 2: Pointer Rearrangement

Once the target node is identified, the forward pointers of the nodes in the update array are modified to skip over the target node. This effectively removes the node from the skip list at all levels where it exists. After the pointers are adjusted, the target node is deallocated from memory.

Analogy: This step resembles removing an element from a singly linked list, where the next pointer of the preceding node is updated to bypass the target node.

For Example: For element 6, the forward pointers at all levels where 6 exists are updated to point to the node that follows 6, effectively bypassing and removing it from the list.

Step 3: Level Adjustment

After the node is removed, it is necessary to check if any levels in the skip list have become empty. If so, the maximum level of the skip list is decremented, ensuring that the structure remains optimized and efficient for future operations.

For Example: If the deletion of 6 results in an empty level 3, the maximum level of the skip list is reduced by 1.

Pseudocode for Deletion

The following pseudocode outlines the deletion operation in a skip list:

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

Code Implementation for 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.

Illustrative Example: Deleting Element 6

Let’s walk through the deletion of the element 6 in a skip list containing the keys 3, 6, 7, 9, 12, 17, 19, 21, 25, and 26.

  • Search for the Node
    • Using the search algorithm, locate the node containing the key 6. Identify the preceding nodes at each level and store them in the update array.
  • Rearrange Pointers
    • Modify the forward pointers of the nodes in the update array to bypass the node containing 6. This removes 6 from all levels where it exists.
  • Adjust Levels
    • After the deletion, check if any levels are empty. In this case, level 3 becomes empty, so the maximum level of the skip list is decremented by 1.

The skip list after deletion: 3, 7, 9, 12, 17, 19, 21, 25, and 26.

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 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;
}

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;
}

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

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

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

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 Deleting an Element from a Skip List

The deletion operation in a skip list offers numerous advantages due to the unique hierarchical design of the data structure. These benefits make skip lists a highly efficient and flexible tool for dynamic data management. Below is a detailed explanation of the advantages of performing a deletion operation in a skip list:

  • Logarithmic Time Complexity
    • The deletion operation in a skip list is highly efficient, with an average time complexity of O(log n). This is due to the hierarchical arrangement of nodes and levels, which allows for rapid traversal and pinpointing of the target node.
    • Why It Matters: In comparison to traditional data structures like a linked list, where deletion takes O(n) in the worst case, the logarithmic complexity of a skip list makes it ideal for applications requiring frequent dynamic updates.
  • Dynamic Level Adjustment
    • One of the standout advantages of the skip list is its ability to adjust levels dynamically during the deletion process. If a level becomes empty after the deletion of a node, the maximum level of the skip list is decremented. This keeps the structure compact and prevents unnecessary traversal of empty levels.
    • Example: After deleting an element, if the topmost level no longer has any forward pointers, it is removed, reducing the space and traversal overhead.
    • Benefit: This dynamic level adjustment ensures that the skip list remains balanced and efficient without requiring complex rebalancing algorithms, as seen in AVL trees or Red-Black trees.
  • Efficient Pointer Rearrangement
    • The hierarchical structure of the skip list enables efficient pointer manipulation. During the deletion process, only the forward pointers at levels where the node exists need to be updated, rather than traversing the entire list.
    • Comparison: Unlike a singly linked list, where finding and deleting a node requires traversing from the head to the target, the skip list optimizes this by reducing the traversal path through its layered design.
  • Minimal Overhead for Deletion
    • The deletion operation in a skip list incurs minimal overhead compared to other data structures like balanced binary trees or hash tables.
    • In Balanced Trees: Deletion may require costly rebalancing operations, which add complexity and increase runtime.
    • In Hash Tables: Deletion can lead to clustering and the need for rehashing, which affects performance.
    • In contrast, the skip list achieves deletion through straightforward pointer updates, making it a simpler and faster alternative.
  • No Need for Rehashing or Rebalancing
    • Unlike hash tables or balanced binary trees, a skip list does not require expensive rehashing or rebalancing operations. The hierarchical structure inherently adapts to deletions without affecting the overall efficiency of the data structure.
    • Impact: This makes the skip list particularly suited for applications where elements are frequently added or removed, such as priority queues or dynamic databases.
  • Supports Duplicate Keys
    • In implementations where duplicate keys are allowed, the skip list simplifies the deletion process by enabling the removal of multiple nodes with the same key efficiently. This flexibility is harder to achieve in other data structures without additional overhead.
  • Memory Efficiency
    • The deletion operation in a skip list is designed to free memory allocated to the removed node. This ensures that no unnecessary memory is consumed, preventing memory leaks and promoting efficient resource utilization.
    • In Programming Languages:
      • In C or C++, manual memory management via functions like free() ensures explicit deallocation.
      • In Java or Python, garbage collection handles memory cleanup, but the skip list’s explicit removal of references ensures the timely reclamation of resources.
  • Simplicity of Implementation
    • The algorithm for deleting an element from a skip list is straightforward and easy to implement. Unlike the intricate rebalancing algorithms required by AVL trees or Red-Black trees, the skip list achieves efficient deletion through simple pointer adjustments.
    • Key Takeaway: This simplicity makes the skip list a popular choice for developers who need a powerful yet easy-to-maintain data structure.
  • Predictable Performance
    • The deletion operation in a skip list provides consistent and predictable performance, as the hierarchical structure ensures logarithmic behavior in most cases. This is particularly advantageous in real-time systems and applications where performance consistency is critical.
  • Versatility in Applications
    • The efficient deletion process of a skip list makes it suitable for a wide range of applications, including:
      • Databases: Where records are frequently inserted and deleted.
      • Priority Queues: Where elements need to be dynamically removed based on their priority.
      • Caching Systems: Where stale or outdated entries are removed to maintain relevancy.

The ability to perform deletions quickly and efficiently ensures that skip lists remain versatile and effective in handling dynamic datasets.

Conclusion

The deletion operation in a skip list is a systematic and efficient process that leverages the hierarchical structure of the data structure. By locating the target node, rearranging pointers, and adjusting levels, the skip list maintains its efficiency and structural integrity. Understanding and implementing this operation is essential for anyone looking to master the skip list as a versatile and powerful data structure.

  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
  5. Deleting an Element from a Skip List: A Detailed Exploration

Frequently Asked Questions (FAQs)

What is the main purpose of the deletion operation in a skip list?

The deletion operation in a skip list is essential for maintaining the dynamic nature of the data structure. The primary purpose of this operation is to efficiently remove a specified element while ensuring that the overall structure of the skip list remains intact. Unlike a simple linked list, the hierarchical levels in a skip list enable faster operations by providing shortcuts through the data. The deletion operation ensures that these shortcuts are adjusted properly when an element is removed.

By rearranging the forward pointers and adjusting the levels of the skip list, the deletion operation guarantees that subsequent search, insertion, and deletion operations continue to operate with logarithmic time complexity. This makes the skip list a highly efficient alternative to traditional data structures like arrays and binary search trees.

How does the deletion operation begin?

The deletion operation begins with locating the target node to be deleted. This is achieved using the search algorithm, which starts at the topmost level of the skip list and traverses downward, level by level. During this traversal, an auxiliary array, typically called update, is used to keep track of the nodes that precede the target node at each level.

For example, if the skip list contains the elements 3, 6, 7, 9, 12, 17, 19, 21, 25, 26 and the target element is 6, the algorithm identifies the nodes preceding 6 at each level and stores them in the update array. These nodes will be crucial for rearranging the forward pointers after the node is located.

What is the role of the Update Array in the deletion operation?

The update array plays a vital role in the deletion operation. It is used to store the pointers to the nodes that immediately precede the target node at each level of the skip list. By maintaining these references, the algorithm ensures that the forward pointers can be efficiently rearranged to bypass the target node.

For Example: Suppose we want to delete the key 6 from a skip list. During the search phase, the update array will store references to the nodes containing 3 at all levels where 6 exists. These nodes are the ones whose forward pointers need to be adjusted to skip over the node containing 6.

Without the update array, the algorithm would require multiple traversals to locate the preceding nodes, significantly increasing the time complexity of the operation.

How are the forward pointers rearranged during the deletion process?

Rearranging the forward pointers is a critical step in the deletion process. Once the target node is identified, the algorithm uses the update array to modify the forward pointers of the preceding nodes. These pointers are updated to bypass the target node and point directly to the node following it.

For Example: If the skip list contains the sequence 3 → 6 → 7 → 9, and the node containing 6 is to be deleted, the forward pointer of the node containing 3 is updated to point to the node containing 7. This effectively removes 6 from the list.

This step is analogous to pointer manipulation in a singly linked list but is performed at multiple levels, ensuring that the hierarchical structure of the skip list remains consistent.

What happens to the memory of the deleted node?

After the forward pointers are rearranged to bypass the target node, the node itself is deallocated from memory. This step is crucial for preventing memory leaks, especially in programming languages like C and C++, where memory management is handled manually.

For Example: In C, the free() function is used to release the memory occupied by the target node. In modern languages like Java or Python, this step is typically handled by the garbage collector, but explicitly removing references to the node ensures that the memory is reclaimed.

Proper memory management during the deletion process ensures that the skip list remains efficient and does not consume unnecessary resources.

How are levels adjusted after a node is deleted?

Adjusting the levels of the skip list is an essential part of the deletion process. If the deletion of a node results in a level becoming empty (i.e., no nodes have forward pointers at that level), the maximum level of the skip list is decremented.

For Example: If the skip list has four levels and the deletion of the element 6 results in level 3 becoming empty, the maximum level of the list is reduced to level 2. This ensures that the structure of the skip list remains optimal and avoids unnecessary overhead during future operations.

What is the time complexity of the deletion operation in a skip list?

The deletion operation in a skip list has an average time complexity of O(log n), where n is the number of elements in the list. This efficiency is achieved due to the hierarchical structure of the skip list, which allows for logarithmic traversal during the search phase.

In the worst-case scenario, the time complexity remains logarithmic, provided that the levels are appropriately balanced. This makes the skip list a powerful alternative to other dynamic data structures like binary search trees and hash tables, which may exhibit linear time complexity in some cases.

How does the skip list handle empty levels after deletion?

After a node is deleted, the algorithm checks whether any levels in the skip list have become empty. An empty level is defined as one where the header node’s forward pointer for that level points to NIL or null. If such a level exists, the algorithm decrements the maximum level of the skip list.

For Example: If level 3 of a skip list becomes empty after deleting an element, the maximum level is reduced to level 2. This adjustment ensures that the skip list remains compact and efficient, avoiding unnecessary traversal of empty levels during future operations.

Can multiple nodes with the same key be deleted in a skip list?

In most implementations of a skip list, each key is unique, meaning that only one node corresponds to a given key. However, if the skip list allows duplicate keys, the deletion operation can be extended to remove multiple nodes with the same key.

Procedure:

  • Use the search algorithm to locate the first node containing the target key.
  • Rearrange the forward pointers to bypass this node.
  • Repeat the process for each subsequent node containing the same key.

Allowing duplicates in a skip list requires additional considerations for maintaining the balance and efficiency of the data structure.

How does the pseudocode implement the deletion operation?

The pseudocode for the deletion operation in a skip list provides a step-by-step approach:

  • Initialize the update array to store references to the preceding nodes at each level.
  • Locate the target node using the search algorithm.
  • If the target node exists:
    • Rearrange the forward pointers using the update array.
    • Free the memory occupied by the target node.
    • Adjust the maximum level of the skip list if necessary.

The pseudocode ensures that the deletion operation is performed efficiently and maintains the integrity of the skip list structure.

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.