public class HeadList {

    Entry head;
    Entry last; // -> Beschreibung siehe Methode add(Entry)

    /**
     * constructor empty HeadList
     */
    public HeadList() {
        head = null;
    }

    /**
     * Appends a new element with value info to the end of this list
     * @param info value of the new element
     */
    public void add(int info) {
        // TODO 01
        add(new Entry(head, null, info));
    }
    /**
     * Fügt einen Eintrag ans Ende der Liste (optional, aber m. M. n. schöner).
     */
    private void add (Entry newEntry) {
        // Man kann sich das letzte Element in einer Membervariable speichern,
        // wie ich es hier tue. Tut man das nicht, muss man das letzte Element
        // jedesmal erst finden, da man das neue Element sonst nicht anhängen kann. 
        // Deutlich effizienter ist das Verwenden einer Membervariable!
        // Aufpassen muss man auf den Sonderfall, dass head noch null ist (denn
        // dann ist der Zugriff head.next nicht möglich) -> head setzen.
        
        if (head == null) {
            head = last = newEntry;
            head.first = newEntry;
        } else {
            /* Mit Membervariable */
            // Element hinten anfügen: Wir setzen den nächsten des aktuell letzten
            // Elements auf das neue Element. Das nun letzte Element soll unser
            // neues element sein, daher die Zuweisung an die Memebervariable last.
            last = last.next = newEntry;
            
            /* ALTERNATIV (ohne Membervariable last) */
            Entry last = head; // wir nehmen erstmal an, das erste wäre das letzte
            while (last.next != null) 
                last = last.next; // -> nimm das nächste Element
            last.next = newEntry; // Element hinten anfügen
            
        }
    }

    /**
     * Removes and returns the element at position index from this list.
     * @param index position of the element that is removed
     * @return value of the removed element
     */
    public int remove(int index) {
        // TODO 03
        
        if (index < 0)  // benötigt? derzeit unklar
            return Integer.MIN_VALUE;

        // Da wir Zeiger umsetzen müssen, speichern wir neben dem gesuchten
        // Element auch eine Referenz auf dessen Vorgänger (in prev)
        
        Entry prev = null, current = head; 
        while (current != null && index-- > 0) {
            prev = current;
            current = current.next;
        }
        
        if (current != null && index == -1) { // vollständig heruntergezählt und vorhanden
            if (prev == null) { // -> head soll entfernt werden
                head = current.next;
                setHead(head); // neuen Head setzen
            } else { // -> "normales" Entfernen
                prev.next = current.next;
            }
            return current.elem;
        }
        
        // nicht vollständig heruntergezählt oder head == null -> nicht vorhanden
        return Integer.MIN_VALUE;
    }

    /**
     * sets the head of each list element to newHead
     * @param newHead reference to the new head
     */
    private void setHead(Entry newHead) {
        // TODO 02

        Entry current = head; // wir beginnen mit dem ersten Element
        while (current != null) {
            current.first = newHead; // Head neu setzen
            current = current.next; // zum nächsten Element gehen
        }
    }

    /**
     * reverse the list
     * example: [1,2,3,4,5] --> [5,4,3,2,1], [] --> [], [1] --> [1]
     */
    public void reverse() {
        Entry prev = null, current = head, next;
        
        while (current != null) {
            next = current.next; // speichere den Nachfolger (soll nachher Vorgänger sein)
            current.next = prev; // setze den Vorgänger (zuvor behandelt) als Nachfolger des aktuellen
            prev = current; // setze den Vorgänger (des als nächstes zu behandelnden)
            current = next; // setze den als nächstes zu behandelnden
        }
        
        head = prev;
        setHead(head);
    }
    

    @Override
    public String toString() {
        String out = "[";
        if (head != null) {
            out += head.elem;
            Entry tmp = head.next;
            while (tmp != null) {
                out = out + "," + tmp.elem;
                tmp = tmp.next;
            }
        }
        out += "]";
        return out;
    }

    public static void main(String[] args) {
        HeadList l = new HeadList();
        System.out.println("empty list: " + l);
        // Test implementation

    }

    class Entry {

        Entry first;
        Entry next;
        int elem;

        public Entry(Entry first, Entry next, int elem) {
            this.first = first;
            this.next = next;
            this.elem = elem;
        }

    }

}