import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Iterator;

public class LinkedList1<E> implements Iterable<E>{

   private listNode firstNode;
   private int size;

   public LinkedList1() {
      firstNode = new listNode(null);
      size = 0;
   }

   public Iterator<E> iterator() {
      return new ListIterator();
   }

   private class ListIterator implements Iterator<E> {

      private listNode curNode;

      public ListIterator() {
         curNode = firstNode;
      }

      public boolean hasNext() {
         return curNode.nextNode != null;
      }

      public E next() {
         if (!hasNext()) {
            throw new NoSuchElementException();
         }
         curNode = curNode.nextNode;
         return curNode.value;
      }
   }

   public int getSize() {
      return size;
   }

   public boolean isEmpty() {
      if (size == 0) {
         return true;
      }
      listNode curNode = firstNode;
      while(curNode.nextNode != null) {
         if (!curNode.value.equals(null)) {
            return false;
         }
         curNode = curNode.nextNode;
      }
      return true;
   }

   public void clear() {
      size = 0;
      firstNode = null;
   }

   public E get(int index) {
      listNode returnNode = firstNode;
      for(int i = 0; i < index; i++) {
         returnNode = returnNode.nextNode;
      }
      return returnNode.value;
   }

   public E set(int index, E e) {
      E toReturn = remove(index);
      add(index, e);
      return toReturn;
   }

   public int indexOf(E e) {
      int count = 0;
      listNode curNode = firstNode;
      for(int i = 0; i < size; i++) {
         if (curNode.value.equals(e)) {
            return count;
         }
         curNode = curNode.nextNode;
         count++;
      }
      return -1;
   }

   public boolean contains(E e) {
      listNode curNode = firstNode;
      for(int i = 0; i < size; i++) {
         if (curNode.value.equals(e)) {
            return true;
         }
         curNode = curNode.nextNode;
      }
      return false;
   }

   public int lastIndexOf(E e) {
      int count = 0;
      int lastFound = -1;
      listNode curNode = firstNode;
      for(int i = 0; i < size; i++) {
         if (curNode.value.equals(e)) {
            lastFound = count;
         }
         curNode = curNode.nextNode;
         count++;
      }
      return lastFound;
   }

   public E getFirst() {
      return firstNode.value;
   }

   public E getLast() {
      listNode curNode = firstNode;
      while(curNode.nextNode != null) {
         curNode = curNode.nextNode;
      }
      return curNode.value;
   }

   public void addFirst(E e) {
      add(0, e);
   }

   public void addLast(E e) {
      add(e);
   }

   public boolean add(E e) {
      listNode newNode = new listNode(e);

        listNode curNode = firstNode;

        // while we're not at end of list, iterate over list
        while(curNode.nextNode != null) {
            curNode = curNode.nextNode;
        }

        // curNode = last node in list
        curNode.nextNode = newNode;

        size++;

        return true;
   }

   public void add(int index, E e) {
      if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        listNode newNode = new listNode(e);

        listNode curNode = firstNode;

        for(int i = 0; i < index; i++) {
            curNode = curNode.nextNode;
        }

        // curNode is at index-1
        newNode.nextNode = curNode.nextNode;
        curNode.nextNode = newNode;

        size++;
   }

   public E remove() {
      //if list is empty
      if (size == 0) {
         throw new NoSuchElementException();
      }
      return remove(0);
   }

   public E remove(int index) {
      //error checking
      if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        listNode curNode = firstNode;

        for(int i = 0; i < index; i++) {
            curNode = curNode.nextNode;
        }

        // curNode is at index-1
        E toReturn = curNode.nextNode.value;
        curNode.nextNode = curNode.nextNode.nextNode;

        size--;

        return toReturn;
   }

   public boolean remove(E e) {
      if(size == 0) {
         return false;
      //} else if( firstNode.value.equals(e) ) {
      //   firstNode = firstNode.nextNode;
      //   size--;
      //   return true;
      } else {
         listNode curNode = firstNode;
         for (int i = 0; i < size-1; i++) {
            curNode = curNode.nextNode;
            if (curNode.value.equals(e)) {
               curNode.nextNode = curNode.nextNode.nextNode;
               size--;
               return true;
            }
         }
         return false;
      }
   }

   //test function to print out list
   public void printLinkedList() {
      listNode curNode = firstNode;
      System.out.print("Printing list: Size: " + size + ", ");
      for(int i = 0; i < size; i++) {
         System.out.print(curNode.value + " >> ");
         curNode = curNode.nextNode;
      }
      System.out.println("");
   }

   private class listNode {
      private E value;
      private listNode nextNode;

      public listNode(E e) {
         value = e;
         nextNode = null;
      }

      public void setNext(listNode next) {
         nextNode = next;
      }

      public listNode getNext() {
         return nextNode;
      }

      public E getValue() {
         return value;
      }
   }
}