/**
 * AlgoDat SS00 Aufgabe 50
 * Selbstanordnende Liste
 * Gefundenes Element wird an den Anfang verschoben
 *
 * @author Laura Marnitz, Christian Semrau, 16.05.2000
 * <a href="mailto:gemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */
class MoveToFirstList {

    private SingleListElement head = null;
    private int size = 0;

    // kein Konstruktor --> parameterloser Standardkonstruktor wird
    // automatisch erzeugt

    public void insert(Object x){
        SingleListElement y = new SingleListElement(x, head);
        head = y;
        size++;
    }

    public Object findElement(Object x){
        SingleListElement prev, h = head;
        if (h == null)  // leere Liste
            return null;

        // die Liste ist nicht leer
        if (h.getElement().equals(x))  // an erster Stelle gefunden
           return h.getElement();

        prev = head;
        h = h.getNext();
        // das erste Element war's nicht, h zeigt auf das zweite

        while (h != null){  // solange h auf ein Element zeigt
            if (h.getElement().equals(x)){
                prev.setNext(h.getNext());  // h an die erste Stelle verschieben
                h.setNext(head);
                head = h;

                return h.getElement();
            }
            prev = h;
            h = h.getNext();  // die Liste durchwandern
        }
        return null; //nicht gefunden
    }
  
    public String toString(){
        String s = "";
        SingleListElement h = head;
        s += "size: "+size+"\n";
        while (h != null){
            s += h.getElement()+"\n";
            h = h.getNext();
        }
        return s;
    }    
}

/**
 * AlgoDat SS00 Aufgabe 50
 * Selbstanordnende Liste
 * Testklasse
 */
public class ChS_Aufg50a{
    public static void main(String args[]) {
        MoveToFirstList list=new MoveToFirstList();
        list.insert(new Integer(4));
        list.insert(new Integer(3));
        list.insert(new Integer(2));
        list.insert(new Integer(1));
        list.findElement(new Integer(4));
        list.findElement(new Integer(2));
        System.out.println(list);
    }
}