For this assignment, you will explore the Java Collections Framework through the List interface to implement an OrderedList interface. You will also implement a SkipList which allows fast searching for data and fast updates. You should save your programs in your cs35/homework/05
directory. You may work with one partner on this assignment. If you work with a partner, be sure to put both names on your assignment when submitting.
In you cs35/homework/05
folder, you will find a description of an
interface for storing a collection of integers
sorted order. A student directory is also an OrderedList
alphabetically by last name, but for simplicity in this assignment, we are just
storing integers. Review the interface description in OrderedList.java
and be sure you understand what each method is trying to do before you
implement it. Note that the add
method must add a new element to the
list in sorted order (smaller integers first). The find
returns a Boolean value indicating if the particular item or key
found in the list. Note it is possible to store more than one copy of the same
integer in the OrderedList
. Your assignment is to implement the
interface in three different ways: using a LinkedList,
using an ArrayList, and implementing a new structure called the SkipList.
Modify the file LinkedOrderedList.java
to implement the
interface. For this implementation, you should use Java's
imported from java.util.LinkedList to store the data. Note
that most of your methods for the LinkedOrderList
can be implemented
by calling appropriate methods on the LinkedList
object storing your
data. The role of your LinkedOrderList
class is to make sure elements
are added in sorted (increasing) order. Because LinkedOrderedList
, you must include an implementation for each
method in the OrderedList
interface. Do not modify the
interface. You may add other method to the
class that are not in the OrderedList
interface. One such helpful method may be something that takes as input an
and finds the smallest index in the linked list containing a
value greater than m
The LinkedOrderedList list class is the easiest to implement because
many of the methods can be written using one method in the corresponding
LinkedList class. The methods size, isEmpty, find, get, and
iterator are all examples that can be written with one line of code.
Once you are done implementing your LinkedOrderedList, you can test it
using the TestLists.java. Feel free to modify this code to include
Next, modify the ArrayOrderedList.java
file to implement the OrderedList
interface using Java's ArrayList
class. For this implementation, you must implement find
using binary search. A description of binary search can be found on page 395 of your text book. You may use binary search in other methods if you wish. Once you finish implementing your ArrayOrderedList
, test your code by modifying TestList.java
While an ArrayList implementation offers faster get
methods than the LinkedList, updates (add
) are still slow in both implementations. You will implement a SkipList
from scratch to allow faster updates. A description of SkipLists
can be found in section 9.4 of your text on page 398. A simple implementation of a SkipNode
is included in your homework folder. Feel free to modify this class if you do not like it. Your SkipList
class must also implement the OrderedList
The SkipList might seem overly complicated at first, but draw a few examples on the board or trace through some examples in the text. It will be helpful to implement SkipSearch, SkipInsert, and insertAfterAbove according the book's description. Once these are implemented, you should find that many of the methods in the OrderedList interface can be implemented on top of these methods.
The book refers to special nodes that store the values positive and negative infinity. In Java, you can use the special values Integer.MAX_VALUE and Integer.MIN_VALUE to represent these limits. You can use these numbers just like any other integer.
Think about how to implement get and remove. You implementation of get does not need to be fast. An O(n) algorithm is fine.
To create an iterator for you skip list, the easiest thing to do is to create a new LinkedList, incrementally add the appropriate skip list elements to the LinkedList and return the iterator of the newly created linked list.
Along with your java source code, you should hand in a file named README. Your README should include a brief summary of your results, including a discussion of the advantages/disadvantages of the three implementations of OrderedList. Describe how you tested your implementations. Do you have any problems/bugs in your code? For each of the following operations: add, remove, get,
, describe which implementations you think gives the best/worst performance. You do not have to give big-Oh run times.