## Instructions

**Objective**

Write a java assignment program to implement sorted list.

## Requirements and Specifications

**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?)

**Source Code**

**APP**

```
public class App {
public static void main(String[] args) throws Exception {
MyList l = new MyList();
l.insert(5);
l.insert(10);
l.insert(-1);
l.insert(-30);
printList(l);
System.out.println(l.size());
System.out.println(l.get(7));
}
public static void printList(MyList l)
{
Node current = l.head;
while(current != null)
{
System.out.println(current.value + " ");
current = current.next;
}
}
}
```

**SORTED LIST**

```
/**
* 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();
}
```

**MY LIST**

```
public class MyList implements SortedList {
Node head;
Node tail;
@Override
public void insert(int number) {
// TODO Auto-generated method stub
Node node = new Node(number);
if(head == null)
{
head = node;
tail = node;
}
else
{
tail.next = node;
tail = node;
}
// after adding each element, let's sort them
// The list is sorted using the Bubble Sort method
Node current = head;
Node next_to_current = null;
int temp;
if(head == null)
return;
else
{
while(current != null)
{
next_to_current = current.next;
while(next_to_current != null)
{
if(current.value > next_to_current.value) // if previous is higher than next, swap
{
temp = current.value;
current.value = next_to_current.value;
next_to_current.value = temp;
}
next_to_current = next_to_current.next;
}
current = current.next;
}
}
}
@Override
public int get(int i) {
// TODO Auto-generated method stub
if(i > size()-1) // if the parameter i is out of bounds
throw new IndexOutOfBoundsException("Index " + i + " is out of bounds.");
int idx = 0; // parameter to hold current index
int val = -1; //
Node current = head; // current node
while(current != null)
{
if(idx == i)
{
val = current.value;
break;
}
current = current.next;
idx++;
}
return val;
}
@Override
public int size() {
// TODO Auto-generated method stub
int i = 0;
// Count all elements until the last one is not initialized
Node current = head;
while(current != null)
{
i++;
current = current.next;
}
return i;
}
void sort()
{
}
}
```