Doppelt verkettete Liste rückwärts ausgeben

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();
    }

}
 
K

kneitzel

Gast
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"?
 

MoxxiManagarm

Top Contributor
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.
Nein, das musst du nicht und sollst du m.E. auch nicht. Man beachte die von mir fett markierte Aussage

"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."

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.
 
K

kneitzel

Gast
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.
 

MoxxiManagarm

Top Contributor
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
 
K

kneitzel

Gast
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"?

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...
 

Albi_2020

Mitglied
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.
 

Olli76

Mitglied
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
 
K

kneitzel

Gast
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.
 

Olli76

Mitglied
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?
 
K

kneitzel

Gast
Ach ja - das hatte ich noch übersehen: Bei einer Rekursion rufst doch die Methode sich selbst auf. Du rufst aber eine andere Methode auf ...
 

Olli76

Mitglied
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:
K

kneitzel

Gast
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.
 
K

kneitzel

Gast
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.
 

Olli76

Mitglied
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.
 

Olli76

Mitglied
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
 
K

kneitzel

Gast
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
D Doppelt Verkettete Zirkular-Liste Java Basics - Anfänger-Themen 1
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 8
scratchy1 doppelt verkettete Liste testen Java Basics - Anfänger-Themen 8
B Doppelt Verkettete Liste - Ist alles gut so? Java Basics - Anfänger-Themen 3
U Datentypen Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 13
J Methoden Doppelt verkettete Liste remove(Object) Java Basics - Anfänger-Themen 8
B OOP Über eine doppelt verkettete Liste iterieren Java Basics - Anfänger-Themen 4
L Doppelt verkettete Liste Java Basics - Anfänger-Themen 6
R doppelt verkettete Liste aus Arrays erstellen Java Basics - Anfänger-Themen 1
S Doppelt verkettete Liste Java Basics - Anfänger-Themen 3
G Doppelt Verkettete Liste Java Basics - Anfänger-Themen 2
A Doppelt Verkettete Liste Java Basics - Anfänger-Themen 16
E doppelt verkettete liste Java Basics - Anfänger-Themen 10
E Datentypen Doppelt verkettete Liste Java Basics - Anfänger-Themen 10
P Einfügen in doppelt verkettete Liste Java Basics - Anfänger-Themen 7
S Queue als doppelt verkettete Liste Java Basics - Anfänger-Themen 2
N doppelt verkettete liste einfügen Java Basics - Anfänger-Themen 7
K Datentypen Einfach/Doppelt verkettete Liste Java Basics - Anfänger-Themen 4
W Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 2
G Doppelt verkettete, generische Liste Java Basics - Anfänger-Themen 11
D doppelt verkettete Liste Java Basics - Anfänger-Themen 16
S Doppelt Verkettete Liste Java Basics - Anfänger-Themen 7
M Doppelt verkettete Liste Zeiger Vorgänger beim Einfügen Java Basics - Anfänger-Themen 2
J doppelt verkettete Liste Java Basics - Anfänger-Themen 5
L doppelt verkettete Liste Java Basics - Anfänger-Themen 6
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 12
B Doppelt verkettete Liste Java Basics - Anfänger-Themen 16
R Datentyp Ring - zyklisch doppelt verkettete Liste - HILFE! Java Basics - Anfänger-Themen 12
R doppelt verkettete Liste Java Basics - Anfänger-Themen 8
F doppelt verkettete liste! Java Basics - Anfänger-Themen 8
R doppelt verkettete azyklische Liste Java Basics - Anfänger-Themen 2
T Klasse in Java für doppelt verkettete Listen Java Basics - Anfänger-Themen 4
H Doppelt verkettete Listen Java Basics - Anfänger-Themen 2
S doppelt verkettete Listen Java Basics - Anfänger-Themen 4
X Vererbung: Doppelt verkettete Listen Java Basics - Anfänger-Themen 16
O Doppelt verkette Liste Element löschen Java Basics - Anfänger-Themen 15
J Doppelt verkette Liste ich bitte um Hilfe Java Basics - Anfänger-Themen 4
I Input/Output Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 3
N package wird doppelt im exporer angezeigt Java Basics - Anfänger-Themen 2
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
J Fehler beim generieren von 4 Zufallszahlen Zahl doppelt ist eigentlich ausgeschlossen Java Basics - Anfänger-Themen 9
T Löschen in doppelt verketteter Liste Java Basics - Anfänger-Themen 1
L Input/Output Println wird doppelt ausgeführt Java Basics - Anfänger-Themen 11
D Interface Frame doppelt durch Aufruf der GUI Klasse Java Basics - Anfänger-Themen 1
B BufferedReader gibt Datei-Inhalt doppelt aus Java Basics - Anfänger-Themen 3
M Liste Implementation, doppelt next() Java Basics - Anfänger-Themen 13
D Klassen Doppelt so viele Elemente in Arraylist ? Java Basics - Anfänger-Themen 4
Salo Datentypen "Doppelt" List(e) ("gesucht") Java Basics - Anfänger-Themen 6
L do-while-Schleife läuft doppelt, try catch fehler Java Basics - Anfänger-Themen 12
T Java Methode wird unerwünscht doppelt aufgerufen?! Java Basics - Anfänger-Themen 4
OnDemand Doppelt Werte CSV Java Basics - Anfänger-Themen 2
llabusch Verkette Listen - Einfach und Doppelt Java Basics - Anfänger-Themen 3
N Erste Zeile bei BufferedReader doppelt lesen? Java Basics - Anfänger-Themen 2
E Erste Schritte Sortieren von Objekten in doppelt-verlinkter Liste Java Basics - Anfänger-Themen 9
S Methoden Methode wird doppelt aufgerufen ... Java Basics - Anfänger-Themen 5
J Mehrere Zufallszahlen erzeugen, aber keine darf doppelt erzeugt werden - Wie? Java Basics - Anfänger-Themen 5
B Doppelt gekettete Listen Java Basics - Anfänger-Themen 4
G PropertyChangeListener empfängt Events doppelt Java Basics - Anfänger-Themen 5
L doppelt verkette Liste Java Basics - Anfänger-Themen 5
H Fenster doppelt gezeichnet. Java Basics - Anfänger-Themen 2
G Einfügen aus Zwischenablage - alles doppelt? Java Basics - Anfänger-Themen 2
G JFileChooser kommt doppelt Java Basics - Anfänger-Themen 3
N Nullpointerexception bei Doppelt verketteter Liste Java Basics - Anfänger-Themen 7
M Listen richtig doppelt verkettet? Java Basics - Anfänger-Themen 13
D Exceptions in doppelt verketteter Liste Java Basics - Anfänger-Themen 5
C verify() wird doppelt aufgerufen (JTable + InputVerifier) Java Basics - Anfänger-Themen 8
H doppelt verkette liste Java Basics - Anfänger-Themen 2
L rückwärtsausgeben einer doppelt verketteten liste Java Basics - Anfänger-Themen 2
G JList und ListCellRenderer - Vector erscheint doppelt Java Basics - Anfänger-Themen 6
G JComboBox gibt SelectedItem immer doppelt aus Java Basics - Anfänger-Themen 4
B Array doppelt Felder löschen Java Basics - Anfänger-Themen 27
M Code wird doppelt ausgeführt Java Basics - Anfänger-Themen 2
R Zeilen aus datei lesen + doppelt gespeichert? Java Basics - Anfänger-Themen 3
G Trotz Abfrage immer noch Zahlen doppelt Java Basics - Anfänger-Themen 3
R Benutzerregistrierung: Doppelt registriert. Java Basics - Anfänger-Themen 8
M Verkettete Liste Java Basics - Anfänger-Themen 1
S Einfach-Verkettete-Listen Ausgabe zeigt nur 1. und letzte instanz Java Basics - Anfänger-Themen 2
H Java verkettete Liste, Wert eines Index zurückgeben Java Basics - Anfänger-Themen 1
Igig1 Autoparkplatz verkettete Liste erstes und letztes Auto Java Basics - Anfänger-Themen 13
R Rückgabe: verkettete Liste Java Basics - Anfänger-Themen 2
R einfach verkettete Liste Java Basics - Anfänger-Themen 1
R einfach verkettete Liste Java Basics - Anfänger-Themen 12
B Verkettete Liste durchgehen und einzelne Elemente in neue Liste tun Java Basics - Anfänger-Themen 9
B Bin komplett am verzweifeln :( Verkettete Liste die Objekte hat Attribut auslesen Java Basics - Anfänger-Themen 14
V einfach verkettete Listen Java Basics - Anfänger-Themen 10
A Verkettete Liste Java Basics - Anfänger-Themen 2
L verkettete Liste Java Basics - Anfänger-Themen 15
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
C Methoden Über eine einfach verkettete Liste Java Basics - Anfänger-Themen 8
H Verkettete Liste Java Basics - Anfänger-Themen 7
N Verkettete liste rückwärts ausgeben Java Basics - Anfänger-Themen 18
K Verkettete Liste und seine Methoden Java Basics - Anfänger-Themen 1
A Was könnten typische Prüfungsaufgaben zum Thema lineare, verkettete Listen sein? Java Basics - Anfänger-Themen 5
N Verkettete Liste implementieren Java Basics - Anfänger-Themen 5
O Einfach verkettete Liste - Revert Methode Java Basics - Anfänger-Themen 1
G Verkettete Liste - Neu erzeugte Elemente werden nicht ausgegeben Java Basics - Anfänger-Themen 5
S Einfach verkettete Liste Element an bestimmter Position einfügen Java Basics - Anfänger-Themen 24
C Verkettete Liste - sortiert einfügen Java Basics - Anfänger-Themen 7
R Erste Schritte Verkettete Liste will einfach nicht in meinen Schädel Java Basics - Anfänger-Themen 11

Ähnliche Java Themen

Neue Themen


Oben