Create a new class ListCDLSBased with a node head field that follows the problem below and have a driver to test the code, In java only. circular doubly linked structure only.
// ******************************************************** // 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() {
} }
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!!! 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 ListReferenceBased would defeat the purpose of this lab. Note: You should build DNode on the Node class frame and re-use driver from Lab 3 instead of starting from scratch. Just remove the deleteLargest option and move up the last 2 cases. Use the reverse as implemented in the Lab 3 driver. Make sure your implementation doesn't leave the CDLS in an inconsistent state. ExtraCredit I: Design a new find method that works with an index in an extended range. Design add and remove to use it efficiently (these methods will not work with the old find, as it cannot handle indices beyond [0, listsize-1]) 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
