import java.util.*;

/**
 * Linkedlist127 -- a singly linked list developed in class by CS127 
 *                  on 16 and 18 January 2006.
 *
 * David Liben-Nowell (skeleton only)
 * Carleton College Winter 2006 CS 127 class (everything else).
 * 
 */
class LinkedList127<E> {

    /**
     * The nested Node class -- it's static to prevent us from doing
     * anything stupid, like fiddling with LinkedList instance variables.
     */
    private static class Node<E> {
        public E data;            // the value stored in this node.
        public Node<E> successor; // the node after this one in the list,
                                  // or null if this node is the last.
    }


    
    private Node<E> head;  // the first node in the list, or null if the
                           // list is empty.

    private Node<E> tail;  // the last node in the list, or null if empty.

    private int size;      // the number of elements in the list.

    /**
     * Constructor -- creates an empty list.
     */
    public LinkedList127() {
        head = null;
        size = 0;
        tail = null;
    }

    /**
     * Returns a string version of the list.
     */
    public String toString() {
        String str = "";
        Node<E> current = head;

        while (current != null) {
            str = str + " -> [" + current.data + "]";
            current = current.successor;
        }
        return str;
    }


    /**
     * Returns the (index)th node in the list.
     */
    private Node<E> getNode(int index)  throws IndexOutOfBoundsException {
        if (index < 0 || index >= this.size() ) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> current = head;
        int counter = 0;
        while (counter < index) {
            current = current.successor;
            counter++;
        }
        return current;
    }

    /**
     * Returns the value stored in the (index)th node in the list.
     */
    public E get(int index) {
        return getNode(index).data;
    }

    /**
     * Adds a new node with value x at the beginning of list.
     */
    public void prepend(E x) {
        Node<E> newNode = new Node<E>();
        newNode.data = x;
        newNode.successor = head;
        head = newNode;
        size++;
        if (size == 1) {  // we just added the only node in the list
            tail = head;
        }
    }

    /**
     * Adds a new node with value x at the end of list.
     */
    public void append(E x) {
        if (head == null) {
            prepend(x);
        } else {
            // current.successor is null, so current is the last node in list.
            Node<E> newNode = new Node<E>();
            newNode.data = x;
            newNode.successor = null;
            tail.successor = newNode;
            tail = newNode;
            size++;
        }
    }

    /**
     * Returns the number of nodes in the list.
     */
    public int size() {
        return size;
    }

    /**
     * Deletes the (index)th node in the list.
     */
    public void delete(int index) {
        if (index == 0) {
            head = head.successor;
            size--;
            if (size == 0) { // list is now empty
                tail = null;
            }
        } else if (index >= this.size()) {
            throw new IndexOutOfBoundsException();
        } else {
            Node<E> previousNode = getNode(index-1);
            if (index == size-1) { // we're deleting the old tail
                tail = previousNode; 
            }
            previousNode.successor = previousNode.successor.successor;
            size--;
        }
    }

    /**
     * The nested Iterator class -- it's NOT static because we need
     * access to "head".
     */
    private class LLIterator implements Iterator<E> {
        Node<E> current;   // the "bookmark" of the iterator.

        // constructor -- bookmark initially begins at the head of the list.
        public LLIterator() {
            current = head;
        }

        // hasNext -- there's a next element to report unless we're at the end.
        public boolean hasNext() {
            return (current != null);
        }
        
        // next -- return the next element to report, and advance current.
        public E next() {
            E elmt = current.data;
            current = current.successor;
            return elmt;
        }

        // remove -- would delete the just-reported element if
        // written.  (Note that this requires some changes in the
        // above, because in this implementation you can't access the
        // element you just reported, because current has already
        // moved on.)
        public void remove() {
            throw new UnsupportedOperationException("remove not implemented");
        }

    }

    // == "give me a new iterator for this list."
    public LLIterator iterator() {
        return new LLIterator();
    }
    

}