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<E> {
    private Node first;

    /**
     * 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 E getFirst() {
        if (first == null)
            throw new NoSuchElementException();
        return first.data;
    }

    /**
     * Removes the first element in the linked list.
     *
     * @return the removed element
     */
    public E removeFirst() {
        if (first == null)
            throw new NoSuchElementException();
        E 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(E element) {
        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<E> listIterator() {
        return new LinkedListIterator();
    }

    private class Node {
        public E data;
        public Node next;
    }

    /**
     * A list iterator allows access to a position in a linked list.
     *
     *
     * Example: when the iterator has not started
     * .........first--> NODE --> NODE --> NODE --> NODE --> null
     * .........prev --> null
     * .........pos --> null         
     *
     * Example: in the middle of a list
     * .........first--> NODE --> NODE --> NODE --> NODE --> null
     * ...........................prev.....pos
     * ----------------------------------------------------------
     */
    private class LinkedListIterator implements ListIterator<E> {
	/** the current node available in the linked list */
        private Node position; 
	/** the previous node available in the linked list */
        private Node previous; 

        /**
         * Constructs an iterator that will start at front of the linked list.
         */
        public LinkedListIterator() {
	    // both are null until we start traversing the list
            position = null;
            previous = null;
        }

        /**
         * Moves the iterator to the next element.
	 * If there is no next element, throws an exception.
         *
	 * @return the traversed element
         */
	 // Example: calling next when we havent started yet
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //          prev --> null
	 //          pos --> null         
	 // becomes  first--> NODE --> NODE --> NODE --> NODE --> null
	 //                   pos
	 //          prev --> null
	 //
	 // Example: calling next on a legal state
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                            prev     pos
	 // becomes  first--> NODE --> NODE --> NODE --> NODE --> null
	 //                                     prev     pos
	 //
	 // Example: calling next in an illegal state (see add for illegal states)
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                                     pos
	 //                                     prev
	 // becomes  first--> NODE --> NODE --> NODE --> NODE --> null
	 //                                     prev     pos
	 // calling next fixes the illegal state
        public E next() {
            if (!hasNext())
                throw new NoSuchElementException();

	    // Update the previous reference
            previous = position; 

	    // if we havent started yet, begin on the first node
	    // position is now first and previous is null since there
	    // is no node before the first
            if (position == null)
                position = first;

	    // or go on to the next node
	    // position is now the next node and previous is right behind it
            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
         */
	 // Example: calling hasNext when we havent started yet
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //          prev --> null
	 //          pos --> null         
	 // answer is true
	 //
	 // Example: calling hasNext when the list is empty
	 //          first--> null
	 //          prev --> null
	 //          pos --> null         
	 // answer is false
	 //
	 // Example: calling hasNext when we are in the middle
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                            prev     pos
	 // answer is true
	 //
	 // Example: calling hasNext when we are at the end
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                                     prev     pos
	 // answer is false
        public boolean hasNext() {
	    // if we haven't started yet, the next node would be the first node
            if (position == null)
                return (first != null);

	    // otherwise, look at the next node
            else
                return position.next != null;
        }

        /**
         * Adds an element after the iterator position and moves the iterator
         * on to the inserted element. Add always leaves the iterator in a
         * state where we cannot call remove.
	 * 
	 * @param element
         *            the element to add
         */
	 // Example: adding an elemement NEW when we havent started yet
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //          prev --> null
	 //          pos --> null         
	 // becomes  first--> NEW --> NODE --> NODE --> NODE --> NODE --> null
	 //                   pos
	 //                   prev  and we are in an illegal state
         //
	 // Example: adding an element NEW in the middle
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                            prev     pos
	 // becomes  first--> NODE --> NODE --> NODE --> NEW --> NODE --> null
	 //                                              pos
	 // and we are in an illegal state               prev
         public void add(E element) {
	    // if we haven't started yet, this element will go first
	    // and position will point to it. previous stays null
            if (position == null) {
                addFirst(element);
                position = first;
            } 

	    // otherwise, insert a new node after this position
	    // and position will then point to it
	    else {
                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.
	 */
	 // Example: remove when we have not started yet
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //          prev --> null
	 //          pos --> null         
	 // throws exception
	 //
	 // Example: remove on an illegal state
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                                     pos
	 //                                     prev
 	 // throws exception
	 //
	 // Example: remove the first node
 	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                   pos
 	 //          prev --> null
	 // becomes  first--> NODE --> NODE --> NODE --> null
 	 //          prev --> null
	 //          pos --> null      and we are in an illegal state
	 //
	 // Example: remove a middle node
	 //          first--> NODE --> NODE --> NODE --> NODE --> null
	 //                            prev     pos
	 // becomes  first--> NODE --> NODE --> NODE --> null
	 //                            pos
	 //                            prev    and we are in an illegal state
         public void remove() {
	    // if we added a node but have not called next yet, its illegal
            if (previous == position)
                throw new IllegalStateException();

	    // if we are on the first node
            if (position == first) {
                removeFirst();
            } 

	    // else we are on a middle node
	    else {
                previous.next = position.next;
            }

	    // update position
            position = previous;
        }

        /**
         * Sets the last traversed element to a different value.
         *
         * @param element
         *            the element to set
         */
        public void set(E element) {
            if (position == null)
                throw new NoSuchElementException();
            position.data = element;
        }
    }
}