A skip list in C++ is a data structure that allows fast search, insertion, and deletion operations through multiple linked lists at different levels, providing an efficient alternative to balanced trees.
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
class SkipListNode {
public:
int value;
std::vector<SkipListNode*> forward;
SkipListNode(int level, int value) : value(value), forward(level + 1, nullptr) {}
};
class SkipList {
private:
int maxLevel;
float p;
SkipListNode* header;
int randomLevel() {
int level = 0;
while ((rand() % 100) < (p * 100) && level < maxLevel) level++;
return level;
}
public:
SkipList(int maxLevel, float p) : maxLevel(maxLevel), p(p) {
header = new SkipListNode(maxLevel, -1);
}
void insert(int value) {
std::vector<SkipListNode*> update(maxLevel + 1, nullptr);
SkipListNode* current = header;
for (int i = maxLevel; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < value) {
current = current->forward[i];
}
update[i] = current;
}
current = current->forward[0];
if (!current || current->value != value) {
int level = randomLevel();
SkipListNode* newNode = new SkipListNode(level, value);
for (int i = 0; i <= level; i++) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
}
void display() {
for (int i = 0; i <= maxLevel; i++) {
SkipListNode* node = header->forward[i];
std::cout << "Level " << i << ": ";
while (node) {
std::cout << node->value << " ";
node = node->forward[i];
}
std::cout << std::endl;
}
}
};
int main() {
srand(time(nullptr));
SkipList list(3, 0.5);
list.insert(3);
list.insert(6);
list.insert(7);
list.insert(9);
list.insert(12);
list.insert(19);
list.display();
return 0;
}
What is a Skip List?
A skip list is a probabilistic data structure that provides an efficient way to maintain a sorted sequence of elements. It achieves rapid search, insertion, and deletion processes, similar to balanced trees but with a more straightforward design. Designed by William Pugh in 1989, skip lists utilize a hierarchy of linked lists, where each level acts like an express lane for elements, allowing for faster access.
Advantages of Skip Lists:
- Expected O(log n) time complexity for insertion, deletion, and searching.
- Easier to implement compared to balanced trees.
- Provides a clear and straightforward approach to maintaining sorted data.
Importance of Skip Lists in C++
Skip lists are significant in C++ for various reasons, foremost among them is their performance. As computer systems increasingly require quick access to data, skip lists offer a balanced alternative.
Performance: The expected time complexity for operations in skip lists is O(log n) on average, making them highly efficient for large datasets. This performance is especially beneficial for applications that require frequent updates.
Use Cases:
- Databases: Skip lists can efficiently manage indices.
- Memory Management: They are valuable in applications that require dynamic allocation and deallocation.
- Multi-threaded environments: Their structure lends itself well to concurrent modifications.
Understanding the Structure of a Skip List
Basic Components of a Skip List
At its core, a skip list consists of nodes connected by forward pointers.
Nodes: Each node contains a value and an array of pointers that represent its forward links to other nodes at various levels.
Sentinels: A special node often used at the head of the skip list to represent the lowest boundary, making it easier to handle edge cases during operations.
Layers of a Skip List
A skip list has multiple levels, where each level allows nodes to be skipped during traversal, effectively lowering search time.
Level Representation: Each node has a variable number of forward pointers, with some nodes appearing in higher levels than others. This setup creates a multi-layered linked list.
Randomization: The number of levels a node can have is determined randomly, which ensures an even distribution of nodes across levels, helping maintain efficient access times.
Implementation of Skip List in C++
C++ Node Structure
To implement a skip list, we first define the basic structure of its nodes. Each node should store its value and an array of pointers pointing to the nodes on the next level.
struct Node {
int value;
Node** forward; // Array of pointers to represent connections
Node(int level, int value) {
forward = new Node*[level + 1];
this->value = value;
}
};
In this code snippet, each node dynamically allocates an array of pointers that will be utilized for linking to other nodes across various levels.
Creating a Skip List Class
Next, we create a SkipList class that encapsulates the logic for managing skip lists. This class should include management of the head node, the maximum level, and the probability factor for level generation.
Class Definition
class SkipList {
private:
Node* head; // Sentinel node
int maxLevel;
float p;
public:
SkipList(int maxLevel, float probability);
void insert(int value);
void remove(int value);
bool search(int value);
};
This class design sets up an infrastructure for skip list functionalities.
Power Function for Level Generation
Randomness is crucial for creating new nodes at varying levels. The following function illustrates how we can implement this.
int randomLevel() {
int level = 0;
while (rand() % 2 == 0) { // 50% chances to increase level
level++;
}
return level;
}
By using a random number generator, nodes can get assigned different levels, promoting an even distribution across the list.
Operations on Skip Lists
Insertion
Inserting elements into a skip list involves positioning them correctly across levels. We traverse the list, identify the correct location, and insert the new node.
void insert(int value) {
Node *current = head;
Node *update[maxLevel + 1];
for (int i = maxLevel; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < value) {
current = current->forward[i];
}
update[i] = current; // Store the last node for each level
}
current = current->forward[0]; // Move to the next node
if (!current || current->value != value) { // Check if the value exists
int newLevel = randomLevel();
if (newLevel > maxLevel) { // Increase the list's max level
for (int i = maxLevel + 1; i <= newLevel; i++) {
update[i] = head;
}
maxLevel = newLevel;
}
Node* newNode = new Node(newLevel, value);
for (int i = 0; i <= newLevel; i++) {
newNode->forward[i] = update[i]->forward[i]; // Link the new node
update[i]->forward[i] = newNode;
}
}
}
In this implementation, we traverse down the list to locate where the new value should go. We then insert a new node and adjust links accordingly.
Deletion
Removing nodes requires identifying the node and re-linking the affected pointers.
void remove(int value) {
Node *current = head;
Node *update[maxLevel + 1];
for (int i = maxLevel; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < value) {
current = current->forward[i];
}
update[i] = current; // Store nodes for linking
}
current = current->forward[0];
if (current && current->value == value) { // Confirm the value's existence
for (int i = 0; i <= maxLevel; i++) {
if (update[i]->forward[i] != current) break;
update[i]->forward[i] = current->forward[i]; // Bypass the node
}
delete current; // Free memory
}
}
This code carefully navigates to the target node and updates the forward pointers to remove the targeted node from the structure.
Searching
Searching for a node involves traversing the list while utilizing the pointer levels for efficient access.
bool search(int value) {
Node *current = head;
for (int i = maxLevel; i >= 0; i--) {
while (current->forward[i] && current->forward[i]->value < value) {
current = current->forward[i];
}
}
current = current->forward[0]; // Move to the next node
return current && current->value == value; // Check existence
}
This function checks each level, skipping nodes as necessary to find the specified value quickly.
Performance Analysis
Time Complexity
The expected time complexity for insertion, deletion, and search operations in a skip list is O(log n) on average. In the worst case, all operations could degrade to O(n), but the randomized nature generally maintains efficiency.
Space Complexity
The space complexity of a skip list is O(n), primarily due to its node structure. The extra space used for forward pointers can vary depending on the number of levels assigned to nodes but remains efficient compared to many traditional data structures.
Conclusion
Skip lists provide a remarkably effective method for handling sorted data, marrying simplicity and efficiency. With an expected logarithmic performance in essential operations, they serve well in various applications, from database management to concurrent programming. The approachable implementation in C++ makes skip lists an excellent choice for programmers looking to bolster their knowledge of data structures.
References
For those interested in further exploration, consider diving into more detailed texts on data structures or checking out online coding platforms and forums specializing in algorithm discussions and implementations.
