← back to the schedule


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. Since the class will need 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 full list of methods to implement is below. Some of the methods in this class will throw an exception if they cannot do what is asked, such as getting an element at an index that is out of bounds, while others will handle "exceptional" conditions through specific return values. A list allows duplicates, so your code should handle and test situations with duplicates.

Getting Started

Create a class named 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 OrderedList<T extends Comparable<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 creating an OrderedList class that has only add and toString methods.

Download the skeleton tester class OrderedListTester.java. and use it to test your initial, 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.

Methods to Include

The full set of methods for the class should include:

  • public void add(T element) Adds an element to the list. 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 boolean isEmpty() Determines if the list is empty.
  • public int size(): Determines the number of elements in the list.
  • public T get(int index) Returns the element at the given index, throwing IndexOutOfBoundsException if the given index is not within the list's range.
  • public int find(T element) If the element is in the list, the method returns its index, otherwise it returns -1. (An alternative approach for this method is to throw NoSuchElementException when the element is not found, instead of returning -1.) Implement this method using a Binary Search. (Analysis Question: Why is this a good implementation choice for this method?)
  • public boolean contains(T element) Returns true if the element is contained in the list, false otherwise.
  • public T remove (int index) Removes and returns the element at the given index, throwing IndexOutOfBoundsException if the given index is not within the list's range.
  • public boolean removeIfExists (T element) If the element exists it will be removed and return true; if the element doesn't exist, the method returns false.
  • public String toString() Returns a String containing all the elements in the list. It should have the form [1, 2, 3, 4] for example.

Submission

Submit your completed program through Kit, under Ordered List Mini-Lab.

Have fun! And if you have any questions remember my email, my office hours, and the Collaboration Center are here for you!



← back to the schedule