Interactive Programming Education Platform

Logic Practice

Skip list is a type of data structure that provides an effective method for searching, adding, and removing elements within a sorted series. William Pugh introduced it in 1989 as a substitute for balanced trees, offering comparable average case performance metrics with a more straightforward implementation approach.

Problem Statement:

Challenges frequently occur when managing extensive data collections that necessitate searching, inserting, or deleting elements utilizing arrays or linked lists. Typically, these methods exhibit a linear time complexity. While achieving a logarithmic time complexity for these operations is feasible with balanced trees such as AVL trees and red-black trees, the complexity of implementing and maintaining them can be considerably intricate.

These challenges are effectively addressed by skip lists by incorporating randomness into the data structure. Skip lists utilize several interconnected lists with different skip distances, facilitating quicker search operations, which is particularly beneficial in scenarios where rapid searches are crucial, like in database management systems and online search platforms.

In this tutorial, we are going to explore the intricacies of skip lists and develop a basic implementation in C++. Additionally, we will delve into the key concepts and procedures for searching, inserting, and removing elements, providing a practical demonstration of each operation. To start, let's delve into the significance of skip lists and the reasons behind their utility in the realm of data structures.

Program:

Let's consider a C++ program to demonstrate the Skip List data structure.

Example


#include <iostream>
#include <cstdlib>
#include <ctime>
#include<cstring>

const int MAX_LEVEL = 6; // Maximum level for the skip list

// Node structure for skip list
struct Node {
    int key;
    Node** forward;

    Node(int k, int level) {
        key = k;
        forward = new Node*[level + 1];
        memset(forward, 0, sizeof(Node*) * (level + 1));
    }

    ~Node() {
        delete[] forward;
    }
};

// Skip list structure
class SkipList {
private:
    Node* header;
    int level;
    float p; // Probability factor for levels

public:
    SkipList() {
        header = new Node(-1, MAX_LEVEL);
        level = 0;
        p = 0.5; // Adjust this value based on dataset size
        srand(time(0)); // Seed for random number generation
    }

    ~SkipList() {
        delete header;
    }

    // Generate random level for a new node
    int randomLevel() {
        int lvl = 0;
        float r = (float)rand() / RAND_MAX;
        while (r < p && lvl < MAX_LEVEL) {
            lvl++;
            r = (float)rand() / RAND_MAX;
        }
        return lvl;
    }

    // Insert a key into the skip list
    void insert(int key) {
        Node* current = header;
        Node* update[MAX_LEVEL + 1];
        memset(update, 0, sizeof(Node*) * (MAX_LEVEL + 1));

        for (int i = level; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->key < key) {
                current = current->forward[i];
            }
            update[i] = current;
        }

        current = current->forward[0];

        if (current == nullptr || current->key != key) {
            int newLevel = randomLevel();
            if (newLevel > level) {
                for (int i = level + 1; i <= newLevel; i++) {
                    update[i] = header;
                }
                level = newLevel;
            }

            Node* newNode = new Node(key, newLevel);

            for (int i = 0; i <= newLevel; i++) {
                newNode->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = newNode;
            }
        }
    }

    // Search for a key in the skip list
    bool search(int key) {
        Node* current = header;
        for (int i = level; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->key < key) {
                current = current->forward[i];
            }
        }
        current = current->forward[0];
        return (current != nullptr && current->key == key);
    }

    // Delete a key from the skip list
    void remove(int key) {
        Node* current = header;
        Node* update[MAX_LEVEL + 1];
        memset(update, 0, sizeof(Node*) * (MAX_LEVEL + 1));

        for (int i = level; i >= 0; i--) {
            while (current->forward[i] != nullptr && current->forward[i]->key < key) {
                current = current->forward[i];
            }
            update[i] = current;
        }

        current = current->forward[0];

        if (current != nullptr && current->key == key) {
            for (int i = 0; i <= level; i++) {
                if (update[i]->forward[i] != current) {
                    break;
                }
                update[i]->forward[i] = current->forward[i];
            }
            delete current;

            while (level > 0 && header->forward[level] == nullptr) {
                level--;
            }
        }
    }

    // Display the skip list
    void display() {
        std::cout << "Skip List" << std::endl;
        for (int i = 0; i <= level; i++) {
            Node* node = header->forward[i];
            std::cout << "Level " << i << ": ";
            while (node != nullptr) {
                std::cout << node->key << " ";
                node = node->forward[i];
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    SkipList skipList;
    skipList.insert(3);
    skipList.insert(6);
    skipList.insert(7);
    skipList.insert(9);
    skipList.insert(12);
    skipList.insert(19);
    skipList.insert(17);
    skipList.display();

    std::cout << "Searching for 9: " << (skipList.search(9) ? "Found" : "Not Found") << std::endl;
    std::cout << "Searching for 15: " << (skipList.search(15) ? "Found" : "Not Found") << std::endl;

    skipList.remove(9);
    skipList.display();

    std::cout << "Searching for 9: " << (skipList.search(9) ? "Found" : "Not Found") << std::endl;

    return 0;
}

Output:

Output


Skip List
Level 0: 3 6 7 9 12 17 19 
Level 1: 7 12 17 
Searching for 9: Found
Searching for 15: Not Found
Skip List
Level 0: 3 6 7 12 17 19 
Level 1: 7 12 17 
Searching for 9: Not Found

Explanation:

Node Structure:

✅ Each node of a skip list has key (integer in this case) and an array of pointers called forward .
✅ The forward array is allocated dynamically depending on the maximum level of the skip list.

SkipList Class:

✅ This class manages the structure and operations of the skip list.
✅ It includes a pointer to its header node, an integer for tracking the current level of the skip list, and a probability factor p as a floating-point number used in determining levels of nodes.
✅ In order to initialize header node, set initial level to 0 and seed random number generator for level generation.
✅ Destructor should delete header node along with its associated memory to ensure proper cleanup is done for memory.

Random Level Generation:

✅ The randomLevel function generates a random level for a new node based on the probability factor p.
✅ It uses rand function to generate a random float between 0 and 1 that it compares with p incrementing level as long as randomized value is greater or equal to p or maximum level is reached.

Insertion Operation:

✅ The insert(int key) function inserts a new node with the given key into the skip list structure.
✅ Traversal starts from headernode , while updating forwarding pointers to find the correct position for insertion through levels.
✅ If the key already exists, its node is updated with a new value; otherwise, it creates another node and adjusts levels accordingly.

Search Operation:

✅ The search(int key) function searches for a key in the skip list.
✅ It starts from the header node and moves downwards through various levels while comparing keys until it encounters a match or reaches the end of that level.

Deletion Operation:

✅ The remove(int key) function removes a node having any specified key from skip list.
✅ As in insertion, it goes through each level to find the node being removed, modifies forward pointers of the previous nodes and de-allocates memory of deleted node as well.

Display Function:

✅ The display function will output contents of skiplist showing each level and each present Key in it.

Main Function:

✅ In the main function, an instance of the SkipList class is created.
✅ Multiple keys are inserted into the skiplist, and then search and removal are shown to ensure the skiplist works correctly.

Time and Space Complexities:

Time Complexity:

✅ Search Operation (Average Case): O (log n) , where n is the number of elements in the skip list. The average case time complexity comes due to structure of skip-list which has many layers for faster traversal to reach an element.
✅ Insertion operation (Average Case): O (log n) like search operation, uses traversing multiple levels to find the right position for insertion.
✅ Deletion Operation (Average Case): O (log n) also involves traversing multiple levels in order to find the node to be deleted.

Note: The above time complexities are average-case scenarios, assuming a well-balanced skip list with a suitable probability factor for level generation (p).

Space Complexity:

✅ The space complexity of a skip list is dependent on how many elements that it holds and the maximum level of the skip list.
✅ For a skiplist with n elements having at most m levels, the space complexity is O(n * m) because each node has pointers to each upward level up to the highest one.
✅ However, given that maximum height (m) is typically kept small (e.g. 16 or less in practice), compared to other balanced tree data structures such as AVL trees or red-black trees, skip lists have moderate overhead in terms of space.

Features of Skip List:

There are several features of the Skip List in C++. Some main features of the Skip List are as follows:

✅ Efficient Search Operations: Skip lists allow fast searches with an average-case time complexity of O(log n) . This efficiency is achieved using many levels of linked lists so that finding the desired element becomes quick.
✅ Balanced Structure: Unlike simple linked lists whose search times can go up to linear complexity, skip lists always maintain a balanced structure mainly because of random level generation. As such, these operations are characterized by logarithmic time complexity on average and thus appropriate for large data sets.
✅ Probabilistic Approach: During insertion, skip list uses a probabilistic method to determine the level at which each node will be placed thereby making nodes evenly distributed across levels. This randomness makes skip lists balanced and simplifies its implementation compared to its counterparts, balanced tree structures.
✅ Ease of Implementation: When compared to intricate balanced tree structures, such as AVL trees or red-black trees, skip list is relatively simpler. In fact, its logic for insertion, search and deletion operations is easy making it friendly to developers in general.
✅ Skip lists are flexible in terms of adjusting such parameters as the maximum level and probability factor for level generation (p) . Developers can adjust these parameters based on specific needs for performance and properties of data sets.
✅ Skip lists have a wide range of applications where sorted data management is required. Examples include databases, cache systems, priority queues etc. They achieve a good combination between simplicity, efficiency, and scalability.
✅ The average case time complexity of skip lists for search, insert and delete operations make them attractive in situations that require fast accessing or modifying of sorted data.

Disadvantages of Skip List:

There are several disadvantages of the Skip List in C++. Some main disadvantages of the Skip List are as follows:

✅ More Space Overhead: Compared to simpler data structures like arrays or linked lists, skip lists have higher space overheads. This is because every node has pointers to multiple levels especially if it is a high maximum level skip list.
✅ Unpredictable Nature: Randomness in performance arises from the probabilistic behaviour of Skip List. Although their average case time complexities are well-characterized, the actual performance depends on key distribution and randomness in level generation.
✅ The Complexity of Implementation: Even though skip lists are generally easier to implement than balanced trees, such as AVL trees or red-black trees, they still require careful manipulation of pointers and levels. This complexity can be heightened when one is dealing with optimizations or advanced features.
✅ Not for In-Place Operations: Skip lists do not lend themselves well to in-place operations or cases where memory utilization is imperative. The extra pointers and levels make it challenging to effect changes in place and create increased memory usage.
✅ Limited Applications: Skip lists work best in situations where there is a need for efficient search, insertion, and deletion functions especially when huge sorted data sets are involved. Other data access patterns or special requirements may call for other data structures.
✅ Performance Variations: Although skip lists provide fast average case performance, their worst-case time complexities may be higher compared to some other data structures. For applications needing a consistent predictable performance at all times, it might not always be the best option.

Conclusion:

In summary, skip lists are a versatile and efficient probabilistic data structure that offers fast search, insertion, and deletion operations with an average time complexity of O(log n). They were designed as alternatives to traditional balanced tree structures like red-black trees and AVL trees, aiming to achieve comparable performance with simpler development and maintenance processes.

Skip List In C++