Add an instance variable previous to the Node class in Section 15.2, and supply previous and hasPrevious methods in the iterator.

Complete the following file:

LinkedList.java

import java.util.NoSuchElementException; /** A linked list is a sequence of nodes with efficient element insertion and removal. This class contains a subset of the methods of the standard java.util.LinkedList class. */ public class LinkedList { private Node first; private class Node { public Object data; public Node previous; public Node next; } // TODO: Update the previous field in all mutator methods /** Constructs an empty linked list. */ public LinkedList() { first = null; } /** Returns the first element in the linked list. @return the first element in the linked list */ public Object getFirst() { if (first == null) throw new NoSuchElementException(); return first.data; } /** Removes the first element in the linked list. @return the removed element */ public Object removeFirst() { // TODO: Do you need to update previous? if (first == null) throw new NoSuchElementException(); Object element = first.data; first = first.next; return element; } /** Adds an element to the front of the linked list. @param element the element to add */ public void addFirst(Object element) { // TODO: Do you need to update previous? Node newNode = new Node(); newNode.data = element; newNode.next = first; first = newNode; } /** Returns an iterator for iterating through this list. @return an iterator for iterating through this list */ public ListIterator listIterator() { return new LinkedListIterator(); } private class LinkedListIterator implements ListIterator { private Node position; private Node previous; // TODO: add previous/hasPrevious methods /** Constructs an iterator that points to the front of the linked list. */ public LinkedListIterator() { // TODO: Replace previous field with position.previous expression position = null; previous = null; } /** Moves the iterator past the next element. @return the traversed element */ public Object next() { if (!hasNext()) throw new NoSuchElementException(); previous = position; // Remember for remove if (position == null) position = first; else position = position.next; return position.data; } /** Tests if there is an element after the iterator position. @return true if there is an element after the iterator position */ public boolean hasNext() { if (position == null) return first != null; else return position.next != null; } /** Adds an element before the iterator position and moves the iterator past the inserted element. @param element the element to add */ public void add(Object element) { if (position == null) { addFirst(element); position = first; } else { // TODO: Do you need to update previous? Node newNode = new Node(); newNode.data = element; newNode.next = position.next; position.next = newNode; position = newNode; } previous = position; } /** Removes the last traversed element. This method may only be called after a call to the next() method. */ public void remove() { if (previous == position) throw new IllegalStateException(); if (position == first) { removeFirst(); } else { // TODO: Do you need to update previous? previous.next = position.next; } position = previous; } /** Sets the last traversed element to a different value. @param element the element to set */ public void set(Object element) { if (position == null) throw new NoSuchElementException(); position.data = element; } } }

Use the following file:

ListTester.java

/**
   A program that demonstrates the LinkedList class
*/
public class ListTester
{  
   public static void main(String[] args)
   {  
      LinkedList names = new LinkedList();
      names.addFirst("Tom");
      names.addFirst("Romeo");
      names.addFirst("Harry");
      names.addFirst("Dick");
      
      // | in the comments indicates the iterator position

      ListIterator iterator = names.listIterator(); // |DHRT
      iterator.next(); // D|HRT
      iterator.next(); // DH|RT

      // Add more elements after second element
      
      iterator.add("Juliet"); // DHJ|RT
      iterator.add("Nina"); // DHJN|RT

      iterator.next(); // DHJNR|T

      // Remove last traversed element 

      iterator.remove(); // DHJN|T
     
      // Print all elements

      iterator = names.listIterator();
      while (iterator.hasNext())
         System.out.print(iterator.next() + " ");
      System.out.println();
      System.out.println("Expected: Dick Harry Juliet Nina Tom");
      while (iterator.hasPrevious())
         System.out.print(iterator.previous() + " ");
      System.out.println();
      System.out.println("Expected: Tom Nina Juliet Harry Dick");
   }
}