skip-list

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

const float P = 0.5;
const int MAX_LEVEL = 16;

template<typename T>
class Node {
public:
    T value;
    std::vector<Node<T>*> forward;

    Node(int level, const T &value)
        : value(value), forward(level, nullptr) {}
};

template<typename T>
class SkipList {
public:
    SkipList() : level(0), header(new Node<T>(MAX_LEVEL, T())) {
        std::srand(std::time(nullptr));
    }

    ~SkipList() {
        Node<T>* curr = header->forward[0];
        while (curr != nullptr) {
            Node<T>* tmp = curr;
            curr = curr->forward[0];
            delete tmp;
        }
        delete header;
    }

    void insert(const T &value) {
        Node<T>* curr = header;
        std::vector<Node<T>*> update(MAX_LEVEL, nullptr);

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

        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; ++i) {
                update[i] = header;
            }
            level = newLevel;
        }

        Node<T>* newNode = new Node<T>(newLevel + 1, value);
        for (int i = 0; i <= newLevel; ++i) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }

    bool contains(const T &value) {
        Node<T>* curr = header;
        for (int i = level; i >= 0; --i) {
            while (curr->forward[i] != nullptr && curr->forward[i]->value < value) {
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        return curr != nullptr && curr->value == value;
    }

    void remove(const T &value) {
        Node<T>* curr = header;
        std::vector<Node<T>*> update(MAX_LEVEL, nullptr);

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

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

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

private:
    int level;
    Node<T>* header;

    int randomLevel() {
        int lvl = 0;
        while (std::rand() / static_cast<float>(RAND_MAX) < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }
};

int main() {
    SkipList<int> list;

    list.insert(3);
    list.insert(6);
    list.insert(7);
    list.insert(9);
    list.insert(12);

    std::cout << "Contains 3: " << list.contains(3) << std::endl;
    std::cout << "Contains 4: " << list.contains(4) << std::endl;

    list.remove(6);
    std::cout << "Contains 6: " << list.contains(6) << std::endl;

    return 0;
}