class Main {
    public static void main(String[] args) {
	int i;
	List integers = ListNew();
	List l;

	for(i = 0; i < 20; ++i)
	    integers = ListPut(integers,i);
	ListPrint(integers);
	ListPrint(ListIth(integers,5));
	ListPrint(ListIth(integers,50));
	
	System.out.println("-----------------");

	l = ListRemove(integers,5,10);
	ListPrint(integers);
	ListPrint(l);
	
	System.out.println("-----------------");

	ListInsertBefore(l,ListIth(integers,10));
	ListPrint(integers);
	ListPrint(l);
    }

    public static List ListNew() {
	return null;
    }

    public static boolean ListIsEmpty(List that) {
	return that == null;
    }

    public static List ListPut(List that, int elem) {
	List res = new List();
	
	res.value     = elem;
	res.previous  = null;
	res.next      = that;
	if(!ListIsEmpty(that))
	    that.previous = res;

	return res;
    }
    
    public static void ListPrint(List that) {
	List iter;

	if(ListIsEmpty(that))
	    System.out.println("[]");
	else {
	    if(that.previous == null)
		System.out.print("[");
	    else
		System.out.print("...");
	    System.out.print(that.value);
	    for(iter = that.next; iter != null; iter = iter.next) {
		System.out.print(", ");
		System.out.print(iter.value);
	    }
	    System.out.println("]");
	}
    }

    public static List ListIth(List that, int i) {
	if(ListIsEmpty(that) || ( i <= 1) )
	    return that;
	else
	    return ListIth(that.next, i-1);
    }

    // "from" starts from index 1.
    public static List ListRemove(List that, int from, int to) {
	List first,last,last_next;


	first = ListIth(that,from);
	if(ListIsEmpty(first)) 
	    return ListNew();

	last = ListIth(that,to);
	if(!ListIsEmpty(last))
	    last_next = last.next;
	else
	    last_next = ListNew();

	if(!ListIsEmpty(first.previous))
	    first.previous.next = last_next;

	if(!ListIsEmpty(last_next))
	    last_next.previous = first.previous;

	first.previous = ListNew();

	if(!ListIsEmpty(last))
	    last.next = ListNew();
	
	return first;
    }

    public static void ListInsertBefore(List that, List iter) {
	List last,iter_previous;

	if(!ListIsEmpty(that) && !ListIsEmpty(iter) ) {

	    iter_previous = iter.previous;
	    for(last = that; !ListIsEmpty(last.next); last = last.next);

	    last.next = iter;
	    if(!ListIsEmpty(iter_previous))
		iter_previous.next = that;
	    iter.previous = last;

	    if(!ListIsEmpty(that.previous))
		that.previous.next = ListNew();
	    that.previous = iter_previous;
	}
    }
}