LinkedList add-Methode

[baker333]

Hi,

ich habe ein Verständnisproblem beim Hinzufügen von Knoten an einer bestimmten Stelle in einer LinkedList (oder ähnlich dazu ist das HInzufügen in einer sortierten Liste). Es handelt sich um eine rekursive Methode, aber ich verstehe nicht so ganz, was passiert, wenn man die Basisfall (steps == 0) erreicht hat. Mit der der "return" Anweisung bei steps == 0 wird doch die gesamte Methode beendet, wie wir dann der restliche Teil der Liste, der nach dem einzufügenden Element kommt "angehängt"?

Danke

public void add(int index, int value) {
        if ( index < 0 || index > size()) {
            throw new IndexOutOfBoundsException("Der Index liegt außerhalb des korrekten Wertebereichs!");
        }
        this.head = add(this.head, index, value);
    }

private ListNode add(ListNode node, int steps, int value) {
        if (steps == 0) {
            return new ListNode(value, node);
        }
        node.setNext(add(node.getNext(), steps-1, value));
        return node;
    }

 

[mihe7]

Mit der der "return" Anweisung bei steps == 0 wird doch die gesamte Methode beendet

Es wird die aktuelle Ausführung der Methode beendet. Da die Methode mehrfach (rekursiv) aufgerufen wird, gibt es mehrere Ausführungen.

 

[baker333]

okay, aber nach dem der Basisfall erreicht wurde wird sie doch nicht mehr ausgeführt, oder?

 

[mihe7]

Was ist der Basisfall?

 

[httpdigest]

Nachdem der "Basisfall" erreicht ist, existieren gerade noch `n` (mit `n` = Länge der Liste) verschachtelte/rekursive Aufrufe, die gerade noch auf das Wiederkehren des tiefsten rekursiven Aufrufs (der, der den Basisfall erreicht hat) warten, um dann ihrerseits mit `node.setNext(...)` weiterzumachen.

 

[baker333]

Nachdem der "Basisfall" erreicht ist, existieren gerade noch `n` (mit `n` = Länge der Liste) verschachtelte/rekursive Aufrufe, die gerade noch auf das Wiederkehren des tiefsten rekursiven Aufrufs (der, der den Basisfall erreicht hat) warten, um dann ihrerseits mit `node.setNext(...)` weiterzumachen.

Das verstehe ich nicht ganz, wenn der Basisfall (steps == 0) erreicht wurde, wird dann nicht mit "return new ListNode(value, node)" einerseits ein neuer Knoten mit dem entsprechenden Wert erzeugt und eine Referenz auf den Nachfolger gesetzt und dieser Nachfolger hat eine Referenz auf seinen Nachfolger und so weiter?

Also ich gehe die Liste durch und solange der Basisfall nicht erreicht ist, wird die Methode rekursiv aufgerufen (mit steps -1) und die Knoten werden quasi bis dahin "verknüpft".

 

[mihe7]

Vielleicht wird es deutlicher, wenn man den Code etwas umschreibt:

    private ListNode add(ListNode node, int steps, int value) {
        if (steps == 0) {
            return new ListNode(value, node);
        }
        ListNode oldNext = node.getNext();
        ListNode newNext = add(oldNext, steps-1, value);
        node.setNext(newNext);
        return node;
    }

 

[httpdigest]

Solange die Abbruchbedingung (dein "Basisfall") nicht erreicht ist, passiert erstmal noch überhaupt gar nichts mit der Liste. Da wird noch nichts umgesetzt, da noch kein rekursiver Aufruf den setNext(...) Aufruf tatsächlich erreicht hat. Jeder rekursive Aufruf steckt noch im Auswerten des Arguments von setNext(...) fest, nämlich add(...).
Und wenn die Abbruchbedingung erreicht ist, ist effektiv immer noch nichts passiert. Erst, wenn der tiefste rekursive Aufruf mit seinem Knoten zurückkehrt, wird die Rekursion quasi aufgerollt/"unwinded" und jeder rekursive Aufruf ruft setNext(...) auf.

 

[baker333]

Solange die Abbruchbedingung (dein "Basisfall") nicht erreicht ist, passiert erstmal noch überhaupt gar nichts mit der Liste. Da wird noch nichts umgesetzt, da noch kein rekursiver Aufruf den setNext(...) Aufruf tatsächlich erreicht hat. Jeder rekursive Aufruf steckt noch im Auswerten des Arguments von setNext(...) fest, nämlich add(...).
Und wenn die Abbruchbedingung erreicht ist, ist effektiv immer noch nichts passiert. Erst, wenn der tiefste rekursive Aufruf mit seinem Knoten zurückkehrt, wird die Rekursion quasi aufgerollt/"unwinded" und jeder rekursive Aufruf ruft setNext(...) auf.

Was ist denn der "tiefste" rekursive Aufruf? Ich glaube ich bin mir noch nicht so ganz im klaren, wie genau eine rekursive Methode aufgerufen wird.

 

[baker333]

Also wenn eine Methode eine andere aufruft, dann entsteht doch ein Methodenstapel, also die zuletzt aufgerufene Methode wird ausgeführt. Das ist in meinem Fall der Basisfall (steps == 0), in diesem Schritt wird quasi ein neuer Knoten erstellt und mit seinem Nachfolger verknüpft. Die Methode wird vom Stapel genommen und die Methode darunter wird forgesetzt, die wieder den Vorgänger mit dem neu erstellten Knoten verknüpft usw. Sehe ich das richtig?

 

[mihe7]

Sehe ich das richtig?

Denke schon, dass Du das richtige meinst.