public class AutoSortListTest {
	public static void main (String[] args) {
		AutoSortList a = new AutoSortList();

		java.util.Random rnd = new java.util.Random();
		for (int i = 0; i < 100; ++i) {
			a.insert (rnd.nextInt() % 1000);
		}
		
		AutoSortListNode n = a.getHead();
		while (n != null) {
			System.out.println (n.data);
			n = n.next;
		}
	}
}

class AutoSortList {
	AutoSortListNode head, tail;

	public AutoSortListNode getHead() {  return head;  }
	public AutoSortListNode getTail() {  return tail;  }

	void init () {
		head = new AutoSortListNode();
		tail = head;
	}

	public void insert (int data) {
		System.out.println ("Inserting " + data);
		// Empty list
		if (head == null) {
			init();
			head.data = data;
			return;
		} else if (data < head.data) {
			AutoSortListNode tmp = new AutoSortListNode();
			tmp.data = data;
			tmp.next = head;
			head.prev = tmp;
			head = tmp;
			return;
		} else if (head.next != null) {
			// Seek to the correct node
			AutoSortListNode n = head.next;
			while (n != null) {
				if (data > n.prev.data && data <= n.data) {
					// Insert here
					AutoSortListNode tmp = new AutoSortListNode();
					tmp.data = data;
					tmp.prev = n.prev;
					tmp.next = n;
					n.prev.next = tmp;
					if (n.next != null) {
						n.next.prev = tmp;
					}
					return;
				}
				n = n.next;
			}
		}

		// Last node
		tail.next = new AutoSortListNode();
		tail.next.prev = tail;
		tail = tail.next;
		tail.data = data;
	}
}

class AutoSortListNode {
	public AutoSortListNode prev, next;
	public int data;
}