Create a Program to Implement Sorted List in Java Assignment Solution

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() { } }