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 OrderedList interface for storing a collection of integers in sorted order. A student directory is also an OrderedList, sorted 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 method just returns a Boolean value indicating if the particular item or key was 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 OrderedList 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 OrderedList interface. For this implementation, you should use Java's LinkedList 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 implements OrderedList, you must include an implementation for each method in the OrderedList interface. Do not modify the OrderedList interface. You may add other method to the LinkedOrderedList class that are not in the OrderedList interface. One such helpful method may be something that takes as input an integer m 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 other tests.

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 and find methods than the LinkedList, updates (add and remove) 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 interface.

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, and find, describe which implementations you think gives the best/worst performance. You do not have to give big-Oh run times.

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:42 AM