You are to implement a linked list that remains sorted. The linked list should be able to store any object as long as the object has implemented the Comparable interface. You may create either a singly linked sorted list or a doubly linked sorted list.

To start out, the list should be ordered in ascending order. This can change if the reverse method is called. If the reverse method is called and the list is in ascending order, then the list should change to be in descending order. If the list is in descending order and the reverse method is called, then the list should change to be in ascending order.

In addition to these methods you may implement any additional helper methods that should be kept private.

clear- Should reset the list to be empty. Can be called in the default constructor.

getSize- Returns the size of the list.

toString- Returns a string representation of the list.

add- Adds a new object to the list in its sorted position. Starts adding elements in ascending order. If the reverse method has been called, then the order is changed from ascending to descending and vice versa.

If the list is in ascending order then the newData needs to be placed in the list such that node.prev.data newData node.next.data.

If the list is in descending order then the newData needs to be placed in the list such that node.prev.data newData node.next.data.

removeFromIndex- Removes an item from a given position. If the position is out of bounds, then throw an IndexOutOfBoundsException. If the list is empty, then throw a NoSuchElementException. You will need to import this exception.

removeAll- Removes all of a given item. If the list is empty, then throw a NoSuchElementException.

get- Returns the item from a given position. If the position is out of bounds, then throw an IndexOutOfBoundsException.

reverse- Reverses the ordinal direction of the list. If the list is in ascending order, then the list should end up in descending order and vice versa. This will also affect how add behaves.

contains- Takes an element and returns true if the element is in the list and false if it does not.

Extra Info: When you add an element, you may not just add it to the front or back of the list then call a sort method. The element must be placed in its sorted position in BigO(N) time. Calling a sort such as merge or quick will result in BigO(NLogN) for merge and BigO(N^2) time for quicksort. Furthermore, your contains method should also be BigO(N) time. Dont waste effort trying to implement a binary search as this may result in longer wait times. Unlike arrays, you cant calculate the position of an element in memory and will need to traverse through a linked list. Linear traversal is fine.