Question

How is a Skip List implemented?

Answer 1

Implementing a Skip List involves creating the necessary data structures and defining functions to perform insertion, deletion, and search operations. Here's a basic implementation in C++:

#include <iostream>
#include <cstdlib>

// Node structure for Skip List
struct Node {
    int data;
    Node** forward; // Array of pointers to the next nodes at different levels

    // Constructor to initialize a node with a given data value and level
    Node(int value, int level) : data(value) {
        forward = new Node*[level + 1];
        std::fill_n(forward, level + 1, nullptr); // Initialize all pointers to nullptr
    }

    // Destructor to free the memory allocated for the array of pointers
    ~Node() {
        delete[] forward;
    }
};

// Skip List class
class SkipList {
private:
    int maxLevel;     // Maximum level of the Skip List
    Node* header;     // Header node with the smallest possible key
    int currentLevel; // Current highest level of the Skip List

public:
    // Constructor to initialize the Skip List
    SkipList(int maxLvl) : maxLevel(maxLvl), currentLevel(0) {
        // Create the header node
        header = new Node(-1, maxLevel);
    }

    // Destructor to free the memory allocated for the Skip List
    ~SkipList() {
        delete header;
    }

    // Function to generate a random level for a new node
    int randomLevel() {
        int lvl = 0;
        while (rand() % 2 && lvl < maxLevel) {
            lvl++;
        }
        return lvl;
    }

    // Function to insert a new element into the Skip List
    void insert(int value) {
        // Create update array to store pointers to nodes where levels are updated
        Node* update[maxLevel + 1];
        std::fill_n(update, maxLevel + 1, nullptr);

        // Start from the highest level and move down to the bottom level
        Node* current = header;
        for (int i = currentLevel; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->data < value) {
                current = current->forward[i];
            }
            update[i] = current; // Update array stores the node where level is updated
        }

        // Generate a random level for the new node
        int newLevel = randomLevel();

        // If the new node has a higher level than the current highest level, update the header
        if (newLevel > currentLevel) {
            for (int i = currentLevel + 1; i <= newLevel; i++) {
                update[i] = header;
            }
            currentLevel = newLevel;
        }

        // Create a new node with the given value and random level
        Node* newNode = new Node(value, newLevel);

        // Update pointers at each level
        for (int i = 0; i <= newLevel; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }

        std::cout << "Inserted element: " << value << " with level: " << newLevel << std::endl;
    }

    // Function to search for an element in the Skip List
    bool search(int value) {
        Node* current = header;

        // Start from the highest level and move down to the bottom level
        for (int i = currentLevel; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->data < value) {
                current = current->forward[i];
            }
        }

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

        // If the node contains the target value, return true; otherwise, return false
        return (current != nullptr && current->data == value);
    }

    // Function to display the elements of the Skip List
    void display() {
        std::cout << "Skip List:" << std::endl;
        for (int i = 0; i <= currentLevel; i++) {
            Node* current = header->forward[i];
            std::cout << "Level " << i << ": ";
            while (current != nullptr) {
                std::cout << current->data << " ";
                current = current->forward[i];
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    // Create a Skip List with a maximum level of 3
    SkipList skipList(3);

    // Insert elements into the Skip List
    skipList.insert(3);
    skipList.insert(6);
    skipList.insert(7);
    skipList.insert(9);
    skipList.insert(12);
    skipList.insert(19);
    skipList.insert(17);
    skipList.insert(26);
    skipList.insert(21);
    skipList.insert(25);

    // Display the Skip List
    skipList.display();

    // Search for elements in the Skip List
    std::cout << "Search for 19: " << (skipList.search(19) ? "Found" : "Not Found") << std::endl;
    std::cout << "Search for 20: " << (skipList.search(20) ? "Found" : "Not Found") << std::endl;

    return 0;
}
 

This example demonstrates a basic implementation of a Skip List in C++. The SkipList class includes functions for insertion, search, and display. The Node structure represents individual nodes in the Skip List, and the randomLevel function is used to generate a random level for new nodes during insertion. The display function prints the Skip List at each level.

Remember that this implementation is simplified, and production-level implementations might include additional features and optimizations.