SkipList class implementation with basic methods
◆ SkipList()
data_structures::SkipList::SkipList |
( |
| ) |
|
|
inline |
Skip List constructor. Initializes header, start Node for searching in the list
◆ 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. |
137 update.fill(
nullptr);
139 for (
int i =
level; i >= 0; i--) {
140 while (x->forward[i] !=
nullptr && x->forward[i]->key < key) {
148 bool doesnt_exist = (x ==
nullptr || x->key != key);
151 for (
int i = 0; i <=
level; i++) {
152 if (update[i]->forward[i] != x) {
155 update[i]->forward[i] = x->forward[i];
◆ displayList()
void data_structures::SkipList::displayList |
( |
| ) |
|
|
inline |
Display skip list level
193 for (
int i = 0; i <=
level; i++) {
196 while (
node !=
nullptr) {
◆ 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 |
96 for (
int i =
level; i >= 0; i--) {
97 while (x->forward[i] !=
nullptr && x->forward[i]->key < key) {
105 bool doesnt_exist = (x ==
nullptr || x->key != key);
109 if (rlevel >
level) {
110 for (
int i =
level + 1; i < rlevel + 1; i++) update[i] =
header;
117 std::make_shared<Node>(key, rlevel, value);
118 for (
int i = 0; i <= rlevel; i++) {
119 n->forward[i] = update[i]->forward[i];
120 update[i]->forward[i] = n;
◆ 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
◆ 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
174 for (
int i =
level; i >= 0; i--) {
175 while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
179 if (x && x->key == key) {
The documentation for this class was generated from the following file: