A doubly-linked list is a data structure where each element in the list stores the following: a reference to the next element in the list a reference to the previous element in the list The actual...

A doubly-linked list is a data structure where each element in the list stores the following:

1. a reference to the next element in the list


2. a reference to the previous element in the list


3. The actual data stored in the list element.

For the element at the back of the list, the next reference stores null. Likewise, for the element at the front of the list, the previous element stores null.

In addition, the list itself stores the following:

1. A reference to the first element in the list


2. A reference to the last element in the list.

For this assignment you will create aclass for creating doubly linked liststhat can storeany variable type that implements the Comparable interface.

Your class must be declared as follows:

public class DoublyLinkedList>

There is an excellent discussion of the Comparable interface at the start of chapter 2.1 in Sedgewick -- I recommend using that as your primary reference. For a more detailed discussion of the Comparable interface, seeOracle's reference(Links to an external site.).

We haven't covered (and Sedgewick doesn't go into much detail on) the use ofbounded generic typesin this class declaration. The short version of what it means is "this container uses a generic typethat must be Comparable toother variables of that same type."

Feel free to ignore the gory details and just use the line above. In the rest of your class, you can refer to the type that the container stores as justT, just like when using ordinary unbounded generic types.

Your class must have the following methods:

• A constructor that takes no parameters and creates an empty list.


• 
  public void insert(T item)
  

This method inserts the new item into the list,while keeping the list in sorted order(sorted from smallest to largest). This means that you will have to figure out where the new item is supposed to go, and then correctly rewire the list to actually place it there.

• 
  public boolean itemInList(T item)
  

This method returnstrueif the item is already in the list, andfalseotherwise.

• 
  public boolean remove(T item)
  

If the item is already in the list, this method removes it and return true. if the item is not in the list, it returns false and leaves the list unchanged.

• 
  public String toString()
  

Returns a String representation of the contents of the list.

I encourage you to write a main function to extensively test your list -- there are, as you'll discover, a number of edge cases you'll have to consider -- but when I test your program it will be with my own main function.