Data Structures and Algorithms (Circular doubly linked structure problem.)
Please code in java and use CDLS to fill the methods for the implement class ListCDLS. create a driver to test the methods
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
//please note that this code is different from the textbook code, because the data is encapsulated! public class DNode { private Object item; DNode next; DNode back;
public DNode(Object newItem) { this.item = newItem; this.next = null; this.back = null; } // end constructor
public DNode(Object newItem, DNode nextNode, DNode backNode) { item = newItem; next = nextNode; back = backNode; } // end constructor
public void setItem(Object newItem) { item = newItem; } // end setItem
public Object getItem() { return item; } // end getItem
public void setNext(DNode nextNode) { next = nextNode; } // end setNext
public DNode getNext() { return next; } // end getNext public void setBack(DNode backNode) { back = backNode; } // end setBack public DNode getBack() { return back; } // end getBack } // end class Node
public class ListCDLS implements ListInterface {
private DNode head; private int numItems; @Override public boolean isEmpty() {
}
@Override public int size() {
}
@Override public void add(int index, Object item) throws ListIndexOutOfBoundsException {
}
@Override public Object get(int index) throws ListIndexOutOfBoundsException {
}
@Override public void remove(int index) throws ListIndexOutOfBoundsException {
}
@Override public void removeAll() {
} public String toString() { } private DNode find(int index) { // Locates a specified node in a linked list } }
Test sample:
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. 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 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. 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
