// MUSTERLÖSUNG ohne Javadoc, Stand 24.6.04

import java.util.ListIterator;
import java.util.NoSuchElementException;

public class LinkedList implements InfoIIListe {

    Link first;
    Link last;

    private void leeren() {
	first = null;
	last = null;
    }

    public LinkedList() {
	leeren();
    }

    public ListIterator listIterator() {
	return new LinkedListIterator(this);
    }

    public Object getFirst() {
	if (first==null) throw new NoSuchElementException();
	else return first.data;
    }

    public Object getLast() {
	if (last==null) throw new NoSuchElementException();
	else return last.data;
    }

    public void addFirst(Object obj) {
	Link newLink = new Link();
	newLink.data = obj;
	newLink.next = first;
	newLink.prev = null;
	if (first == null) {
	    first = newLink;
	    last = newLink;
	} else {
	    first.prev = newLink;
	    first = newLink;
	}
    }

    public void addLast(Object obj) {
	// nun implementiert, einfach dual zu addFirst
	Link newLink = new Link();
	newLink.data = obj;
	newLink.next = null;
	newLink.prev = last;
	if (first == null) {
	    first = newLink;
	    last = newLink;
	} else {
	    last.next = newLink;
	    last = newLink;
	}
    }

    public Object removeFirst() {
	// nun implementiert
	if (first==null) throw new NoSuchElementException();
	Object obj = first.data;
	if (first == last) leeren();
	else {
	    first = first.next;
	    first.prev = null;
	}
	return obj;
    }

    public Object removeLast() {
	// nun implementiert, einfach dual zu removeFirst
	if (last==null) throw new NoSuchElementException();
	Object obj = last.data;
	if (first == last) leeren();
	else {
	    last = last.prev;
	    last.next = null;
	}
	return obj;
    }
}

 
class Link {

    public Object data;
    public Link next;
    public Link prev;
}


class LinkedListIterator implements ListIterator {
    private Link forward;
    private Link backward;
    private LinkedList list;
    private Link lastReturned;
    private int cursor;  // neue Instanzvariable

    public LinkedListIterator(LinkedList l) {
	forward = l.first;
	backward = null;
	list = l;
	lastReturned = null;
	cursor = 0; // neu
    }
    
    public void add(Object obj) {
	lastReturned = null;
	if (backward == null) {
	    list.addFirst(obj);
	    backward = list.first;
	} else if (!hasNext()) {
	    list.addLast(obj);
	    backward = backward.next;
	} else {
	    Link newLink = new Link();
	    newLink.data = obj;
	    newLink.next = forward;
	    newLink.prev = backward;
	    backward.next = newLink;
	    forward.prev = newLink;
	    backward = newLink;
	}
	cursor++; // neu
    }
    
    public boolean hasNext() {
	return forward != null;
    }
    
    public boolean hasPrevious() {
	return backward!= null;
    }
    
    public Object next() {
	lastReturned = forward;
	backward = forward;
	forward = forward.next;
	cursor++; // neu
	return backward.data;
    }
    
    public int nextIndex() {
	return cursor; // nun implementiert
    }

    public Object previous() {
	// nun implementiert, einfach dual zu next
	lastReturned = backward;
	forward = backward;
	backward = backward.prev;
	cursor--;
	return forward.data;
    }
    
    public int previousIndex() {
	return cursor-1; // nun implementiert - nicht dual!
    }

    public void remove() {
	// nun implementiert - dies war der schwierigste Teil
	if (lastReturned == null)
	    throw new IllegalStateException();
	else {
	    if (lastReturned.prev == null)
		list.removeFirst();
	    else if (lastReturned.next == null)
		list.removeLast();
	    else {
		lastReturned.prev.next = lastReturned.next;
		lastReturned.next.prev = lastReturned.prev;
	    }
	    if (lastReturned == backward)
		backward = lastReturned.prev;
	    else
		forward = lastReturned.next;
	    lastReturned = null;
	}
	cursor--;
    }

    public void set(Object obj) {
	// nun implementiert
	lastReturned.data = obj;
    }
}