Länge der Liste bestimmen/Neues Element Einfügen

Die Länge der Liste kann man bestimmen, indem man sich vom ersten Element zum letzten bewegt und dabei mit einem Zähler die verarbeiteten Elemente mit zählt.

• Implementiere die Methode length
• Teste deine Methode mit unterschiedlich langen Listen. welchen Fall solltest du unbedingt testen?

Lösungsvorschlag

    /**
     * Gibt die Anzahl der Elemente der Liste zurück
     * 
     * @return   Anzahl der Listenelemente
     */
    public int length() {
        int numElements = 0;
 
        Node<T> n = first;
 
        if ( n == null) {
            return numElements;
        }
 
        numElements++;
 
        while ( n.getNext() != null ) {
            n = n.getNext();
            numElements++;
        }
 
        return numElements;
    }

Das Einfügen eines neuen Knotens ist im folgenden Objektdiagramm dargestellt. Man muss beim ändern der Objektreferenzen (nextNode) darauf achten, dass die Reihenfolge stimmt und man die Referenz auf den ursprünglichen Nachfolger des Knotens, hinter dem der neue Knoten eingefügt wird nicht verliert. ¹⁾

Schreibe als Merksatz stichwortartig nieder, was beim Einfügen eines neuen Knotens nach dem n-ten vorhandenen Knoten alles passieren muss. Gibt es Fälle, die gesondert behandelt werden müssen?

Implementiere die Methode insertAt, so dass man damit ein neues Element nach dem n-ten Listenelement einfügen kann. Teste deine Methode, indem du Elemente in eine Liste einfügst und mit dem Objektinspektor überprüfst, dass das neue Element an der richtigen Stelle eingefügt wurde - und dass die Nachfolgenden Knoten noch erreichbar sind.

++ Lösungsvorschlag Kann sicher weiter optimiert werden.

    /**
     * Fügt einen neuen Wert an einer gewünschten Stelle in der Liste ein.
     * @param index Die Stelle, an der der neue Wert stehen soll (0 <= index <= laenge())
     * @param val Der einzufügende Wert
     */
    public void insertAt(int index, T val) {
 
        // Der neue Knoten
        Node<T> new_node = new Node(val, null);
 
        // Wenn der Index groesser als die Laenge ist 
        // passiert nix
        if (this.length() < index) {
            return;
        }
        // Wenn der Index gleich ist, die die Listenlaenge
        // muss das neue Element angehängt werden
        if (this.length() == index) {
            this.append(val);
            return;
        }
        // Wenn der Index Null ist, muss das Element als erster neuer
        // Knoten eingefuegt werden
        if (index == 0) {
            new_node.setNext(first);
            first = new_node;
            return;
        }
        // In allen anderen Faellen muss das n-te Element 
        // aufgesucht werden und der neue Knoten dort eingefügt werden.
        Node<T> n = first;
        for (int i=1; i<index; i++) {
            n = n.getNext();
        }
 
        new_node.setNext(n.getNext());
        n.setNext(new_node);
 
    }