实现一个高性能的List，采用类似 SkipList 的数据结构。
Important Submission Instructions
You will be uploading your submission using the assignment server. The link is
posted to cuLearn. A short video is posted there also in case you require
instructions. You may submit as many times as you wish, but must wait at least
5 minutes between submissions (to protect the server). Your highest mark is
kept. It would help us out if you try the upload early, even using just the
unmodified assignment skeleton. That way potential problems can be found
before the deadline. It will also ensure that YOU know how to submit your
assignment well before the deadline. If your attempt to obtain your secret
code is unsuccessful, please email me at [ [email protected] ](/cdn-
cgi/l/email-protection) . This may happen if you have registered late, etc.
You must adhere to the following rules (as your submission will be subjected
to automatic marking system):
- Download the compressed file “comp2402a3.zip” from cuLearn.
- Retain the directory structure (i.e., if you find a file in subfolder “comp2402a3”, you must not remove it).
- Retain the package directives (i.e., if you see “package comp2402a3;” in a file, you must not remove it).
- Do not rename any of the methods already present in the files provided.
- Do not change the visibility of any of the methods provided (e.g., do not change private to public).
- You may use the main method of FastDefaultList for test code; this is a different specification from previous assignments.
- Upload a compressed file “comp2402a3.zip” to the assignment server to submit your assignment as receive your mark immediately (highest mark of all submissions will be your assignment mark).
Please also note that your code may be marked for efficiency as well as
correctness - this is accomplished by placing a hard limit on the amount of
time your code will be permitted for execution. If you select/apply your data
structures correctly, your code will easily execute within the time limit, but
if your choice or usage of a data structure is incorrect, your code may be
judged to be too slow and it may receive a grade of zero.
You are expected to demonstrate good programming practices at all times (e.g.,
choosing appropriate variable names, provide comments in your code, etc.) and
your code may be penalized if it is poorly written. The server won’t judge
this, but in case of discrepancies, this will be evaluated.
Instructions
Start by downloading the comp2402a3 Zip file from cuLearn, which contains a
skeleton of the code you need to write. This assignment is about modifying the
SkiplistList class to implement a FastDefaultList. The folder contains two
files (java classes); DumbDefaultList.java and FastDefaultList.java. You are
to complete FastDefaultList.java according to the specification provided
below. DumbDefaultList.java is not to be modified. It is to help you test the
correctness of your class. It is a correct but slow implementation of the
behaviour required.
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.
A DumbDefaultList class has already been implemented for you. You can use it
to help test the correctness of your implementation. Your FastDefaultList
should have the same output for a given input as DumbDefaultList, but it
should run much faster.
Warning: 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.
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.
Here is a short example to illustrate the behaviour required:
- I make a new FastDefaultList of Strings.
- I call get(1000) and it returns null.
- I call add(1000, “hello”).
- get(1000) now returns “hello”.
- A call of get(500) returns null.
- I call add(500, “goodbye”).
- get(1000) now returns null.
- get(1001) returns “hello” (because every entry from 500 to was shifted up one index to make room for “goodbye” at index 500).
- I call remove(20).
- get(500) returns null.
- get(499) returns”goodbye”, and get(1000) returns “hello” (because all the items from index 21 to were shifted one index down when we removed index 20).
