SkipList

skip_list.h

#ifndef SKIP_LIST_H
#define SKIP_LIST_H

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

class SkipList {
 public:
  SkipList(int max_level = 16);
  ~SkipList();

  void Insert(int value);
  void Delete(int value);
  bool Search(int value) const;
  std::vector<int> Traverse() const;
  void Print() const;

 private:
  struct Node {
    int value;
    std::vector<Node*> forward;

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

  Node* CreateNode(int value, int level);
  int RandomLevel();

  Node* header_;
  int max_level_;
  int level_;
  float probability_;

  static const int MINUS_INFINITY = std::numeric_limits<int>::min();
};

#endif  // SKIP_LIST_H

skip_list.cc

#include "skip_list.h"

SkipList::SkipList(int max_level)
    : max_level_(max_level), level_(0), probability_(0.5f) {
  header_ = new Node(MINUS_INFINITY, max_level_);
  std::srand(
      static_cast<unsigned>(std::time(nullptr)));  // Initialize random seed
}

SkipList::~SkipList() {
  Node* current = header_;
  while (current != nullptr) {
    Node* next = current->forward[0];
    delete current;
    current = next;
  }
}

void SkipList::Insert(int value) {
  std::vector<Node*> update(max_level_, nullptr);
  Node* current = header_;

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

  current = current->forward[0];

  if (current == nullptr || current->value != value) {
    int new_level = RandomLevel();
    if (new_level > level_) {
      for (int i = level_ + 1; i <= new_level; ++i) {
        update[i] = header_;
      }
      level_ = new_level;
    }

    Node* new_node = CreateNode(value, new_level + 1);
    for (int i = 0; i <= new_level; ++i) {
      new_node->forward[i] = update[i]->forward[i];
      update[i]->forward[i] = new_node;
    }
  }
}

void SkipList::Delete(int value) {
  std::vector<Node*> update(max_level_, nullptr);
  Node* current = header_;

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

  current = current->forward[0];

  if (current != nullptr && current->value == value) {
    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_--;
    }
  }
}

bool SkipList::Search(int value) const {
  Node* current = header_;
  for (int i = level_; i >= 0; --i) {
    while (current->forward[i] != nullptr &&
           current->forward[i]->value < value) {
      current = current->forward[i];
    }
  }
  current = current->forward[0];
  return current != nullptr && current->value == value;
}

std::vector<int> SkipList::Traverse() const {
  std::vector<int> values;
  Node* current = header_->forward[0];
  while (current != nullptr) {
    values.push_back(current->value);
    current = current->forward[0];
  }
  return values;
}

void SkipList::Print() const {
  for (int i = max_level_; i >= 0; --i) {
    Node* ptr = header_;
    while (ptr != nullptr) {
      if (ptr == header_) {
        if (ptr->forward[i] == nullptr) {
          goto BRK;
        }

        std::cout << "level_" << i << ":";

      } else {
        if (ptr->forward.size() >= i + 1) {
          std::cout << ptr->value;
        } else {
          std::cout << " ";
        }
      }

      std::cout << "\t";
      ptr = ptr->forward[0];
    }
    std::cout << std::endl;

  BRK:;
  }

  Node* ptr = header_;
  while (ptr != nullptr) {
    if (ptr == header_) {
      std::cout << "[hight]\t";
    } else {
      std::cout << "[" << ptr->forward.size() << "]";
    }

    std::cout << "\t";
    ptr = ptr->forward[0];
  }
  std::cout << std::endl << std::endl;
}

SkipList::Node* SkipList::CreateNode(int value, int level) {
  return new Node(value, level);
}

int SkipList::RandomLevel() {
  int level = 0;
  while (static_cast<float>(std::rand()) / RAND_MAX < probability_ &&
         level < max_level_ - 1) {
    level++;
  }
  return level;
}