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 anelement
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 givenindex
, throwsIndexOutOfBoundsException
if the givenindex
is not within the list's range.public T remove (int index)
Removes and returns theelement
at the givenindex
, throwsIndexOutOfBoundsException
if the givenindex
is not within the list's range.public boolean removeIfExists (T element)
If theelement
exists it will be removed and returntrue
, if theelement
doesn't exist, returnsfalse
.public boolean contains(T element)
Returnstrue
if the element is contained in the list,false
otherwise. This method will implement a Binary Search.public int find(T element)
If theelement
exist, itsindex
will be returned, otherwise returns-1
. An alternative definition for this method is to throwNoSuchElementException
when theelement
is not found, instead of returning-1
. This method will also implement a Binary Search.public boolean isEmpty()
Determines if the list is emptypublic int size():
Determines the number of elements in the list.public String toString()
Returns aString
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()
, andpublic 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 (speciallyadd
,get
,remove
,removeIfExists
,contains
, andfind
) 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