Introduction
A skip list is a probabilistic data structure that allows for efficient searching, insertion, and deletion of nodes. Skip lists have a similar structure to linked lists, but with additional levels of nodes that "skip" over sections of the list.
class Node {
val: number;
next: Node | null;
down: Node | null;
constructor(val: number) {
this.val = val;
this.next = null;
this.down = null;
}
}Advantages of Skip Lists
One of the main advantages of skip lists is their simplicity. While balanced trees require complex algorithms to maintain their balance, skip lists use a straightforward probabilistic approach. This makes them easier to implement and understand. Additionally, skip lists have the same average-case time complexity as balanced trees, but with a lower constant factor. This means that skip lists can be faster in practice, especially for smaller data sets.
Where L1 is the number of nodes in the first layer and L2 is the number of nodes in the second layer. To minimize it, we let , since L2 is the n, so we want to L1 to be Sqrt(L2).
Searching in Skip Lists
Searching in a skip list is similar to searching in a linked list, but with the addition of multiple levels of nodes. Starting at the top level, we compare the value we are searching for to the value of the next node. If the value is bigger than the next node’s value, we move down to the next level and repeat the process. If the value is smaller than or equal to the next node’s value, we move to the next node on the current level and repeat the process. We continue this process until we find the node we are searching for, or determine that it does not exist in the list.
Insert in Skip Lists
To insert a node into a skip list, we first search for the correct position for the node. Once we have found the correct position, we create a new node and insert it into the list at that position. We then "promote" the node to higher levels with some probability, using a random number generator. The search operation in a skip list is similar to that of a binary search tree, but with the added benefit of multiple levels. This allows for a logarithmic search time complexity, which is the same as a balanced binary search tree.
Implementation
class SkipList {
head: Node; // Head node of the highest level
// Skip List constructor
constructor() {
this.head = new Node(-Infinity); // Create a head node with the minimum possible value
}
// Method to randomly determine the height of a new node
pickHeight(): number {
let height = 1;
while (Math.random() < 0.5) {
height++;
}
return height;
}
// Method to insert a new value into the Skip List
insert(val: number): void {
const newNodeHeight = this.pickHeight(); // Determine the height of the new node
let currentHeight = this.getHeight(); // Get the current height of the Skip List
// Add levels to the Skip List if the new node's height is greater than the current height
while (newNodeHeight > currentHeight) {
const newHead = new Node(-Infinity);
newHead.down = this.head;
this.head = newHead;
currentHeight++;
}
let currentNode: Node = this.head;
let prevNodes: Node[] = []; // Array to store the previous nodes for each level
// Traverse the Skip List to find the insertion point
for (let h = currentHeight - 1; h >= 0; h--) {
while (currentNode.next && currentNode.next.val < val) {
currentNode = currentNode.next;
}
if (h < newNodeHeight) {
prevNodes[h] = currentNode;
}
currentNode = currentNode.down!;
}
// Insert the new node at the determined positions
for (let h = 0; h < newNodeHeight; h++) {
const newNode = new Node(val);
newNode.next = prevNodes[h].next;
prevNodes[h].next = newNode;
if (h > 0) {
newNode.down = prevNodes[h - 1].next;
}
}
}
// Method to search for a value in the Skip List
search(val: number): Node | null {
let currentNode: Node | null = this.head;
// Traverse the Skip List to find the target value
while (currentNode) {
while (currentNode.next && currentNode.next.val < val) {
currentNode = currentNode.next;
}
if (currentNode.next && currentNode.next.val === val) {
return currentNode.next;
}
currentNode = currentNode.down;
}
return null; // Return null if the value is not found
}
// Method to delete a node with the specified value from the Skip List
delete(val: number): void {
let currentNode: Node | null = this.head;
// Traverse the Skip List to find the node to delete
for (let h = this.getHeight() - 1; h >= 0; h--) {
while (currentNode.next && currentNode.next.val < val) {
currentNode = currentNode.next;
}
if (currentNode.next && currentNode.next.val === val) {
currentNode.next = currentNode.next.next; // Update the pointer to bypass the node to delete
}
currentNode = currentNode.down;
}
}
// Method to get the height of the Skip List
getHeight(): number {
let height = 0;
let currentNode: Node | null = this.head;
// Count the levels in the Skip List
while (currentNode) {
height++;
currentNode = currentNode.down;
}
return height;
}
}
// Example usage:
const skipList = new SkipList();
skipList.insert(5);
skipList.insert(10);
skipList.insert(15);
skipList.insert(20);
console.log('Search for 10:', skipList.search(10));
console.log('Search for 25:', skipList.search(25));
