← back to the schedule


MINI-LAB #4
Ordered List and Binary Search



In this mini-lab you will implement an ordered list using a java.util.ArrayList as its underlying structure. Name the class OrderedList and remember this class will receive a generic type, so it can be an ordered list of Integers or Strings, and so on. Your class will also need to be able to compare elements of this generic type, so it should specify that those objects are comparable, as in

public class OrderedList<T extends Comparable<T>>

Implement the following methods for the class:

  • public void add(T element) Adds an element in its corresponding position. Remember this is an ordered list, so you need to know what "corresponding position" means.
  • public T get(int index) Returns the element at the given index, throws IndexOutOfBoundsException if the given index is not within the list's range.
  • public T remove (int index) Removes and returns the element at the given index, throws 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, returns false.
  • public boolean contains(T element) Returns true if the element is contained in the list, false otherwise. This method will implement a Binary Search.
  • public int find(T element) If the element exist, its index will be returned, otherwise returns -1. An alternative definition for this method is to throw NoSuchElementException when the element is not found, instead of returning -1. This method will also implement a Binary Search.
  • public boolean isEmpty() Determines if the list is empty
  • public int size(): Determines the number of elements in the list.
  • public String toString() Returns a String coatining all the elements in the list. It should have the form [1, 2, 3, 4] for example.

Create a tester class called OderedListTester that contains main to test each one of the methods in the class OrderedList. Make sure you use try/catch blocks for methods that can throw exceptions.

You can use the follwing piece of code in your main method to add random elements to the list and test if they are being added in order:

import java.util.Random;
...
// Adds 1,000 random elements between 0 and 1,000 to the ordered list
Random r = new Random();
for (int i = 0; i < 1000; i++) {
  list.add(r.nextInt(1001));
}

System.out.println(list);

By using the code above you will end up with repeated numbers in the list, which is ok. Just make sure to code this behavior for methods like find, contains, removeIfExists, and so on.

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

EVALUATION

Mini-lab #4 is worth 15 points. This project will be submitted individually. The following items describe the criteria we will use to evaluate your mini-lab:

  • Correct implementation of the method public void add(T element). This is an ordered list, so when the list is printed all the numbers most be in ascending order, from min to max. 4 pts.
  • Correct implementation of public T get(int index) 1 pt.
  • Correct implementation of public T remove (int index) 1 pt.
  • Correct implementation of public boolean removeIfExists (T element) 1 pt.
  • Correct implementation of public boolean contains(T element) 2 pt.
  • Correct implementation of public int find(T element) 2 pt.
  • Correct implementation of the methods public boolean isEmpty(), public String toString(), and public int size() 1.5 pts.
  • Adding appropriate amount of comments to the code (your name and description of the class, method description, and so on) 1 pt.
  • Proper organization of your code (indentation, clarity, cleverness), and for adding the OrderedListTester class and adding a test for each of the previous method (specially add, get, remove, removeIfExists, contains, and find) 1.5 pts.

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