data_structure::SkipList Class Reference

Collaboration diagram for data_structure::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_structure::SkipList::SkipList ( )

inline

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

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

Member Function Documentation

deleteElement()

void data_structure::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_structure::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_structure::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::shared_ptr<Node>(new 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_structure::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_structure::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