Circular Doubly Linked List Objectives To gain experience with implementing reference-based linked list. To learn how to use dummy head node to eliminate the special cases for add and remove operations. To learn how to use doubly linked list to locate the last node directly without a traversal. Description Both the insertion and deletion algorithm for linked lists require a special case to handle action at the first position of a list. To add a dummy head node to the list, the need for handling such special cases can be eliminated. Doubly linked lists with a dummy head node (see Figure below) further eliminates many difficulties inherent in singly linked list. A doubly linked list differs from a singly linked list in that each node has a prev reference to the previous node as well as a next reference to the next node.This additional reference makes it possible to traverse the list in either direction. As the above figure shows, the external reference head always references the dummy head node. Notice that the dummy head node has the same data type as the other nodes in the list; thus it also contains prev and next references. Furthermore, you can link the list so that it becomes a circular doubly linked list. The previous Node class has been modified into the DoublyNode class by introducing the prev reference as well as its associated accessor and mutator. (DoublyNode.java is included) Also, the ListInterface has been extended into the ExtendedListInterface by introducing 6 commonly used operations on list, namely, getFirst, getLast, addFirst, addLast, removeFist and removeLast. (ExtendedListInteface.java is included) In this lab, you will implement the class CircularDoublyLinkedList by completing the following methods. Notice that the methods getFirst, getLast and add have already been implemented in the CircularDoublyLinkedList class. public void remove(int index); public void addFirst(Object newItem); public void addLast(Object newItem); public void removeFirst(); public void removeLast(); The methods addFirst, removeFirst can be implemented by calling either the method add and remove with appropriate parameters, respectively. However, the methods addLast and removeLast must be implemented without calling the method add or remove. This is to avoid a traversal from the beginning of the list to the end of the list, so the algorithm can be more efficient. Notice that the reference to the last node is head.getPrev(). Exercises 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

///////////////////////////////////////////////////////////// // Circular Linked List that implements ExtendedListInterface /////////////////////////////////////////////////////////////

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

public class ListException extends Exception {

public ListException(String s) { System.out.println("ListException: " + s); } }