A Fast Default List

Starting with the SkipListList class, implement a FastDefaultList class that represents an infinite list with indices 0,1,2,3,...,∞ When we start, every value in this list is assigned the default value null. Otherwise, this class behaves just like a List; it has the add(i,x), remove(i), set(i,x), and get(i) that behave just like the same methods in a list. Each of these operations should run in O(log n) time. The size() method is already implemented for you, it returns the largest value you can store in an int

Again, this is not a hack job. First understand how the SkiplistList class works and figure out how you can modify it to do what this question asks.

Note: A DumbDefaultList class has already been implemented for you. You can use it to help test correctness of your implementation.

Hint: Work slowly. There is not much code you have to change in the FastDefaultList.java file (which is mostly just a copy of SkiplistList), but it is delicate. Checkpoint your work often and test carefully as you go.

Part II: Testing

Within the Tester class, write the following functions, all of which return true if all tests are successful or false if any test fails.

1 testPart1(t) function that tests if the Table t satisfies the requirements for Question 1:

1 This function should do all kinds of correctness tests.

2 This function should test that the performance of all operations is what it should be for a FasterTable

2 testPart2(dl) function that tests if the DefaultList dl satisfies the requirements for Question 2:

1 This function should do all kinds of correctness tests.

2 This function should test that the performance of all operations is what it should be for a FastDefaultList

Attachment:- DumbDefault.rar