Implementing a Skip List in JavaScript

Skip lists are probabilistic data structures that use multiple levels of linked lists to achieve logarithmic time complexity for search, insertion, and deletion operations, similar to balanced trees. This challenge asks you to implement a skip list in JavaScript, providing a practical exercise in data structure design and probabilistic algorithms. Skip lists are a powerful alternative to balanced trees, often simpler to implement while maintaining excellent performance.

Problem Description

You are tasked with creating a Skip List data structure in JavaScript. The Skip List should support the following operations:

• insert(key, value): Inserts a new node with the given key and value into the skip list. The key must be a number. The value can be of any type.
• search(key): Searches for a node with the given key and returns its value if found. If the key is not found, it should return undefined.
• delete(key): Deletes the node with the given key from the skip list. If the key is not found, the function should do nothing.
• print(): Prints the skip list level by level, showing the keys and values at each level. This is primarily for debugging and visualization.

The skip list should be implemented with a probabilistic approach to determine the level of each newly inserted node. A common approach is to flip a coin (using Math.random()) to decide whether to promote a node to the next higher level. The probability of promotion is typically 1/2.

Key Requirements:

• The skip list should maintain sorted order based on the keys.
• The implementation should handle duplicate keys (inserting multiple nodes with the same key).
• The print() method should provide a clear visual representation of the skip list's structure.

Expected Behavior:

The skip list should behave as a sorted data structure, allowing efficient search, insertion, and deletion operations. The probabilistic nature of the levels should result in a balanced structure on average, providing logarithmic performance.

Edge Cases to Consider:

• Empty skip list: Handle insertion, search, and deletion operations on an empty skip list.
• Duplicate keys: Ensure that multiple nodes with the same key can be inserted and retrieved correctly.
• Deleting a non-existent key: The delete operation should gracefully handle cases where the key is not present.
• Large number of insertions: Test the performance and stability of the skip list with a significant number of insertions.

Examples

Example 1:

Input:
insert(3, "apple");
insert(6, "banana");
insert(7, "cherry");
insert(9, "date");
insert(12, "elderberry");

search(7);

delete(6);

print();

Output:

7

Explanation: The skip list is initialized with several key-value pairs. Searching for the key 7 returns "cherry". Deleting the key 6 removes the corresponding node. The print() method displays the structure of the skip list after these operations.

Example 2:

Input:
insert(1, "one");
insert(1, "uno");
insert(2, "two");
insert(1, "ein");

search(1);

Output:

[ 'one', 'uno', 'ein' ]

Explanation: Multiple nodes with the same key (1) are inserted. Searching for the key 1 returns an array of all values associated with key 1.

Example 3: (Edge Case - Deletion)

Input:
insert(5, "grape");
delete(10);
search(5);

Output:

5

Explanation: Deleting a key that doesn't exist (10) has no effect. Searching for the key 5 returns "grape".

Constraints

• Key Type: Keys must be numbers.
• Value Type: Values can be of any JavaScript data type.
• Level Probability: The probability of a node being promoted to the next level should be 1/2 (or a similar value).
• Time Complexity: Average case time complexity for insert, search, and delete should be O(log n), where n is the number of elements in the skip list.
• Space Complexity: The space complexity should be O(n) in the worst case.

Notes

• Consider using a Node class to represent each node in the skip list. Each node should have pointers to the next node at each level.
• The insert operation should randomly determine the level of the new node.
• The search operation should traverse the skip list from the highest level down, efficiently narrowing down the search space.
• The delete operation should carefully remove the node from all levels of the skip list.
• The print method is primarily for debugging and visualization; it doesn't need to be highly optimized.
• You can use Math.random() to simulate a coin flip for level determination. A simple approach is to keep flipping until you get a false result.
• Think about how to handle the head and tail nodes of the skip list. They are crucial for managing the levels and pointers.