// Implements a singly-linked list.

import java.util.Iterator;

public class SinglyLinkedList implements Iterable<Object>
{
  private ListNode head;
  private int nodeCount;

  // Constructor: creates an empty list
  public SinglyLinkedList()
  {
    head = null;
    nodeCount = 0;
  }

  // Constructor: creates a list that contains
  // all elements from the array values, in the same order
  public SinglyLinkedList(Object[] values)
  {
    ListNode tail = null;
    for (Object value : values) // for each value to insert
    {
      ListNode node = new ListNode(value, null);
      if (head == null)
        head = node;
      else
        tail.setNext(node);
      tail = node;    // update tail
    }

    nodeCount = values.length;
  }

  // Returns true if this list is empty; otherwise returns false.
  public boolean isEmpty()
  {
    return head == null;
  }

  // Returns the number of elements in this list.
  public int size()
  {
    return nodeCount;
  }

  // Returns true if this list contains an element equal to obj;
  // otherwise returns false.
  public boolean contains(Object obj)
  {
    if(isEmpty())
      return false;
    for(Object o : this)
      if(o.equals(obj))
        return true;
    return false;
  }

  // Returns the index of the first element in equal to obj;
  // if not found, retunrs -1.
  public int indexOf(Object obj)
  {
    if(isEmpty())
      return -1;
    Integer count = 0;
    for(Object o : this)
    {
      if(o.equals(obj))
        return count;
      count++;
    }
    return -1;
  }

  // Adds obj to this collection.  Returns true if successful;
  // otherwise returns false.
  public boolean add(Object obj)
  {
    ListNode node = new ListNode(obj, null);
    ListNode x = head;
    
    while(x.getNext() != null)
      x = x.getNext();
    x.setNext(node);
    node.setNext(null);
    nodeCount++;
    return true;
  }

  // Removes the first element that is equal to obj, if any.
  // Returns true if successful; otherwise returns false.
  public boolean remove(Object obj)
  {
    throw new UnsupportedOperationException( );
  }

  // Returns the i-th element.               
  public Object get(int i)
  {
    throw new UnsupportedOperationException( );
  }

  // Replaces the i-th element with obj and returns the old value.
  public Object set(int i, Object obj)
  {
    throw new UnsupportedOperationException( );
  }

  // Inserts obj to become the i-th element. Increments the size
  // of the list by one.
  public void add(int i, Object obj)
  {
    if(isEmpty() && i == 0)
    {
      nodeCount++;
      head.setNext(new ListNode(obj, null));
    }
    ListNode node = new ListNode(obj, null);
    ListNode x = getHead();
    ListNode y = head.getNext();
    Integer z = 0;
    while(i <= nodeCount && z != i - 1)
    {
      x = x.getNext();
      i++;
    }
    x.setNext(node);
    node.setNext(null);
  }

  // Removes the i-th element and returns its value.
  // Decrements the size of the list by one.
  public Object remove(int i)
  {
    throw new UnsupportedOperationException( );
  }

  // Returns a string representation of this list.
  public String toString()
  {
    String str;
    str = "[";
    ListNode o = getHead();    
    for(int i = 0; i <= nodeCount; i++)
    {
      o = o.getNext();
      str += " "+o;
    }
    return str;
  }

  // Returns an iterator for this collection.
  public Iterator<Object> iterator()
  {
    return new SinglyLinkedListIterator(head);
  }
  private ListNode getHead()
  {
    return head;
  }
}