Sorted List 2

Project instructions

In this project, you are to implement the SortedList interface (download the attached SortedList.java file and include that in your project).

A SortedList allows for three operations:

• insert(): Adds an element to the list
• get(): Gets the "i"-th smallest number in the list
• size(): Returns the size of the list.

One should be able to use a SortedList by adding elements in any order, and then iterating through the list and getting the elements back in sorted order.

For example:

SortedList l;
// some code which initializes l
l.insert(5);
l.insert(3);
l.insert(7);
l.insert(20);
l.insert(-30);

for (int i = 0; i < l.size(); i++) {
System.out.println(l.get(i));
}

This should output:

-30
3
5
7
20

Directions

This project has two parts: a programming part and a written part. For the programming part:

• Implement the SortedList interface.
• Write a main class which tests out the interface.

For the written part, you must determine the asymptotic running time ("Big Oh") of all of the functions. You should explain the tradeoffs: for example, you may have decided to make the insert method faster at the expense of the get method, or the other way around. Describe which situations would be appropriate for this tradeoff. For example, why would you want get to be fast at the expense of insert? (What kind of application would that be appropriate for?)

SortedList

/**
* An interface which represents a Sorted List of integers.
* Implementations do not necessarily need to keep their lists sorted, but they need to return the elements
* in sorted order.
*/
public interface SortedList {

/**
* Inserts number into the list
*
* @param number
*/
void insert(int number);

/**
* Gets the "i"-th smallest number in the list.
*
* @param i
* @return the i-th smallest number in the list
* @throws IndexOutOfBoundsException if i is not between 0 and size() - 1
*/
int get(int i);

/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
int size();
}