/** Implementation of a generic linked list.
    @author Jed Yang, 2018-02-02
*/
public class CarlLinkedList<E> implements List<E>
{
   private static class Node<E>
   {
      private E data;         // data of the item
      private Node<E> next;   // link to next node

      public Node(E data)
      {
         this(data, null);
      }

      public Node(E data, Node<E> nextNode)
      {
         this.data = data;
         this.next = nextNode;
      }
   }

   // instance variables, private
   private Node<E> head;

   public CarlLinkedList()
   {
      // FIXME: implement!
      head = null;
   }

   /** Live-code. */
   public void add(E item)
   {
      // FIXME: implement!
      if (head == null)
      {
         head = new Node<E>(item);
      }
      else
      {
         Node<E> cur = head;
         while (cur.next != null)
         {
            cur = cur.next;
         }
         cur.next = new Node<E>(item);
      }
   }











   /** Worksheet. */
   public void add(int index, E item)
   {
      if (index < 0)
      {
         throw new IndexOutOfBoundsException("index too small");
      }
      else if (index == 0)
      {
         head = new Node<E>(item, head);
      }
      else
      {
         Node<E> prev = head;
         for (int i = 1; i < index; i++)
         {
            if (prev.next == null)
            {
               throw new IndexOutOfBoundsException("index too large");
            }
            prev = prev.next;
         }
         prev.next = new Node<E>(item, prev.next);
      }
   }

   public E get(int index)
   {
      return null;
   }

   public int size()
   {
      return -1;
   }

   /** Returns a comma-separated list of the elements.
       @return string representation
   */
   public String toString()
   {
      return "[" + toStringRecursive(head) + "]";
   }

   /** Constructs string representation starting at node. */
   private String toStringRecursive(Node<E> node)
   {
      if (node == null) // 0 elements
      {
         return "";
      }
      else if (node.next == null) // 1 element
      {
         return "" + node.data;
      }
      else
      {
         return node.data + ", " + toStringRecursive(node.next);
//         return "" + toStringRecursive(node.next) + ", " + node.data;  // in reverse!
      }
   }

   /** Iterative version of toString; using StringBuilder for efficiency. */
   public String toStringIterative()
   {
      StringBuilder str = new StringBuilder("[");
      Node<E> cur = head;
      while (cur != null)
      {
         str.append(cur.data);
         if (cur.next != null)
            str.append(", ");
         cur = cur.next;
      }
      str.append("]");
      return str.toString();
   }

   /** Demo and test of List methods. */
   public static void main(String[] args)
   {
      List<Integer> list1 = new CarlLinkedList<Integer>();
      for (int i = 0; i < 4; i++)
      {
         list1.add(i);
      }
      System.out.println("list1 should be [0, 1, 2, 3]; actually: " + list1);
      System.out.println("length should be 4; actually: " + list1.size());

      System.out.println("===============================================");

      List<String> list2 = new CarlLinkedList<String>();
      list2.add(0, "a");
      list2.add(1, "c");
      list2.add(1, "b");
      list2.add(3, "d");
      System.out.println("list2 should be [a, b, c, d]; actually: " + list2);
      System.out.println("length should be 4; actually: " + list2.size());
   }
}