import java.util.AbstractList;

public class MyLinkedList<E extends Comparable<E>> extends AbstractList<E>
{
  private Node first, last;
  private int size;

  private void printInReverse(Node ref)
  {
    if (ref != null)
    {
      printInReverse(ref.next);
      System.out.println(ref.value);
    }
  }

  void printInReverse()
  {
    printInReverse(first);
  }

  public E remove(int index)
  {
    if (index < 0 || index >= size())
    {
      throw new IndexOutOfBoundsException("Invalid index: " + index);
    }

    if (index == 0)
    {
      first = first.next; //garbage collect the old "first"
      if (first == null)
      {
        last = null; //now list is empty
      }
    } else {
      Node ref = first;
      //travel to the node right before "index"
      for (int x = 0; x < index - 1; x++)
      {
        ref = ref.next;
      }
      ref.next = ref.next.next;
      if (ref.next == null)
      {
        last = ref;
      }
    }
    size--;
    return null;
  }

  //O(N)
  public void add(int index, String value)
  {
    if (index < 0 || index > size())
    {
      throw new IndexOutOfBoundsException("Invalid index: " + index);
    }
    if (index == 0)
    {
      first = new Node(value, first);
    } else {
      Node ref = first;
      //travel to the node right before "index"
      for (int x = 0; x < index - 1; x++)
      {
        ref = ref.next;
      }
      //make the connection
      ref.next = new Node(value, ref.next);
    }
    if (last.next != null)
    {
      last = last.next;
    }
    size++;
  }

  public String toString()
  {
    //way to concatenate many Strings together
    StringBuilder result = new StringBuilder();
    Node ref = first;
    while (ref != null)
    {
      result.append(ref.value + "\n");
      ref = ref.next;
    }
    return result.toString();
  }

  @SuppressWarnings("unchecked")
  public E get (int index)
  {
    if (index < 0 || index >= size())
    {
      throw new IndexOutOfBoundsException("Invalid index: " + index);
    }

    //starting at very first node
    Node ref = first;
    for (int x = 0; x < index; x++)
    {
      // x does not = subscript
      ref = ref.next; //hop to next node
    }
    return (E) ref.value;
  }

  void add(String value)
  {
    //check if it's empty 1st
    if (isEmpty())
    {
      first = last = new Node(value);
    }
    else
    {
      last.next = new Node(value);
      last = last.next; //leap frog!
    }
    size++;
  }

  //method to check if linked list is empty - first node is empty
  public boolean isEmpty()
  {
    return first == null;
  }

  public int size()
  {
    return size; //O(1) - constant time
  }
}