Why skip list??
In a sorted linked list :
- search : O(n)
- update : O(1) (after search)
In a sorted array
- search : O(log(n)) (binary search)
- Update : O(n)
So, skip list is basically a combination of advantages of both data structure.
As the name suggests Skip List is a data structure that allows for fast search, insertion, and deletion of elements in a sorted sequence, similar to a linked list. It achieves this by maintaining multiple layers of linked lists with skip pointers, allowing for more efficient search operations.
With linked list we were able to update efficiently but now we need to speed up the searching we introduce some shortcuts.
Suppose we have a skip list :
Here, each level has exactly half the number of nodes as the level below it as we have simply skipped the alternative nodes and this is known as Perfect skip list
So, if we want to search node with value 50 we will check that if head->next >val is true then we will go down else we will go right.
Here is the visualization : Currently head is pointing to -inf
we will start from L2 and see that if 40(head->next) > 50 which is false so go right now our head is 40.
Now again we will check that inf(head->next) > 50 which is true so we will go down now our head is 40.
Now again we will check that 60(head->next) > 50 which is true so we will go down now our head is 40.
Now again we will check that 50(head->next) > 50 which is true and we will return our answer.
Here we can see that our number of steps for searching node has been decreased and we can now search in O(log(n)) time.
But what if I say that it is not practically possible to maintain a perfect skip list where you are ensuring that only the alternate nodes are promoted to the next level.
Because suppose if I want to insert a node with value 55.
Lets see what happen now
When we inserted the node 55 our concept of promoting alternative node is disturbed and it not feasible and practical to maintain it after every insertion and deletion.
And here comes the concept of Randomization
Here randomness is introduced during the insertion process to determine whether a newly added node should be promoted to higher levels. This randomness helps achieve a balanced and efficient structure without the need for precise adjustments during insertions, making the data structure more adaptive and suitable for dynamic datasets.
Search Operation
Now if we want to search node with value 40:
Here the time complexity will not be exactly O(log(n)) as there can be more comparisions in the upper levels.
Insert Operation
Suppose we want to insert node with value 55.
So, first we need to search node just smaller value than 55 and then we will insert that node.
Now, we need to decide whether to elevate this node to the top level. To make this decision, we'll flip a fair coin, where the probability of getting heads or tails is 1/2. If the result is heads, we'll promote it to the top level; if it's tails, we won't promote it.
So, when we toss coin 1 time it results in head and again on 2nd time - head so we will promote our node 2 level up.
Now the question should be that what if we toss for the 3rd time ans again its a head??
So, no issues we will simply promote it to one level up and now we will have 3 levels in our skip list.
Delete Operation
Suppose we want to delete node with value 50.
So, first we need to search node of value than 50 and then we will delete that node from all levels(as it could be possible that node is present on more than one level so we need to delete all the occurances of that node).
So, now we can erase all the occurances of 50 from the list by keeping some previous and next pointers.
Now, lets implement what we have discussed
Here we need to erase only any one of node
So, lets deep dive into implemetation of Skip List
Initially we need two pointers one that goes to right and one that goes down.
So, we will create a structure for this purpose.
struct Node {
Node *right, *down;
int val;
Node(int val){
this->val = val;
right = NULL;
down = NULL;
}
};To search a particular node in a skip list :
We will see that if head->next < targetValue then we will go right else we will go down.
bool search(int target) {
Node* temp = head;
while(temp){
while(temp->right && temp->right->val < target) temp = temp->right;
if(temp->right && temp->right->val == target) return true;
temp = temp->down;
}
return false;
}To insert a node in a list
We will iterate and store all the nodes at each level after which we need to insert in a vector .
Lets take example from this list
Here we will store the nodes 30, 50, 50 in a vector as we have three levels here.
Then we will start from the bottom and pop out the first node 50 and insert the node 55 right after it and same for the other nodes.
What if all the levels are done and we still get a head then we will create a new level with a newHead and insert the node in that level as well.
void add(int num) {
vector<Node*> prevNodes;
Node* temp = head;
while(temp){
while(temp->right && temp->right->val < num) temp = temp->right;
prevNodes.push_back(temp);
temp = temp->down;
}
bool insertUp = true;
Node* downNode = NULL;
while(insertUp && prevNodes.size()){
Node* prev = prevNodes.back();
prevNodes.pop_back();
Node* newNode = new Node(num);
Node* next = prev->right;
newNode->right = next;
newNode->down = downNode;
prev->right = newNode;
downNode = newNode;
insertUp = (rand() % 2) == 0;
}
if(insertUp){
Node* newHead = new Node(-1);
Node* newNode = new Node(num);
newHead->down = head;
head = newHead;
newHead->right = newNode;
newNode->down = downNode;
}
}
And here we only need to erase one occurance of the node , so I have deleted the node that is at the level 0.
bool erase(int num) {
bool flag = false;
Node* temp = head;
while(temp){
while(temp->right && temp->right->val < num) temp = temp->right;
if(temp->right && temp->right->val == num){
Node* node = temp->right;
temp->right = node->right;
delete(node);
flag = true;
}
temp = temp->down;
}
return flag;
}And here is the complete code:
struct Node {
Node *right, *down;
int val;
Node(int val){
this->val = val;
right = NULL;
down = NULL;
}
};
class Skiplist {
public:
Node* head;
Skiplist() {
head = new Node(-1);
}
bool search(int target) {
Node* temp = head;
while(temp){
while(temp->right && temp->right->val < target) temp = temp->right;
if(temp->right && temp->right->val == target) return true;
temp = temp->down;
}
return false;
}
void add(int num) {
vector<Node*> prevNodes;
Node* temp = head;
while(temp){
while(temp->right && temp->right->val < num) temp = temp->right;
prevNodes.push_back(temp);
temp = temp->down;
}
bool insertUp = true;
Node* downNode = NULL;
while(insertUp && prevNodes.size()){
Node* prev = prevNodes.back();
prevNodes.pop_back();
Node* newNode = new Node(num);
Node* next = prev->right;
newNode->right = next;
newNode->down = downNode;
prev->right = newNode;
downNode = newNode;
insertUp = (rand() % 2) == 0;
}
if(insertUp){
Node* newHead = new Node(-1);
Node* newNode = new Node(num);
newHead->down = head;
head = newHead;
newHead->right = newNode;
newNode->down = downNode;
}
}
bool erase(int num) {
bool flag = false;
Node* temp = head;
while(temp){
while(temp->right && temp->right->val < num) temp = temp->right;
if(temp->right && temp->right->val == num){
Node* node = temp->right;
temp->right = node->right;
delete(node);
flag = true;
}
temp = temp->down;
}
return flag;
}
};
**Thankyou **