Ordered List MINI-LAB

In this mini-lab you will implement an ordered list of elements (which may include duplicates) using a java.util.ArrayList as its underlying structure. The elements in an ordered list are ordered based on the functionality of their compareTo method; for example, they might be ordered alphabetically or numerically. An ordered list adds new elements to the list in a way that maintains the ordered nature of the list, and does not support operations that could cause the elements to become unordered. Since the class needs to be able to compare the elements put into it to establish and maintain its ordered nature, the objects in it must be comparable.

The K_OrderedList class should implement the K_SimpleList interface using an ArrayList as its underlying structure. This means that it has some similar functionality to the K_SimpleAL class. Some methods may need different behavior, though, to maintain the ordered nature of the list.

Getting Started

Create a class named K_OrderedList. Specify that its elements may be any generic type that is comparable, such as Integer or String objects. This can be done with the following syntax:

    public class K_OrderedList<T extends Comparable<T>>

If you decide to make it a subclass of K_SimpleAL, the syntax would be:

    public class K_OrderedList<T extends Comparable<T>> extends K_SimpleAL<T>

Following the practices of Agile Development, you should start with the most basic methods that you can implement and test before going on to other methods, and you should test each method as you implement it. For example, you might start by implementing and testing the constructor, add, and toString methods to make sure you can create ordered lists before adding and testing other functionality.

Download the skeleton tester class OrderedListTester.java. Note, though, that the provided version only tests very basic methods. The provided test driver creates an empty ordered list of type Integer, then generates random numbers so that you can test that your list is created and maintained in random order. As you go on to implement and test other methods, make sure you use try/catch blocks for methods that can throw exceptions.

A list allows duplicates, so your code should handle and test situations with duplicates.

Method Details

Many of the methods in K_OrderedList have the same functionality as in K_SimpleAL. A few, though, will require modification to maintain or take advantage of the ordered nature of your new class.

• public void add(T element) Remember this is an ordered list, so you need to be careful where you add it. What is the impact of adding an element to its proper location? How might this be similar to the actions in one of the sorting algorithms we have studied?
• public int find(T element) The K_SimpleAL class implements this with a sequential search, but an ordered list can do better. Implement this method using a Binary Search. (Analysis Question: Why is this a good implementation choice for this method?)
• public boolean contains(T element) This also can be done more efficiently than in the K_SimpleAL class.
• public boolean remove (T element) Again, finding the element to remove can be done more efficiently than in the K_SimpleAL class.