data_structures::SkipList Class Reference

Collaboration diagram for data_structures::SkipList:

Public Member Functions
	SkipList ()
int	randomLevel ()
void	insertElement (int key, void *value)
void	deleteElement (int key)
void *	searchElement (int key)
void	displayList ()

Private Attributes
int	level
	Maximum level of the skiplist.
std::shared_ptr< Node >	header
	Pointer to the header node.

Detailed Description

SkipList class implementation with basic methods

Constructor & Destructor Documentation

SkipList()

data_structures::SkipList::SkipList ( )

inline

Skip List constructor. Initializes header, start Node for searching in the list

               {
        level = 0;
        // Header initialization
        header = std::make_shared<Node>(-1, MAX_LEVEL);
    }

Member Function Documentation

deleteElement()

void data_structures::SkipList::deleteElement ( int key )

inline

Deletes an element by key and prints if has been removed successfully

Parameters

key	is number that is used for comparision.

                                {
        std::shared_ptr<Node> x = header;
 
        std::array<std::shared_ptr<Node>, MAX_LEVEL + 1> update;
        update.fill(nullptr);
 
        for (int i = level; i >= 0; i--) {
            while (x->forward[i] != nullptr && x->forward[i]->key < key) {
                x = x->forward[i];
            }
            update[i] = x;
        }
 
        x = x->forward[0];
 
        bool doesnt_exist = (x == nullptr || x->key != key);
 
        if (!doesnt_exist) {
            for (int i = 0; i <= level; i++) {
                if (update[i]->forward[i] != x) {
                    break;
                }
                update[i]->forward[i] = x->forward[i];
            }
            /* Remove empty levels*/
            while (level > 0 && header->forward[level] == nullptr) level--;
            std::cout << "Deleted" << std::endl;
        } else {
            std::cout << "Doesn't exist" << std::endl;
        }
    }

Here is the call graph for this function:

displayList()

void data_structures::SkipList::displayList ( )

inline

Display skip list level

                       {
        std::cout << "Displaying list:\n";
        for (int i = 0; i <= level; i++) {
            std::shared_ptr<Node> node = header->forward[i];
            std::cout << "Level " << (i) << ": ";
            while (node != nullptr) {
                std::cout << node->key << " ";
                node = node->forward[i];
            }
            std::cout << std::endl;
        }
    }

Here is the call graph for this function:

insertElement()

void data_structures::SkipList::insertElement ( int key, void * value )

inline

Inserts elements with given key and value; It's level is computed by randomLevel() function.

Parameters

key	is number that is used for comparision
value	pointer to a value, that can be any type

                                             {
        std::cout << "Inserting" << key << "...";
        std::shared_ptr<Node> x = header;
        std::array<std::shared_ptr<Node>, MAX_LEVEL + 1> update;
        update.fill(nullptr);
 
        for (int i = level; i >= 0; i--) {
            while (x->forward[i] != nullptr && x->forward[i]->key < key) {
                x = x->forward[i];
            }
            update[i] = x;
        }
 
        x = x->forward[0];
 
        bool doesnt_exist = (x == nullptr || x->key != key);
        if (doesnt_exist) {
            int rlevel = randomLevel();
 
            if (rlevel > level) {
                for (int i = level + 1; i < rlevel + 1; i++) update[i] = header;
 
                // Update current level
                level = rlevel;
            }
 
            std::shared_ptr<Node> n =
                std::make_shared<Node>(key, rlevel, value);
            for (int i = 0; i <= rlevel; i++) {
                n->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = n;
            }
            std::cout << "Inserted" << std::endl;
 
        } else {
            std::cout << "Exists" << std::endl;
        }
    }

Here is the call graph for this function:

randomLevel()

int data_structures::SkipList::randomLevel ( )

inline

Returns random level of the skip list. Every higher level is 2 times less likely.

Returns

random level for skip list

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

Here is the call graph for this function:

searchElement()

void * data_structures::SkipList::searchElement ( int key )

inline

Searching element in skip list structure

Parameters

key	is number that is used for comparision

Returns

pointer to the value of the node

                                 {
        std::shared_ptr<Node> x = header;
        std::cout << "Searching for " << key << std::endl;
 
        for (int i = level; i >= 0; i--) {
            while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
        }
 
        x = x->forward[0];
        if (x && x->key == key) {
            std::cout << "Found" << std::endl;
            return x->value;
        } else {
            std::cout << "Not Found" << std::endl;
            return nullptr;
        }
    }

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• data_structures/skip_list.cpp