Iterators

Create a new Java project.

First, add the following interface to this project:

import java.util.Iterator;

public interface TwoWayIterator extends Iterator {

public boolean hasPrevious();

public ValueType previous();

}

This interface specifies an iterator with two additional methods: hasPrevious() and previous(), which function similarly to hasNext() and next() in a standard iterator.

Second, add the DoublyLinkedList class to the project, and add an inner class that implements TwoWayIterator. You'll need to implement the next() and hasNext()methods and the two additional methods previous() and hasPrevious(), which are implemented similarly.

Third, have your DoublyLinkedList class implement Javas Iterable interface. Remember that the Iterable interface has a single required method: iterator(). This function should return an instance of your TwoWayIterator inner class from the previous step. (Hint: this should have the signature "public TwoWayIterator iterator()").

DoublyLinkedList class:

public class DLList { private Node header; private Node trailer; private int size; public DLList() { header = new Node<>(null, null, null); trailer = new Node<>(null, null, header); header.next = trailer; size = 0; } /** * This method inserts value v in a new node bteween first and second * @param v value to insert * @param first first node * @param second second node */ private void insertBetween(E v, Node first, Node second) { Node newNode = new Node<>(v, second, first); second.prev = newNode; first.next = newNode; size++; } private E removeBetween(Node first, Node second) throws IllegalStateException { if(header.next == trailer) //if(size == 0) { throw new IllegalStateException("Cannot delete from empty list"); } E valueToReturn = first.next.value; first.next = second; second.prev = first; size--; return valueToReturn; } public void insertAtHead(E v) { insertBetween(v, header, header.next); } public void insertAtTail(E v) { insertBetween(v, trailer.prev, trailer); } public E removeHead() throws IllegalStateException { return removeBetween(header, header.next); } public E removeTail() throws IllegalStateException { return removeBetween(trailer.prev, trailer); } public String toString() { if(size == 0) { return "list is empty!"; } String r = ""; Node temp = header.next; while(temp != trailer) { r += temp.toString() + " "; temp = temp.next; } return r; } public void printBackward() { if(size == 0) { System.out.println("list is empty!"); } Node temp = trailer.prev; while(temp != header) { System.out.print(temp + " "); temp = temp.prev; } System.out.println();

} private static class Node { private T value; private Node next; private Node prev; public Node(T v, Node n, Node p) { value = v; next = n; prev = p; } public String toString() { return value.toString(); } }

}

Finally, create a Driver class with a main method that:

Tests your TwoWayIterator by iterating forward and backward through a doubly linked list

Tests your TwoWayIterator on doubly linked lists of varying sizes