Create a new class ListCDLSBased that implements the listInterface using circular doubly linked structures with a node head and numItems data field. more instructions below. have a driver to test the code, In java only. circular doubly linked structure only. DSA

In addition please anaylze the space and time complexity of your get, add, and remove method, more instructions below.

public interface ListInterface { boolean isEmpty(); int size(); void add(int index, Object item) throws ListIndexOutOfBoundsException; Object get(int index) throws ListIndexOutOfBoundsException; void remove(int index) throws ListIndexOutOfBoundsException; void removeAll(); String toString(); } // end ListInterface

public class ListIndexOutOfBoundsException extends IndexOutOfBoundsException { public ListIndexOutOfBoundsException(String s) { super(s); } // end constructor } // end ListIndexOutOfBoundsException

//please note that this code is different from the textbook code, because the data is encapsulated! public class Node { private Object item; Node next;

public Node(Object newItem) { item = newItem; next = null; } // end constructor

public Node(Object newItem, Node nextNode) { item = newItem; next = nextNode; } // end constructor

public void setItem(Object newItem) { item = newItem; } // end setItem

public Object getItem() { return item; } // end getItem

public void setNext(Node nextNode) { next = nextNode; } // end setNext

public Node getNext() { return next; } // end getNext } // end class Node

When a circular doubly linked structure (CDLS) is used to implement a List ADT (see below): the node at the back of the list, instead of having a null next link, references the node at the front. the node at the front of the list, instead of having a null back link, references the node at the back. there needs to be an entry point in the CDLS. Assume that that entry is a head reference. If the list is empty head is null, otherwise head.getBack() references the node at the back of the list(tail). Note: No link in the circular doubly linked structure (next or back) can ever be null!!! CDLS structure: head and numItems data fields. DNode structure: head numItems back item next 4 4 31 89 12 Note: The item data field in the DNode class is a reference data field, not a primitive type (int), the way it is depicted only for simplicity in this picture. Problem 1: Implement the ListInterface as well as a toString method using a circular doubly linked structure in class ListCDLSBased and test the functionality of your class using a menu-driven test application with the following options: 0. Exit Program 1. Insert item to list. 2. Remove item from list. 3. Get item from list. 4. Clear list. 5. Display size and content of list. 6. Reverse list. Include in your submission at least a sample run of your program on this input data. Tackle your (non-ExtraCredit) design in 3 steps performed in this order: Stepl: Design the encapsulated node structure (DNode) to include an additional data field called back of type DNode with the necessary functionality. Design the 1-parameter constructor with self-referencing links for next and back. Step2: Design your add and remove methods and test them thoroughly using the "old" find that works with an index in range [0,listsize-1). None of the cases in add or remove should call find more than once. Use the design outline learned in class: develop the code for the general case, check to see if boundary cases need to be treated separately. Make sure that both head and numitems are consistent with the state of the collection at all times and that adding to an empty list and removing from a l-item list correctly updates the 2 data fields. Step3: Redesign and replace the find method with the redesigned find and again thoroughly re-test. You HAVE TO redesign find to efficiently make use of the circular doubly linked structure. Using the old find from ListReference Based would defeat the purpose of this lab. Problem 2: CDLS analysis for a list of n items: a) Space Complexity analysis: Analyze the amount of memory used by the CDLS (exact amount of 4 bytes) b) Time Complexity analysis: Analyze the efficiency of this implementation (include best, worst and average case analysis for methods get, add and remove). When a circular doubly linked structure (CDLS) is used to implement a List ADT (see below): the node at the back of the list, instead of having a null next link, references the node at the front. the node at the front of the list, instead of having a null back link, references the node at the back. there needs to be an entry point in the CDLS. Assume that that entry is a head reference. If the list is empty head is null, otherwise head.getBack() references the node at the back of the list(tail). Note: No link in the circular doubly linked structure (next or back) can ever be null!!! CDLS structure: head and numItems data fields. DNode structure: head numItems back item next 4 4 31 89 12 Note: The item data field in the DNode class is a reference data field, not a primitive type (int), the way it is depicted only for simplicity in this picture. Problem 1: Implement the ListInterface as well as a toString method using a circular doubly linked structure in class ListCDLSBased and test the functionality of your class using a menu-driven test application with the following options: 0. Exit Program 1. Insert item to list. 2. Remove item from list. 3. Get item from list. 4. Clear list. 5. Display size and content of list. 6. Reverse list. Include in your submission at least a sample run of your program on this input data. Tackle your (non-ExtraCredit) design in 3 steps performed in this order: Stepl: Design the encapsulated node structure (DNode) to include an additional data field called back of type DNode with the necessary functionality. Design the 1-parameter constructor with self-referencing links for next and back. Step2: Design your add and remove methods and test them thoroughly using the "old" find that works with an index in range [0,listsize-1). None of the cases in add or remove should call find more than once. Use the design outline learned in class: develop the code for the general case, check to see if boundary cases need to be treated separately. Make sure that both head and numitems are consistent with the state of the collection at all times and that adding to an empty list and removing from a l-item list correctly updates the 2 data fields. Step3: Redesign and replace the find method with the redesigned find and again thoroughly re-test. You HAVE TO redesign find to efficiently make use of the circular doubly linked structure. Using the old find from ListReference Based would defeat the purpose of this lab. Problem 2: CDLS analysis for a list of n items: a) Space Complexity analysis: Analyze the amount of memory used by the CDLS (exact amount of 4 bytes) b) Time Complexity analysis: Analyze the efficiency of this implementation (include best, worst and average case analysis for methods get, add and remove)