import java.util.*;

/** Class LListReview implements a double linked list and
 *  a ListIterator.
 * */

public class LListReview<E> {
  // Data Fields
  private NodeR <E> head = null;
  private NodeR <E> tail = null;
  private int size = 0;

  //Methods
  
  public LListReview()
  { head = null; tail = null; size = 0; }

  /** Add an item at the specified index.
      @param index The index at which the object is to be
             inserted
      @param obj The object to be inserted
      @throws IndexOutOfBoundsException if the index is out
              of range (i < 0 || i > size())
   */
  public void add(int index, E obj) {
        ListIterator<E> iter = listIterator(index);
        iter.add(obj);
  }

  /** Get the element at position index.
      @param index Position of item to be retrieved
      @return The item at index
   */
  public E get(int index) {
      ListIterator<E> iter = listIterator(index);
      return iter.next();    
  }  
  
  public int size()
  { return size;  }
 
  public ListIterator listIterator() { return new IteratorR(0);  }
  public ListIterator listIterator(int index){return new IteratorR(index);}
  

  // Inner Classes

  private static class NodeR<E> {
    private E data;
    private NodeR<E> next = null;
    private NodeR<E> prev = null;

    /** Construct a node with the given data value.
        @param dataItem The data value
     */
    private NodeR(E dataItem) {
      data = dataItem;
    }
  } //end class Node

  /** Inner class to implement the ListIterator interface. */
  private class IteratorR implements ListIterator<E>  {

    private NodeR<E> nextItem;     
    private NodeR<E> lastItemReturned;
    private int index = 0;

    /** Construct a IteratorR that will reference the ith item.
        @param i The index of the item to be referenced
     */
    public IteratorR(int i) {
      // Validate i parameter.
      if (i < 0 || i > size) {
        throw new IndexOutOfBoundsException(
            "Invalid index " + i);
      }
      lastItemReturned = null; // No item returned yet.
      // Special case of last item.
      if (i == size) {
        index = size;
        nextItem = null;
      }
      else { // Start at the beginning
        nextItem = head;
        for (index = 0; index < i; index++) {
          nextItem = nextItem.next;
        }
      }
    } // end constructor
 

    /** Indicate whether movement forward is defined.
        @return true if call to next will not throw an exception
     */
    public boolean hasNext() {  // this is for you to implement
      return false;  // incorrect implementation
    }

    /** Move the iterator forward and return the next item.
        @return The next item in the list
        @throws NoSuchElementException if there is no such object
     */
    public E next() {   // for you to implement
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      
      return head.data;   // incorrect implementation
    }

    /** Add a new item between the item that will be returned
        by next and the item that will be returned by previous.
        If previous is called after add, the element added is
        returned.
        @param obj The item to be inserted
     */
    public void add(E obj) {

      if (head == null) { // Add to an empty list.

      }
      else if (nextItem == head) { // Insert at head.
      
        }
      else if (nextItem == null) { // Insert at tail. 

      }
      else { // Insert into the middle.
  
      }

    } // End of method add.
    
    /** The following methods must be included since we implement the
     * the ListIterator interface, but they do not enter into this
     * exercise, so have been virturally excluded;  they are NOT
     * implemented correctly, just enought to satisfy the compiler
     */
    public E previous()
    {   return lastItemReturned.data;    }  // not impelemted
    public boolean hasPrevious() { return false;  }   // not implemented
    public int nextIndex() {      return index;    }
    public int previousIndex() {      return index - 1;    }
    
    public void set(E o)  { }  // not implemented
    public void remove(){}      // not implemented


  } //end class LListReview
}