public class OrderedList {

	private class Node {
		int value;
		Node next;

		Node(int theValue, Node theNext) {
			value = theValue;
			next = theNext;
		}
	}

	Node head = null;

	OrderedList() {
		head = new Node(0, null); // empty dummy node
	}

	boolean isEmpty() {
		return (head.next == null);
	}

	void insertIterative(int value) {
		Node cur, prev = head;
		cur = head.next;
		while (cur != null && value > cur.value) {
			prev = cur;
			cur = cur.next;
		}
		// now value <= cur.value BUT value > prev.value
		prev.next = new Node(value, cur);
	}

	void insertRecursive(int value) {
		head.next = insertHelper(head.next, value);
	}

	// returns a new linked list with the value inserted into the correct location
	private Node insertHelper(Node list, int value) {
		if (list == null)
			return new Node(value, null);
		else if (value < list.value)
			return new Node(value, list);
		else {
			list.next = insertHelper(list.next, value);
			return list;
		}
	}

	public String toStringIterative() {
		String ret = "";
		for (Node p = head.next; p != null; p = p.next)
			ret += p.value + " ";
		return ret;
	}

	public String toStringRecursive() {
		return toStringHelper(head.next);
	}

	private String toStringHelper(Node p) {
		if (p == null)
			return "";
		else
			return p.value + " " + toStringHelper(p.next);
	}

	// returns true if remove is successful, false if value not found
	boolean removeIterative(int value) {
		Node cur, prev = head;
		cur = head.next;
		while (cur != null && value != cur.value) {
			prev = cur;
			cur = cur.next;
		}
		if (cur != null) {
			// now value == cur.value, so remove cur from the list
			prev.next = cur.next;
			return true;
		} else
			return false;
	}

	private boolean removeSucceeded;

	public boolean removeRecursive(int value) {
		removeHelper(head.next, value);
		return removeSucceeded;
	}

	// returns a new linked list with the value inserted into the correct location
	private Node removeHelper(Node list, int value) {
		if (list == null) {
			removeSucceeded = false;
			return null;
		} else if (value == list.value) {
			removeSucceeded = true;
			return list.next;
		} else {
			list.next = removeHelper(list.next, value);
			return list;
		}
	}

	private Node doNothing(Node list) {
		if (list == null)
			return null;
		else {
			list.next = doNothing(list.next);
			return list;
		}
	}
}