Doppelt verkettete Liste rückwärts ausgeben

A

Albi_2020

Mitglied
Hi,
ich habe folgende Aufgabe:
"Erweitern Sie die zweite Version der einfach verketteten Liste so, dass die Liste auch rückwärts ausgegeben werden kann. Erstellen Sie dazu eine entsprechende Methode, die sich rekursiv aufruft."

Aktuell kenne ich ja immer nur den Nachfolger. Um die Aufgabenstellung zu lösen, muss ich ja den einzelnen Listenelementen verklickern, wer ihre Vorgänger sind...allerdings habe ich aktuell keine Idee, wie ich das umsetzen kann. Eigentlich muss ja nur die Referenz vom vorherigen Element auf den Vorgänger gesetzt werden. Aber ich weiß nicht wie und wo ich die Referenz übergebe.

Java: 
public class Listenelement {
    
    String daten;
    Listenelement naechster;
    

    void setDaten(String datenNeu) {
        daten = datenNeu;
        naechster = null;
    }
    
    Listenelement anhaengen(String datenNeu) {
            naechster = new Listenelement();
            naechster.setDaten(datenNeu);
            return naechster;
    }

  
    void ausgeben() {
        System.out.println(daten);
        if (naechster != null)
            naechster.ausgeben();
    }
}

public class Aufgabe {

    public static void main(String[] args) {
                        
        Listenelement listenAnfang = new Listenelement();
        
        listenAnfang.setDaten("Element 1");
        
        Listenelement listenEnde = listenAnfang;
        
        for (int element = 2; element < 20; element++) {
            listenEnde = listenEnde.anhaengen("Element " + element);
        }       

        listenAnfang.ausgeben();
    }

}
 
Schau Dir doch einfach einmal Deine Methode ausgeben im Detail an:
Code: 
    void ausgeben() {
        System.out.println(daten);
        if (naechster != null)
            naechster.ausgeben();
    }

Da gehst Du ja rekursiv die Elemente durch. Wenn Du die Methode mal mit eigenen Worten beschreibst: Was macht die Methode? Kannst Du über diese Methode ohne weitere Änderungen an der Liste selbst, die Ausgabe sozusagen "umdrehen"?
 
Albi_2020 hat gesagt.:
Aktuell kenne ich ja immer nur den Nachfolger. Um die Aufgabenstellung zu lösen, muss ich ja den einzelnen Listenelementen verklickern, wer ihre Vorgänger sind.
Zum Vergrößern anklicken....
Nein, das musst du nicht und sollst du m.E. auch nicht. Man beachte die von mir fett markierte Aussage

Albi_2020 hat gesagt.:
"Erweitern Sie die zweite Version der einfach verketteten Liste so, dass die Liste auch rückwärts ausgegeben werden kann. Erstellen Sie dazu eine entsprechende Methode, die sich rekursiv aufruft."
Zum Vergrößern anklicken....

Was du daher brauchst ist eine Dry Function, eine die einen Node erhält und sich rekursiv mit dem Nachfolger dieses Nodes aufruft solange es einen Nachfolger gibt. Nach dem rekursiven Aufruf erfolgt die Ausgabe. Damit erscheint die Ausgabe eines Rekursionsschritts erst nachdem die Rekursion aufgelöst wurde und du erhälst so die Rückwärtsausgabe.
 
Die rekursive Methode hat zwei Schritte wenn du diese verstanden hast, dann sollte es ei Fach sein, die Anforderung zu lösen.

Wobei da ja schon Moxxi auch geschrieben hat, was wichtig ist: Nach dem rekursiven Aufruf erfolgt die Ausgabe.
 
Es ist wie als ob du erst alle Elemente auf einen Stapel legst und dann abarbeitest. Das sind nur 2 Tätigkeiten - ablegen und bearbeiten.

Pseudo:

printRevert(node)
Wenn node nicht null, dann rekursiver Aufruf mit seinem Nachffolger
Node ausgeben

Dann musst du diese Funktion nur initial mit dem Head der LinkedList aufrufen
 
JustNobody hat gesagt.:
Schau Dir doch einfach einmal Deine Methode ausgeben im Detail an:
Code: 
    void ausgeben() {
        System.out.println(daten);
        if (naechster != null)
            naechster.ausgeben();
    }

Da gehst Du ja rekursiv die Elemente durch. Wenn Du die Methode mal mit eigenen Worten beschreibst: Was macht die Methode? Kannst Du über diese Methode ohne weitere Änderungen an der Liste selbst, die Ausgabe sozusagen "umdrehen"?
Zum Vergrößern anklicken....

Wieso nicht einfach ganz einfach einmal diesen ersten Ansatz verfolgen. Was macht diese Methode?

1. Aktuelles Element Ausgeben
2. Restliche Elemente ausgeben

Nun will man die Ausgabe umdrehen, also:
1. Restliche Elemente ausgeben
2. Aktuelles Element ausgeben

Aber nun haben wir mehrfach die Lösung gegeben statt den TE dazu zu bringen, die Lösung zu finden.

Und das finde ich etwas befremdlich, zumal so ein Ansatz komplett ignoriert wurde - und das ist aus meiner Sicht der eigentliche Ansatz bei jeder Entwicklung: man muss sich abstrakt überlegen, wie so etwas gehen könnte bzw. bei bestehendem Code benötigt man erst einmal ein klares Verständnis des Codes...
 
Habe es jetzt hinbekommen mit eurer Hilfe. Vielen Dank. Ja ich muss zugeben, dass mir die rekursiv nicht klar war, Warum die Werte trotzdem gespeichert werden.
 
Hallo zusammen,

ich bin mit der gleichen Aufgabe beschäftigt ( auch ein Kurs ). Und habe die Methode wie folgt angepasst:
[CODE lang="java" title="Liste Rekursiv"]// Methode zum Rekursiven Rückwärtslauf
void ausgebenRev() {
if ( next != null) {
next.ausgeben();
System.out.println(daten);
}
}[/CODE]
Die Aufgabe ist eigentlich fertig zur Abgabe, nur bei diesem Element bin ich mir unsicher ob das so richtig ist.
Vielen Dank für ein Feedback.

Grüsse Olli
 
Hi Olli,

Das sieht noch nicht richtig aus.

Hast du es mal ausprobiert? Wird das letzte Element ausgegeben?

Wenn es kein folgendes Element gibt, dann ruft er die Methode nicht rekursiv auf (richtig) und er gibt die Daten auch nicht aus.
 
Hallo,

danke für die schnelle Antwort. In der Ausgabe kommen die Elemente (2-30) und dann das erste Element.
[CODE lang="java" title="Ausgabe Liste"]Element laufend 2
Element laufend 3
..........
Element laufend 28
Element laufend 29
Element laufend 30
Element 1 / Kopf
[/CODE]

Aber irgendwie vermute ich der er nur das erste Element unten anstellt. Oder liege ich da daneben?
 
Ach ja - das hatte ich noch übersehen: Bei einer Rekursion rufst doch die Methode sich selbst auf. Du rufst aber eine andere Methode auf ...
 
Hallo,
ja stimmt. Den Teil hatte ich nicht bedacht. Da funktioniert das ganze Konstrukt nicht mehr. Wenn die Methode sich selbst aufruft würde es ja eine Endlosschleife geben, da das letze Element in der Kette,also in diesem Fall das Erste Element, ja auch nicht null ist .
Ich habe jetzt auch in verschieden Büchern nachgelesen und habe es so verstanden : Wenn die Kette rückwärts ausgegebn werden soll, muss jedem Knoten sein Vorgänger und sein Nachfolger bekannt sein. Ausser das Erste und das Letzte Element haben keinen Vorgänger bzw. Nachfolger, verweisen aber auf sich ( gegenseitig). Dann spricht man aber bereits von einer doppelt verketteten Liste. In der Aufgabenstellung steht " Erweiter sie die zweite Version der einfach verketteten Liste so, dass die Liste auch rückwärts ausgegeben werden kann. Erstelle sie dazu eine entsprechende Methode , die sich rekursiv aufruft. Ich hänge unten mal den aktuellen Stand der Liste an.
[CODE lang="java" title="Einfach verkettete Liste"]/*##################################
*
* einfach verkettete Liste V2
##################################*/

// Die Klasse für die Listenelemente
// jetzt auch mit Methoden
class Listenelement {
String daten;
Listenelement next;


// die Methode zum setzen der Daten
void setDaten(String datenNeu) {
// die Zeichenkette setzen
daten = datenNeu;
// das Ende markieren
next = null;
}

// die Methode zum Anhängen eines neuen Elements
// am Ende der Liste
Listenelement anhaengen(String datenNeu) {
next = new Listenelement();
next.setDaten(datenNeu);
return next;
}

// die Methode zur Ausgabe der Liste
// sie ruft sich rekursiv auf, bis das
// Ende ereicht ist
void ausgeben() {
System.out.println(daten);
if(next != null) {
next.ausgeben();
}
}
// Methode zum Rekursiven Rückwärtslauf
void ausgebenRev() {
if ( next != null) {
next.ausgeben();
System.out.println(daten);
}
}


}
public class Einsendeaufgabe_5_3 {

public static void main(String[] args) {
// ein neues Listenelement erzeugen
Listenelement listenAnfang = new Listenelement();

// die Daten im ersten Listenelement setzen
listenAnfang.setDaten("Element 1 / Kopf");

// Das Listenende entspricht dem Listenanfang
Listenelement listenEnde = listenAnfang;

// weitere Elemente in einer Schleife einfügen
for(int element = 2; element < 31; element++)
listenEnde = listenEnde.anhaengen("Element laufend "+element);

// Die Liste ausgeben normal
listenAnfang.ausgeben();
// Die Liste rückwärts ausgeben
listenAnfang.ausgebenRev();
}

}[/CODE]
 
Zuletzt bearbeitet:
Das letzte Element ist nicht null. Aber die Referenz auf den Nachfolger, der ist null.

Und damit funktioniert auch die Ausgabe rückwärts.

Was bei der einfachen Verkettung nicht geht, ist das rückwärts gehen im Sinne von: ich habe jetzt ein Element: was ist der Vorgänger.

Aber das brauchst du nicht, denn du gehst vorwärts durch die Liste. Nur die Ausgabe kommt nach dem rekursiven Aufruf.

Somit hattest Du es eigentlich fast schon. Der Aufruf müsste nur eben die eigene Methode mit dem Nachfolger sein.

Aber dann wäre meine Erwartungshaltung, dass das letzte Element nicht ausgegeben wird. Und da solltest du den Fehler einfach finden können, wenn du für das letzte Element die Methode einmal durchspielst.
 
Auf Grund des Titels des Threads ggf. noch die Frage: Wenn die Aufgabe sein soll, dass man eine doppelt verkettete Liste baut, dann können wir auch gerne dies durchgehen. Aber nur um die Elemente rückwärts auszugeben braucht man dies nicht. Das geht mit einer rekursiven Methode auch.

Die Aufgabe "Erweitern Sie die zweite Version der einfach verketteten Liste so, dass die Liste auch rückwärts ausgegeben werden kann. Erstellen Sie dazu eine entsprechende Methode, die sich rekursiv aufruft." impliziert also noch nicht die Erweiterung auf eine doppelt verkettete Liste.
 
Hallo,
nein ich hatte ein verständnisfehler wegen den doppelten Listen. Die Aufgabenstellung sagt ganz klar einfache Liste also halte ich mich daran und versuche das zu lösen.
 
Hallo zusammen,
ich konnte die Aufgabe mit Hilfe von meinem Tutor lösen. Wie wird das hier gehandelt mit den Lösungen?
Die Methode muste nur leicht abgewandelt werden um zu funktionieren. Ich weiss das das abschreiben allein nichts bringt aber ich würde gern anderen weiterhelfen. Wenn man den funktionierenden Code stück für stück zerlegt lernt man auch ziehmlich viel (meiner Meinung nach).

grüsse Olli
 
Du kannst Die Lösung gerne hier präsentieren. Wobei es wenig hilft, nur fertigen Code vorzusetzen, weshalb wir versuchen, immer nur Starthilfe zu geben.

Und Du hattest ja fast die Lösung. Der Aufruf musste lediglich der rekursive Aufruf sein und die Ausgabe musste auf dem if Block raus.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Verkettete Liste rückwärts ausgeben
Antworten: 3
Verkettete liste rückwärts ausgeben
Antworten: 18
Verkettete Liste rückwärts ausgeben
Antworten: 12
Einfügen in eine doppelt verkettete Liste
Antworten: 8
Doppelt Verkettete Zirkular-Liste
Antworten: 1

Zurück
Oben