import java.util.NoSuchElementException;

public class LList
{
    private Node head;

    public LList()
    {
		head = null;
    }

    public boolean isEmpty()
    {
		return head == null;
    }

    public void addAtFront(Comparable c)
    {
		head = new Node(c,head);
    }

    public void addAtEnd(Comparable c)
    {
		if (head == null)
	    	head = new Node(c,head);
		else
		{
            Node curr = head;
            while (curr.getNext() != null)
            	curr = curr.getNext();
	    	curr.setNext(new Node(c));
		}
    }

    public void addInOrder(Comparable c)
    {
		head = orderedHelper(head,c);
    }

    private Node orderedHelper(Node h, Comparable c)
    {
		if (h == null)
	    	return new Node(c);

		if (c.compareTo(h.getData()) < 0)
	    	return new Node(c,h);

		h.setNext(orderedHelper(h.getNext(),c));
		return h;
    }

    public void addList(LList l)
    {
		Node curr = l.head;
		while (curr != null)
		{
	    	addAtFront(curr.getData());
	    	curr = curr.getNext();
		}
    }

    public boolean remove(Comparable c)
    {
		try
		{
	    	head = removeHelper(head,c);
	    	return true;
		}
		catch (NoSuchElementException n)
		{
	    	return false;
		}
    }

    private Node removeHelper(Node h, Comparable c)
    {
		if (h == null)
	    	throw new NoSuchElementException();

		if (h.getData().equals(c))
	    	return h.getNext();

		h.setNext(removeHelper(h.getNext(),c));
		return h;
    }

    public String toString()
    {
		String result = "";

		for (Node curr = head; curr != null; curr = curr.getNext())
		{
	    	result += curr.getData();
	    	if (curr.getNext() != null)
				result += " --> ";
		}
		//result += "null";

		return result;
	}

	private class Node  // inner class to implement linked list
	{
		private Comparable data;
		private Node next;

		public Node(Comparable c, Node n)
		{
			data = c;
			next = n;
		}

		public Node(Comparable c)
		{
			this(c,null);
		}

		public Comparable getData()
		{
			return data;
		}

		public Node getNext()
		{
			return next;
		}

		public void setNext(Node n)
		{
			next = n;
		}
	}

	public static void main(String[] args)
	{
		LList list = new LList();
		list.addInOrder(new Integer(21));
		list.addInOrder(new Integer(398));
		list.addInOrder(new Integer(42));
		System.out.println(list);
		System.out.println("\nTesting deletes...");
		list.remove(new Integer(42));
		System.out.println(list);
		list.remove(new Integer(398));
		System.out.println(list);
		list.remove(new Integer(21));
		System.out.println(list);
	}
}
