1.Download the following class source files. ? CircularDoublyLinkedListTest.java
ID: 3702198 • Letter: 1
Question
1.Download the following class source files.
? CircularDoublyLinkedListTest.java
? CircularDoublyLinkedList.java (the only source file that you must change!)
? DoublyNode.java
? ExtendedListInterface.java
? ListException.java
2. In Eclipse, create a new Java project called "Lab 8 ", and import the above 5 files into a default package.
3. Compile and run the program. It should print out the following messages:
aa, bb, cc, dd, ee.
aa, bb, cc, dd, ee.
ListException: displayList on an empty list
ListException: displayList on an empty list
4. Implement the class called CirularDoublyLinkedList by completing the following methods:
? public void remove (int index) throws ListException;
? public void addFirst(Object newItem) throws ListException;
? public void addLast(Object newItem) throws ListException;
? public void removeFirst() throws ListException;
? public void removeLast() throws ListException;
5. Your program should print out exactly the following messages:
aa, bb, cc, dd, ee.
aa, bb, dd, ee.
aa, bb, cc.
bb.
ListException: displayList on an empty list ListException: removeLast on an empty list
Classes
public class ListException extends Exception {
public ListException(String s) {
System.out.println("ListException: " + s);
}
}
public class CircularDoublyLinkedList implements ExtendedListInterface {
private DoublyNode head; // the head reference to the dummy head node
private int numItems; // number of items in list
public CircularDoublyLinkedList() {
numItems = 0;
// create a dummy head node
head = new DoublyNode(null);
head.setPrev(head);
head.setNext(head);
}
public boolean isEmpty() {
return numItems == 0;
}
public int size() {
return numItems;
}
// -------------------------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the desired node. Assumes that
// 1 <= index <= numItems+1
// Postcondition: Returns a reference to the desired node.
// -------------------------------------------------------------------
private DoublyNode find(int index) {
DoublyNode curr = head;
// due to the dummy head, we skip nodes for index times
for (int skip = 1; skip <= index; skip++) {
curr = curr.getNext();
}
return curr;
}
public Object get(int index) throws ListException {
if (index >= 1 && index <= numItems) {
// get reference to node, then data in node
DoublyNode curr = find(index);
Object dataItem = curr.getItem();
return dataItem;
} else {
throw new ListException("List index out of bounds exception " +
"on get: " + index);
}
}
// Reuse the get method with appropriate parameter
public Object getFirst() throws ListException {
if (size() >= 1) {
return get(1);
} else {
throw new ListException("getFirst on an empty list");
}
}
// To locate the last node without a traversal, DO NOT call the method get
// in this method. Access the last node through head.getPrev().
public Object getLast() throws ListException {
if (size() >= 1) {
DoublyNode lastNode = head.getPrev();
return lastNode.getItem();
} else {
throw new ListException("getLast on an empty list");
}
}
// Insert the new node containing item at position index. Refer to
// Figure 4-30 in the textbook on page 196.
public void add(int index, Object item) throws ListException {
// due to the dummy head, index == 1 is not a special case!
if (index >= 1 && index <= numItems+1) {
DoublyNode prev = find(index-1);
DoublyNode curr = prev.getNext();
DoublyNode newNode = new DoublyNode(item);
newNode.setPrev(prev);
newNode.setNext(curr);
prev.setNext(newNode);
curr.setPrev(newNode);
numItems++;
} else {
throw new ListException("List index out of bounds exception " +
"on add: " + index);
}
}
// Reuse the method add in this method with appropriate parameter.
public void addFirst(Object item) throws ListException {
// ToDo 1.
}
// To locate the last node without a traversal, DO NOT call the method add
// in this method.
public void addLast(Object item) throws ListException {
// ToDo 2.
}
// Delete the node at position index of the list. Refer to Figure 4-29
// in the textbook on page 195.
public void remove(int index) throws ListException {
// ToDo 3.
}
// Reuse the method remove in this method with appropriate parameter.
public void removeFirst() throws ListException {
// ToDo 4.
}
// To locate the last node without a traversal, DO NOT call the method remove
// in this method.
public void removeLast() throws ListException {
// ToDo 5.
}
public void removeAll() {
// create a dummy head
head = new DoublyNode(null);
head.setPrev(head);
head.setNext(head);
numItems = 0;
}
}
public class CircularDoublyLinkedListTest {
// Displays the items on the list aList
public static void displayList(ExtendedListInterface aList) throws ListException {
Object dataItem;
for (int index = 1; index < aList.size(); index++){
dataItem = aList.get(index);
System.out.print(dataItem + ", ");
}
if (aList.size() >= 1) {
dataItem = aList.get(aList.size());
System.out.println(dataItem + ".");
} else {
throw new ListException("displayList on an empty list");
}
}
public static void main(String[] args) {
CircularDoublyLinkedList aList = new CircularDoublyLinkedList();
try {
aList.add(1, "aa");
aList.add(2, "bb");
aList.add(3, "cc");
aList.add(4, "dd");
aList.add(5, "ee");
displayList(aList);
aList.remove(3);
displayList(aList);
} catch (ListException e) {}
try {
aList.removeAll();
aList.addFirst("bb");
aList.addFirst("aa");
aList.addLast("cc");
displayList(aList); // print out "aa, bb, cc."
aList.removeFirst();
aList.removeLast();
displayList(aList); // print out "bb."
aList.removeLast();
displayList(aList); // print out "ListException: displayList on an empty list"
} catch(ListException e) {}
try {
aList.removeLast(); // a ListException is thrown from the called method
displayList(aList); // this statement is ignored
} catch (ListException e) {}
}
}
public class DoublyNode {
private Object item;
private DoublyNode prev;
private DoublyNode next;
// constructors
public DoublyNode() {}
public DoublyNode(Object newItem) {
item = newItem;
prev = null;
next = null;
}
public DoublyNode(Object newItem, DoublyNode prevNode, DoublyNode nextNode) {
item = newItem;
prev = prevNode;
next = nextNode;
}
// mutators
public void setItem(Object newItem) {
item = newItem;
}
public void setPrev(DoublyNode prevNode) {
prev = prevNode;
}
public void setNext(DoublyNode nextNode) {
next = nextNode;
}
// accessors
public Object getItem() {
return item;
}
public DoublyNode getPrev() {
return prev;
}
public DoublyNode getNext() {
return next;
}
}
public interface ExtendedListInterface {
public boolean isEmpty();
// Determines whether a list is empty.
// Precondition: None.
// Postcondition: Returns true if the list is empty, otherwise returns false.
public int size();
// Determines the length of a list.
// Precondition: None.
// Postcondition: Returns the number of items that are currently in the list.
public void add(int index, Object item) throws ListException;
// Adds an item to the list at position index.
// Precondition: index indicates the position at which the item should be
// inserted in the list.
// Postcondition: If 1 <= index <= size()+1, item is added at position index
// in the list, and other items are renumbered accordingly.
public void addFirst(Object item) throws ListException;
// Adds an item to the list at the begining of the list.
// Precondition: None.
// Postcondition: Item is added at the beginning of the list, and other items
// are renumbered accordingly.
public void addLast(Object item) throws ListException;
// Adds an item at the end of the list.
// Precondition: None.
// Postcondition: Item is added at the end of the list, and other items are
// renumbered accordingly.
public Object get(int index) throws ListException;
// Retrieves a list item by position.
// Precondition: index is the position of the item to be retrieved.
// Postcondition: If 1 <= index <= size(), the item at position index in the
// list is returned.
public Object getFirst() throws ListException;
// Retrieves the first item in a list.
// Precondition: None.
// Postcondition: If size() >= 1, the item at the beginning of the list is
// returned.
public Object getLast() throws ListException;
// Retrieves the last item in the list.
// Precondition: None.
// Postcondition: If size() >= 1, the item at the end of the list is returned.
public void remove(int index) throws ListException;
// Deletes an item from the list at a given position.
// Precondition: index indicates where the deletion should occur.
// Postcondition: If 1 <= index <= size(), the item at position index in the
// list is deleted, and other items are renumbered accordingly.
public void removeFirst() throws ListException;
// Deletes the first item from the list.
// Precondition: None.
// Postcondition: If size() >= 1, the first item in the list is deleted, and
// other items are renumbered accordingly.
public void removeLast() throws ListException;
// Deletes the last item from the list.
// Precondition: None.
// Postcondition: If size() >= 1, the item at the end of the list is deleted,
// and other items are renumbered accordingly.
public void removeAll();
// Deletes all the items from the list.
// Precondition: None.
// Postcondition: The list is empty.
}
Explanation / Answer
Please upvote if you find the answer satisfactory :)
Comment on the answer if you face any issue/need any clarifications :)
The following class is the only class changed : rest of the classes are as given
CircularDoublyLinkedList? CLASS
public class CircularDoublyLinkedList implements ExtendedListInterface {
private DoublyNode head; // the head reference to the dummy head node
private int numItems; // number of items in list
public CircularDoublyLinkedList() {
numItems = 0;
// create a dummy head node
head = new DoublyNode(null);
head.setPrev(head);
head.setNext(head);
}
public boolean isEmpty() {
return numItems == 0;
}
public int size() {
return numItems;
}
// -------------------------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the desired node. Assumes that
// 1 <= index <= numItems+1
// Postcondition: Returns a reference to the desired node.
// -------------------------------------------------------------------
private DoublyNode find(int index) {
DoublyNode curr = head;
// due to the dummy head, we skip nodes for index times
for (int skip = 1; skip <= index; skip++) {
curr = curr.getNext();
}
return curr;
}
public Object get(int index) throws ListException {
if (index >= 1 && index <= numItems) {
// get reference to node, then data in node
DoublyNode curr = find(index);
Object dataItem = curr.getItem();
return dataItem;
} else {
throw new ListException("List index out of bounds exception " +
"on get: " + index);
}
}
// Reuse the get method with appropriate parameter
public Object getFirst() throws ListException {
if (size() >= 1) {
return get(1);
} else {
throw new ListException("getFirst on an empty list");
}
}
// To locate the last node without a traversal, DO NOT call the method get
// in this method. Access the last node through head.getPrev().
public Object getLast() throws ListException {
if (size() >= 1) {
DoublyNode lastNode = head.getPrev();
return lastNode.getItem();
} else {
throw new ListException("getLast on an empty list");
}
}
// Insert the new node containing item at position index. Refer to
// Figure 4-30 in the textbook on page 196.
public void add(int index, Object item) throws ListException {
// due to the dummy head, index == 1 is not a special case!
if (index >= 1 && index <= numItems+1) {
DoublyNode prev = find(index-1);
DoublyNode curr = prev.getNext();
DoublyNode newNode = new DoublyNode(item);
newNode.setPrev(prev);
newNode.setNext(curr);
prev.setNext(newNode);
curr.setPrev(newNode);
numItems++;
} else {
throw new ListException("List index out of bounds exception " +
"on add: " + index);
}
}
// Reuse the method add in this method with appropriate parameter.
public void addFirst(Object item) throws ListException {
add(1,item);
}
// To locate the last node without a traversal, DO NOT call the method add
// in this method.
public void addLast(Object item) throws ListException {
// ToDo 2.
DoublyNode newNode = new DoublyNode(item);
if (size() >= 1) {
DoublyNode lastNode=(DoublyNode) head.getPrev();
newNode.setNext(head);
newNode.setPrev(lastNode);
lastNode.setNext(newNode);
head.setPrev(newNode);
numItems++;}
else{
head=newNode;
}
}
// Delete the node at position index of the list. Refer to Figure 4-29
// in the textbook on page 195.
public void remove(int index) throws ListException {
DoublyNode curr=null;
if (index >= 1 && index <= numItems) {
curr = find(index);
DoublyNode prev=curr.getPrev();
DoublyNode next=curr.getNext();
prev.setNext(next);
next.setPrev(prev);
numItems--;
} else {
throw new ListException("List index out of bounds exception " +
"on remove: " + index);
}
}
// Reuse the method remove in this method with appropriate parameter.
public void removeFirst() throws ListException {
// ToDo 4.
remove(1);
}
// To locate the last node without a traversal, DO NOT call the method remove
// in this method.
public void removeLast() throws ListException {
if(numItems>0){
DoublyNode lastNode=(DoublyNode) head.getPrev();
DoublyNode prev=lastNode.getPrev();
DoublyNode next=lastNode.getNext();
if(prev!=null)
prev.setNext(next);
if(next!=null)
next.setPrev(prev);
numItems--;
}
else
{
throw new ListException("removeLast on an empty list");
}
}
public void removeAll() {
// create a dummy head
head = new DoublyNode(null);
head.setPrev(head);
head.setNext(head);
numItems = 0;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.