Exercise: Skiplists

Task

The find(x) method in a Skiplist sometimes performs redundant comparisons; these occur when x is compared to the same value more than once. They can occur when, for some node, u, u.next[r] = u.next[r − 1]. Modify the find(x) method so that these redundant comparisons can be avoided.

Sample input

The sample input will be as follows:

The first 25 values in a skiplist will be using this formula: i % 100 + 900
The next 50 values in a skiplist will be using this formula: i % 50
The next 25 values in a skiplist will be using this formula: i % 20

Expected output

The expected output will be as follows:

Adding 1000 elements
Searching
Found: 10, null, null