ADT/List.java

public class List<T>
{
    /**
     * erster Eintrag der Liste
     */
    public Node<T> first;
    
    /**
     * Konstruktor
     */
    public List() {}
    
    /**
     * Überprüft, ob die Liste leer ist
     * 
     * @return true, wenn keine Elemente in der Liste
     */
    public boolean isEmpty() {
        return first == null;
    }
    
    /**
     * Berechnet die Größe der Liste
     * 
     * @return Anzahl der Elemente in der Liste
     */
    public int size() {
        Node<T> current = first;
        int laenge = 0;
        
        while (current != null) {
            current = current.next;
            laenge++;
        }
        
        return laenge;
    }
    
    /**
     * Gibt das Element an der n-ten Stelle zurück, oder null
     * falls die Liste kürzer ist
     */
    public T get(int n) {
        Node<T> current = first;
        
        if (n >= size()) return null;
        
        for (int i=0; i<n; i++) {
            current = current.next;
        }
        
        return current.wert;
    }
    
    /**
     * Fügt ein neues Element am Ende der Liste ein
     */
    public void add(T neu) {
        Node n = new Node<T>(neu); // Neue Node mit Zahl "neu" anlegen
        
        // Überprüfe, ob Liste leer
        if (first == null) {
            // setze neue Node als ersten Eintrag
            first = n;
        } else {
            Node<T> current = first;
            
            // gehe zum letzten Eintrag
            while (current.next != null) {
                current = current.next;
            }
            
            // current ist jetzt der letzte Eintrag
            // setze neue Node als Nachfolger von bisher letzem Eintrag
            current.setNext(n);
        }
    }
    
    /**
     * Fügt ein neues Element an der Stelle n in die Liste ein
     * oder am Ende, falls die Liste kürzer ist.
     */
    public void add(int n, T wert) {
        // Neue Node anlegen
        Node<T> neu = new Node<T>(wert);
        
        if (n == 0) {
            // Setze Nachfolger auf bisherigen Start
            neu.setNext(first);
            // Setze neuen Start auf neues Element
            first = neu;
        } else {
            Node<T> current = first;
            // gehe an den Vorgänger
            for (int  i=0; i<n-1; i++) {
                if (current.next != null) {
                    current = current.next;
                }
            }
            
            // ändere neu.next auf current.next
            neu.setNext(current.next);
            
            // ändere current.next auf neu
            current.setNext(neu);
        }
    }
    
    /**
     * Überprüft, ob die Liste einen konkreten Wert enthält
     */
    public boolean contains(T wert) {
        Node<T> current = first;
        
        while (current != null) {
            if (current.wert == wert) return true;
            
            current = current.next;
        }
        
        return false;
    }
    
    /**
     * Löscht das Element an der Stelle n und gibt
     * dessen Wert zurück
     */
    public T remove(int n) {
        if (n >= size()) return null;
        
        if (n == 0) {
            T wert = first.wert;
            
            first = first.next;
            
            return wert;
        } else {
            Node<T> current = first;
            
            // gehe an den Vorgänger des zu löschenden Eintrags
            for (int  i=0; i<n-1; i++) {
                current = current.next;
            }
            
            T wert = current.next.wert;
            
            // Setze Übernächsten Eintrag als Nachfolger
            current.next = current.next.next;
            
            return wert;
        }
    }
}