public class LinkedSimpleList implements SimpleList
{
	private ListNode head;
	private ListNode tail;

	/**
	 * Inserts an object at the end of the list
	 * @param o the element to be inserted into the list
	 */
	public void add(Object o)
	{
		if (head == null)
			head = tail = new ListNode(o,null);
		else
		{
			tail.setNext(new ListNode(o,null));
			tail = tail.getNext();
		}
	}
	
	/**
	 * Removes the first element of the list that is equal to o
	 * @param o the object to remove
	 */
	public void remove(Object o)
	{
		if (head != null)
		{
			if (head.getValue().equals(o))
				head = head.getNext();
			else
				for (ListNode curr = head; curr.getNext() != null; curr = curr.getNext())
					if (curr.getNext().getValue().equals(o))
					{
						if (curr.getNext() == tail)
							tail = curr;
						curr.setNext(curr.getNext().getNext());
						return;
					}
		}
	}
	
	/**
	 * Determine whether the list is empty.
	 * @return true if the list is empty
	 */
	public boolean isEmpty()
	{
		return head == null;
	}
	
	public String toString()
	{
		String result = "[";
		
		for (ListNode temp = head; temp != null; temp = temp.getNext())
		{
			result += temp.getValue();
			if (temp.getNext() != null)
				result += ",";
		}
		
		return result += "]";
	}			
	
	/**
	 * Obtain all of the elements in the list, as an Iterator
	 * @return an iterator over all of the elements in the list
	 */
    public java.util.Iterator iterator()
	{
		return new Elements();
	}
	
	// inner class to implement iterator over list
	class Elements implements java.util.Iterator
	{
		private ListNode curr = head;
		
		public boolean hasNext()
		{
			return curr != null;
		}

		// you want this to run in constant time
		public Object next()
		{
			Object result = null;
			
			if (hasNext())
			{
				result = curr.getValue();
				curr = curr.getNext();
				return result;
			}
			else
				throw new java.util.NoSuchElementException();
		}
		
		public void remove()
		{
			throw new UnsupportedOperationException();
		}		
    }
    
    
	public static void main(String[] args)
	{
		SimpleList l = new LinkedSimpleList();
    	
		l.add("mark");
		l.add("judy");
		l.add("don");
		System.out.println(l);
		l.remove("don");
		System.out.println(l);
		l.add("gozer");
		System.out.println(l);
		l.remove("mark");
		System.out.println(l);
		l.remove("judy");
		System.out.println(l);
		l.remove("mark");
		System.out.println(l);
		l.remove("gozer");
		System.out.println(l);
		l.remove("gozer");
		System.out.println(l);
		l.add("one last insert");
		System.out.println(l);
	}
}
