CS 1332 JAVA HW 2 CIRCULAR SINGLY LINKED LIST. PLEASE HELP!!!!! CORRECT ANSWER GETS A THUMBS UP AND GRATITUDE! ---------------------------------------------------------------------- Circular Singly-Linked List You are to code a circular singly-linked list with a head reference. A linked list is a collection of nodes, each having a data item and a reference pointing to the next node. Since it must be circular, the next reference for the last node in this list will point to the head node. Do not use a phantom node to represent the start or end of your list. A phantom or sentinel node is a node that does not store data held by the list and is used solely to indicate the start or end of a linked list. If your list contains n elements, then it should contain exactly n nodes. Your linked list implementation will implement the LinkedListInterface provided. It will use the default constructor (the one with no parameter) which is automatically provided by Java. Do not write your own constructor. Nodes The linked list consists of nodes. A class LinkedListNode is provided to you. LinkedListNode has setter and getter methods to access and mutate the structure of the nodes. Adding You will implement three add() methods. One will add to the front, one will add to the back, and one will add anywhere in the list. See the interface for more details. Removing Removing, just like adding, can be done from the front, the back, or anywhere in your linked list. In addition, you will also be coding a method to remove the last instance of a piece of data. When removing from the front, the rst node should be removed in such a way that the last node points to the new front of the list (mind the eciency!). When removing from the back, the last node should be removed and have the new last node point to the head. When removing from the middle, the previous node of the removed node should point to the next node of the removed node. Make sure that you set any remaining pointers to the deleted nodes to null since in order for the node to be garbage collected, there cannot be any way to access the node. See the interface for more details. ------------------------------------------------------------------------- /** * This interface describes the expected behavior of the public methods * needed for a circular singly linked list with a head pointer. The required  * efficiencies have also been provided.  *  * DO NOT ALTER THIS FILE!!  *  * @author CS 1332 TAs  * @version 1.0  */ public interface LinkedListInterface { /**  * Adds the element to the index specified.  *  * Adding to indices 0 and {@code size} should be O(1), all other cases are  * O(n).  *  * @param index the requested index for the new element  * @param data the data for the new element  * @throws java.lang.IndexOutOfBoundsException if index is negative or  * index > size  * @throws java.lang.IllegalArgumentException if data is null  */  void addAtIndex(T data, int index); /**  * Adds the element to the front of the list.  *  * Must be O(1) for all cases.  *  * @param data the data for the new element  * @throws java.lang.IllegalArgumentException if data is null.  */  void addToFront(T data); /**  * Adds the element to the back of the list.  *  * Must be O(1) for all cases.  *  * @param data the data for the new element  * @throws java.lang.IllegalArgumentException if data is null.  */  void addToBack(T data); /**  * Removes and returns the element from the index specified.  *  * Removing from index 0 should be O(1), all other cases are  * O(n).  *  * @param index the requested index to be removed  * @return the data formerly located at index  * @throws java.lang.IndexOutOfBoundsException if index is negative or  * index >= size  */  T removeAtIndex(int index); /**  * Removes and returns the element at the front of the list. If the list is  * empty, return {@code null}.  *  * Must be O(1) for all cases.  *  * @return the data formerly located at the front, null if empty list  */  T removeFromFront(); /**  * Removes and returns the element at the back of the list. If the list is  * empty, return {@code null}.  *  * Must be O(n) for all cases.  *  * @return the data formerly located at the back, null if empty list  */  T removeFromBack(); /**  * Removes the last copy of the given data from the list.  *  * Must be O(n) for all cases.  *  * @param data the data to be removed from the list  * @return the removed data occurrence from the list itself (not the data  * passed in), null if no occurrence  * @throws java.lang.IllegalArgumentException if data is null  */  T removeLastOccurrence(T data); /**  * Returns the element at the specified index.  *  * Getting index 0 should be O(1), all other cases are O(n).  *  * @param index the index of the requested element  * @return the object stored at index  * @throws java.lang.IndexOutOfBoundsException if index < 0 or  * index >= size  */  T get(int index); /**  * Returns an array representation of the linked list.  *  * Must be O(n) for all cases.  *  * @return an array of length {@code size} holding all of the objects in  * this list in the same order  */  Object[] toArray(); /**  * Returns a boolean value indicating if the list is empty.  *  * Must be O(1) for all cases.  *  * @return true if empty; false otherwise  */  boolean isEmpty(); /**  * Clears the list of all data.  *  * Must be O(1) for all cases.  */  void clear(); /**  * Returns the number of elements in the list.  *  * Runs in O(1) for all cases.  *  * @return the size of the list  */  int size(); /**  * Returns the head node of the linked list.  * Normally, you would not do this, but it's necessary for testing purposes.  *  * DO NOT USE THIS METHOD IN YOUR CODE.  *  * @return node at the head of the linked list  */  LinkedListNode getHead(); }