Iterators and Linked List removal

This assignment requires you to modify the existing code for Linked Lists. Specifically, you must take the existing code for Linked Lists, and make it implement the iterator method of the java.lang.Iterable interface. In implementing your iterator, you may make use of the code in LinkedListIterator. However, that code does not provide an implementation for the remove method, so you must provide that implementation.

You must also add to the Linked List class the two remove methods specified by the List interface, and implement them correctly. You also need to provide a size method, as specified by the List interface.

You are welcome to adapt the remove code from the book.

Finally, you must provide a driver program (in a separate class) that gives the user the possibility to exercise each of the methods of both the LinkedList and the iterator classes. This could be similar to your address book class in assignment 4. Your driver program should create a linked list of strings, and allow operations on that linked list.

Specifically, the user must be able to:

add a string at the end of the list: boolean add(E value)

add a string at an arbitrary position in the list: void add(int index, E value)

remove a string at an arbitrary position in the list: E remove(int index)

remove a given string from the list: boolean remove(Object o)

create an iterator

call hasNext, next, and remove on the iterator, showing the results of each call

Your driver program should correctly handle any exceptions thrown by any of these methods, print an appropriate message, and continue operation.

==============================================================================================

public class LinkedList {

// here, include the LinkedNode definition

private static class LinkedNode { private T item; private LinkedNode next; /** * constructor to build a node with no successor * @param the value to be stored by this node */ private LinkedNode(T value) { item = value; next = null; } /** * constructor to build a node with specified (maybe null) successor * @param the value to be stored by this node * @param the next field for this node */ private LinkedNode(T value, LinkedNode reference) { item = value; next = reference; } } // end of the LinkedNode definition

// this is the start of the linked list. If the list is empty, it is null protected LinkedNode head; // this is the end of the linked list. If the list is empty, it is null protected LinkedNode tail; protected int size;

// there are some relationships between the class variables. This // method checks that these relationships always hold. Any // property that always holds is called an invariant.

// the property may not hold in the middle of a method, // so only call this at the beginning or end of a public method.

/** * checks assertion * @throws java.lang.AssertionError if the assertion is not true */ private void verify(boolean mustBeTrue) { if (! mustBeTrue) { throw new java.lang.AssertionError("assertion error"); } }

/** * checks class invariants * @throws java.lang.AssertionError if the invariant is violated */ private void checkInvariants() { // uncomment the next line to skip the checks: // return; // either head and tail are both null, or neither is null. // size is zero if and only if they are null, and otherwise is positive verify((head == null) == (tail == null)); verify((size == 0) == (head == null)); verify(size >= 0); // if the list only has one element, head should be the same as tail // (and also if the list has no elements), otherwise they should differ verify((head == tail) == (size <= 1)); // a non-null tail variable should always have a null "next" field verify((tail == null) || (tail.next == null)); // check to make sure size is the same as the length of the list. // this code takes O(n), so comment it out if performance is important int measuredSize = 0; LinkedNode node = head; // if visitedLast is null, the list is empty, and tail should also be null LinkedNode visitedLast = null; while (node != null) { visitedLast = node; node = node.next; measuredSize++; } verify(measuredSize == size); // also make sure "last" really is the last node in the linked list verify(visitedLast == tail); }

/** * initializes an empty linked list */ public LinkedList() { head = null; tail = null; size = 0; // one of the constructor's jobs is to make sure that the invariants hold. checkInvariants(); }

// these private (helper) methods simplify implementation of // the public "add" methods // the helper methods never modify "size", the public methods // take care of that, so the invariants probably do not hold at the end of // a helper methods

/** * adds at the head of the list * @param the value to be added */ private void addAtFront(E value) { head = new LinkedNode(value, head); if (tail == null) { tail = head; } }

/** * adds at the tail of the list. Assumes (and checks) that tail is not null * @param the value to be added * @throws RuntimeException */ private void addAtEnd(E value) { if (tail == null) { throw new RuntimeException ("invalid call to addAtEnd, tail is null"); } LinkedNode newNode = new LinkedNode(value); tail.next = newNode; tail = newNode; }

/** * adds a value to the list after the given node * @param the node after which the new value is added * @param the value to be added */ private void addAfter(LinkedNode reference, E value) { LinkedNode newNode = new LinkedNode(value, reference.next); reference.next = newNode; if (reference == tail) { // if added at end, update tail value tail = newNode; } }

/** * adds a value to the end of the list * @param the value to be added * @return true (the add always succeeds) */ public boolean add(E value) { checkInvariants(); // useful for debugging if (head != null) { addAtEnd (value); } else { addAtFront (value); } size++; checkInvariants(); // invariants valid at start, are they still valid? // i.e., did this method break the invariants? return true; }

/** * returns the node at the requested position, may take time O(n) * @param the position of the requested node, 0 for the head node * @return the requested node * @throws NullPointerException if the index is larger than the linked list */ private LinkedNode nodeAtPosition(int index) { verify (index >= 0); LinkedNode result = head; while (index > 0) { result = result.next; index--; } verify (result != null); return result; }

/** * adds a value to the list, in the given position * @param the position at which to add: 0 to add at the start * @param the value to be added * @throws IndexOutOfBoundsException if the index is less than 0 * or greater than the number of elements in the linked list */ public void add(int index, E value) { checkInvariants(); if ((index < 0) || (index > size)) { String badIndex = new String ("index " + index + " must be between 0 and " + size); throw new IndexOutOfBoundsException(badIndex); } if (index == 0) { addAtFront (value); } else { addAfter (nodeAtPosition (index - 1), value); } size++; checkInvariants(); }

/** * concatenates the elements of the linked list, separated by " ==> " * @return the string representation of the list */ public String toString() { checkInvariants(); LinkedNode node = head; StringBuffer result = new StringBuffer(); while (node != null) { result.append (node.item.toString()); node = node.next; if (node != null) { result.append (" ==> "); } } checkInvariants(); // make sure we didn't break anything return result.toString(); }

/** * unit test method -- basic testing of the functionality * @param required, ignored */ public static void main (String [] arguments) { LinkedList ll = new LinkedList(); System.out.println (ll); ll.add ("foo"); System.out.println (ll); ll.add (1, "bar"); System.out.println (ll); ll.add ("baz"); System.out.println (ll); ll.add (0, "hello"); System.out.println (ll); ll.add (1, "world"); System.out.println (ll); }

private class LinkedListIterator implements java.util.Iterator { private LinkedNode current;

private LinkedListIterator() { current = head; // head is declared in the enclosing class }

public boolean hasNext() { return (current != null); }

public E next() { if (hasNext()) { E result = current.item; current = current.next; // may be null return result; } // no next element throw new java.util.NoSuchElementException("linked list.next"); }

public void remove() { throw new UnsupportedOperationException ("Linked list iterator remove not supported"); }

} }