// 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);
    if(head == null)
      head = node;
    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)
  {
    if(isEmpty())
      return false;
    ListNode x = getHead();
    ListNode before = head.getNext();
    if(head.getValue().equals(obj))
    {
      head = head.getNext();
      return true;
    }
    while(before != null)
    {
      if(before.getValue().equals(obj))
      {
        nodeCount--;
        return true;
      }
      x = before;
      before = x.getNext();
    }
    return false;
  }

  // Returns the i-th element.               
  public Object get(int i)
  {
    if(i < 0 || i >= nodeCount)
      throw new IndexOutOfBoundsException();
    ListNode o = getHead();    
    for(int j = 0; j < i; j++)
    {
      o = o.getNext();
    }
    return o.getValue();
  }

  // Replaces the i-th element with obj and returns the old value.
  public Object set(int i, Object obj)
  {
    if(i < 0 || i >= nodeCount)
      throw new IndexOutOfBoundsException();
    ListNode node = getHead();
    Object temp = null;
    for(int j = 0; j < i; j++)
    {
      node = node.getNext();
    }
    temp = node.getValue();
    node.setValue(obj);
    return temp;
  }

  // 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)
  {
    if(i < 0 || i >= nodeCount)
      throw new IndexOutOfBoundsException();
    ListNode node = getHead(); 
    ListNode prev = null;
    Object temp = null;
    for(int j = 0; j <= i; j++)
    {
      prev = node;
      node.getNext();
    }
    temp = node.getValue();
    if(prev == null)
      head = node.getNext();
    prev.setNext(node.getNext());
    nodeCount--;
    return temp;
  }

  // Returns a string representation of this list.
  public String toString()
  {
    String str;
    str = "[";
    ListNode node = getHead();    
    for(Object o : this)
      str += " "+ o;
    return str + " ]";
  }

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