List assignment Always Sorted Linked List Solved

Description

For this assignment, you will need to turn in your .java files that contain the implementation of the linked list as described below and any additional .java files you use to test it.
Additionally, you can find information on Sorted Lists in Chapter 16 (4th edition) or Chapter 17 (5th edition).

Always Sorted Linked List

You are to implement a linked list that remains sorted. The linked list should be able to store any object if 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.

The header for the class should look like this (you can use a different class name. This is just to show the generics)

public class SortedLinkedList<T extends Comparable<? super T>>

The node class will only need the generic <E> since the generic T is used and is guaranteed to have the compareTo method.

private class Node<E>

If you separate the Node class to its own Java file then you will need to make it public and include it with your linked list implementation when you submit it.

Methods to Implement

Below are the methods you need to implement to get full credit. In addition to these methods you may implement any additional helper methods that should be kept private.

1. clear – Should reset the list to be empty. Can be called in the default constructor.
2. getSize – Returns the size of the list.
3. toString – Returns a string representation of the list.
4. add – Adds a new object to the list in it’s 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.
   1. 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.
   2. 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.
5. remove – Removes an item from a given index. If the position is out of bounds, then throw an IndexOutOfBoundsException. If the list is empty, then throw a EmptyCollectionException. Returns the object being removed at the index.
6. removeAll – Removes all of a given item. If the list is empty, then throw a EmptyCollectionException.
7. get – Returns the item from a given position. If the position is out of bounds, then throw an IndexOutOfBoundsException.
8. reverse – Reverses 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. This should physically flip the list in memory so that the object at heads is at tails and vice versa. If the list is in ascending order and reverse is called you should end up with the following.
   1. List: a b c d e f
   2. reverse is called
   3. List: f e d c b a
   4. reverse is called
   5. List: a b c d e f
9. contains – Takes an element and returns true if the element is in the list and false if it does not.

You should test your code as you see appropriate. Here is an example procedure you may take written in pseudocode. This doesn’t test everything. For instance, what happens if you have an empty list, call reverse, then start adding elements. It should end up in descending order.

sll = new SortedLinkedList<String>()
sll.add(“e”)

sll.add(“c”)

sll.add(“a”)

print(sll) //should have output to show a c e. Can look different //like [a, c, e] or (a, c, e) or a c e.
sll.reverse()

print(sll) //e c a.
sll.add(“d”)

print(sll) //e d c a.

sll.reverse()

print(sll) //a c d e.
sll.add(“d”)

sll.add(“d”)

print(sll) //a c d d d e
print(sll.get(5)) //e
print(sll.contains(“d”)) //true
print(sll.contains(“f”)) //false
sll.removeAll(“d”)

print(sll) //a c e
print(sll.getSize()) // 3
sll.removeFromIndex(2)

print(sll) //a c
sll.clear()
sll.removeFromIndex(2) //Should throw an exception

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 it’s sorted position in BigO(N) time. Furthermore, your contains method should also be BigO(N) time. Don’t waste effort trying to implement a binary search as this may result in longer wait times. Linear traversal is fine.

What you need to turn in

All .java files you write to implement the data structure for this assignment. This does not include the already provided class files given to you.

Code that does not compile will result in a 0.