Implement a Skip List in JavaScript

A skip list is a probabilistic data structure that allows for efficient searching, insertion, and deletion operations, similar to balanced trees but with simpler implementation. This challenge asks you to build a functional skip list in JavaScript. Mastering skip lists will provide you with a deeper understanding of advanced data structures and their practical applications in optimizing performance.

Problem Description

You need to implement a SkipList class in JavaScript. This class should support the following operations:

• insert(value): Inserts a new value into the skip list. The value should be unique. If the value already exists, the insertion should be ignored.
• search(value): Returns true if the value exists in the skip list, and false otherwise.
• delete(value): Deletes the value from the skip list if it exists. Returns true if the value was deleted, false otherwise.
• getValues(): Returns an array containing all values in the skip list in ascending order.

Key Requirements:

1. Node Structure: Each node in the skip list will have a value and an array of forward pointers. The length of the forward array determines the level of the node.
2. Levels: The skip list will have a maximum level. Each new node's level is determined probabilistically. A common approach is to flip a coin: if heads, increase the level, until tails or the maximum level is reached.
3. Header Node: The skip list will have a special header node with a value smaller than any possible element (e.g., -Infinity). This node will have forward pointers at all levels.
4. Probabilistic Level Assignment: Implement a function to determine the random level for a new node. The probability of a node being at level i should be p^i for some probability p (e.g., p = 0.5).
5. Ordered Values: The skip list must maintain its elements in sorted order.

Edge Cases to Consider:

• Inserting duplicate values.
• Searching for a value that doesn't exist.
• Deleting a value that doesn't exist.
• Deleting the only element in the list.
• An empty skip list.

Examples

Example 1:

const skipList = new SkipList();
skipList.insert(3);
skipList.insert(6);
skipList.insert(7);
skipList.insert(9);
skipList.insert(12);
skipList.insert(19);
skipList.insert(17);
skipList.insert(26);
skipList.insert(21);
skipList.insert(25);

console.log(skipList.getValues()); // Expected: [3, 6, 7, 9, 12, 17, 19, 21, 25, 26]
console.log(skipList.search(19)); // Expected: true
console.log(skipList.search(10)); // Expected: false

Explanation: This demonstrates the basic insertion and searching functionality, showing that values are stored in order and can be found.

Example 2:

const skipList = new SkipList();
skipList.insert(5);
skipList.insert(10);
skipList.insert(3);

console.log(skipList.delete(10)); // Expected: true
console.log(skipList.getValues()); // Expected: [3, 5]
console.log(skipList.delete(7)); // Expected: false
console.log(skipList.getValues()); // Expected: [3, 5]

Explanation: This example tests the delete operation, including deleting an existing element and attempting to delete a non-existent element.

Example 3: Edge Case - Empty List and Full Deletion

const skipList = new SkipList();
console.log(skipList.getValues()); // Expected: []
console.log(skipList.search(100)); // Expected: false
console.log(skipList.delete(50)); // Expected: false

skipList.insert(50);
console.log(skipList.delete(50)); // Expected: true
console.log(skipList.getValues()); // Expected: []

Explanation: This tests the behavior of the skip list when it's empty, and after inserting and then deleting its only element.

Constraints

• The maximum level for the skip list should be configurable, but a default of 16 is reasonable.
• The probability p for level determination should be 0.5.
• Values inserted into the skip list will be integers.
• The number of elements in the skip list can be up to 10,000.
• Search, insert, and delete operations are expected to have an average time complexity of O(log n), where n is the number of elements in the skip list.

Notes

• Consider how to manage the maximum level of the skip list. The header node should always have pointers up to the maximum possible level.
• The probabilistic level assignment is crucial. Make sure to implement it correctly.
• When searching or deleting, you'll need to keep track of the nodes that precede the target node at each level, as these are the nodes whose forward pointers might need to be updated.
• For getValues(), you only need to traverse the bottom-most level (level 0) of the skip list, as it contains all elements in sorted order.