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.
// ******************************************************** // Interface ListInterface for the ADT list. // ********************************************************* 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
public class MyListReferenceBased1 implements ListInterface{
private Node head; public boolean isEmpty() {
} public int size() {
} public void add(int index, Object item) throws ListIndexOutOfBoundsException { } public Object get(int index) throws ListIndexOutOfBoundsException {
} public void remove(int index) throws ListIndexOutOfBoundsException {
} public void removeAll() {
} }
For this lab we will use a circular doubly linked structure (CDLS) with a head reference to implement the List ADT. The goal for the doubly linked structure is, as discussed in class, to increase the efficiency of the implementation by reducing the number of links traversed to at most (in the worst case) half the links in the whole linked structure. We will use just one entry point in this linked structure in this case a head reference) in order to eliminate redundancy and reduce the number of data fields that have to be maintained. 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 . 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: Step1: 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 ListReferenceBased 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). Select from the following menu: 0. Exit program. 1. Insert item to list. 2. Remove item from list. 3. Get item from list. 4. Clear list. 5. Print size and content of list. 6. Reverse list. Make your menu selection now: 5 List is empty. Make your menu selection now: 1 You are now inserting an item into the list. Enter item: Data Enter position to insert item in : 0 Item Data inserted in position in the list. Make your menu selection now: 5 List of size 1 has the following items : Data Make your menu selection now: 1 You are now inserting an item into the list. Enter item: Beverly Enter position to insert item in : 0 Item Beverly inserted in position in the list. Make your menu selection now: 5 List of size 2 has the following items : Beverly Data Make your menu selection now: 1 You are now inserting an item into the list. Enter item: Jean-Luc Enter position to insert item in : 4 Position specified is out of range! Make your menu selection now: 5 List of size 2 has the following items : Beverly Data
