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. }