Implementation of a variation on the linked list idea that stores its data in two separate orders at once. That is, it stores data in the usual order, based on when it was added by the user.

At the same time, however, it keeps track of an ascending sorted order. To achieve this, it uses a Node class that comes with four separate references.To complete this assignment, you will do the following things (not necessarily in order):

Question 1. Write the constructor for the SortTraversableLinkedList. It should create the head and tail nodes, and set the size of the list to 0, as in a typical linked list.

Question 2. Write the methods used in Section One of the commented-out test code in Main. These methods should work as follows:

• The size() and toString() methods should work in exactly the way they do for normal linked lists, returning the number of elements and a String representation of the list (match the format in the sample output).

• The basic add() method should take in an element of type T and add it to the end of the list (just before the tail), using the next and prev links as usual. At the same time, it should re-arrange any prevSort and nextSort links so that they reflect the sorted order. Since the list class is restricted to Comparable types, you know that any objects that get added to the list will have a compareTo() method. You can use this fact to decide upon the right sorted order. (It should be a least-to-greatest, ascending sort.)

• The second add() method should take in an element of type T, along with an index position at which to add it. It should place the element at that position, using the usual next and prev links, and also re-arrange the other links for the proper sorted order. It should throw an IndexOutOfBoundsException if the given index is not in the proper range of values, just as in a normal linked list.

• The sortedToString() method should return a String that represents the list in its sorted order, again matching the format of the sample output.

When you are done, you should have a list structure that allows insertion of an object at any point in linear O(n) time (we no longer get constant-time O(1) addition to the end of the list, since we have to also re-arrange links to keep the sorted order correct). The trade-off for this extra bit of work here is that we never have to call a method in order to get the list in sorted order-instead, simply traversing the list using the second set of links gives us the sorted order without having to call any sorting algorithms, which can provide significant speed-ups down the road.

Question 3. Write the methods used in Section Two of Main:

• The get() method should work as for a normal linked-list, returning the value at a given position in the list, without changing the list at all, and throwing exceptions if the position requested does not exist.

• The getLeast() and getGreatest() methods should return the least and greatest value in the list, respectively. If you have implemented your list correctly, these methods will each run in constant O(1) time. If the list is empty, the methods should generate a NoSuchElementException.

Question 4. Write the methods used in Section Three of Main:

• The remove() method should work as for a normal linked-list, returning the value at a given position in the list, after removing it from the list, and throwing exceptions if the position requested does not exist.

• The removeLeast() and removeGreatest() methods should remove and return the least and greatest value in the list, respectively. If you have implemented your list correctly, these methods will each run in constant O(1) time. If the list is empty, the methods should generate a NoSuchElementException.

When you write these methods, be sure that you update all of the references required to keep both the insertion and sorted orders working in your list.

Question 5. Write the methods used in Section Four of Main. Each method should return the index of any given input value in the list (indices start at 0). The only differences between the two is that indexOf() should use the normal linked-list order, while sortedIndexOf() should use the sorting order (so that the least element is always at sorted index 0 and the greatest at size() - 1). Both methods should return value -1 if the element sought does not occur in the list at all.

Question 6. Write the methods used in Section Five of Main. To do this, you will have to make your list class properly Iterable and write two separate Iterator implementations inside it. The first one, returned by the usual iterator() method, should work as usual for a linked list, returning elements in the order they were inserted. The second one, returned by the sortedIterator() method, should use the ascending sorted order. Note: by default, the regular iterator will be used when using for-each looping. If you want to loop in sorted order, you will need to explicitly generate the special sorting iterator to do so.

Question 7. Write the methods used in Section Six of Main. Each of these will take in an array of the same type as the list, and return an array of the same type, containing all of its elements. As usual, the normal toArray() method will generate an array containing elements in the normal insertion order, whereas sortedToArray() will return an array containing elements in ascending sorted order. Note: you should not call any algorithms to actually sort any data to accomplish all this-you already have a list that can be put into an array in sorted order directly. Thus, both array conversion methods should run in linear O(n) time.