Verkettete Liste rückwärts ausgeben

[slaner]

Hallo zusammen,

Ich habe angefangen Java zu lernen und habe die Aufgabe bekommen die Ausgabe der folgenden einfach verkettete Liste rückwärts ausgeben zu lassen.

class Listelement { 
      String daten; 
      Listelement naechster; 
      Listelement letzter; 					
      
      public Listelement()
      {
         if (letzter == null)
            letzter = this;
      }
      void setDaten(String datenNeu) {       	
         daten = datenNeu; 
         naechster = null; 
      } 
      void anhaengen(String datenNeu) {         
         if (naechster == null) { 
            naechster = new Listelement(); 
            naechster.setDaten(datenNeu); 
            letzter = naechster;  				
         } 
         
         else 
            naechster.anhaengen(datenNeu); 
        
         System.out.println("Daten " + datenNeu + " wurden eingefügt."); 
      } 
      void ausgeben() { 						
         System.out.println(daten); 
         if (naechster != null) 
        	 naechster.ausgeben(); 
      } 
} 
public class ketterück { 
   public static void main(String[] args) {       
      Listenelement listenAnfang = new Listenelement();    
      listenAnfang.setDaten("Element 1"); 
      
      for (int element = 2; element < 4; element++) 	
         listenAnfang.anhaengen("Element " + element); 
    
      listenAnfang.ausgeben(); 
   } 
}

Leider weiß ich nicht so genau wie ich das anstellen kann. Könnt Ihr mir vielleicht ein paar Tipps geben?

Vielen Dank schon mal.

 

[langhaar!]

Liste durchiterieren und Daten auf einen Stack legen, Daten vom Stack holen, bis er leer ist.

 

[Landei]

Angenommen, du befindest dich im ersten ListenElement. Dann müsstest du alle folgenden ListenElemente rückwärts ausgeben, und dass [edit: und _/dann/schließlich] das erste ListenElement selbst. Angenommen, du befindest dich im zweiten ListenElement... Erkennst du ein Muster?

 

[fastjack]

Vermutlich rekursiv vom letzten beginnend, bis Du den ersten hast, der keinen letzten hat

Mal's Dir einfach auf und schmeiß die Umlaute aus dem Sourcecode.

 

[slaner]

Danke schon mal für eure Tipps. Werde nachher gleich mal probieren.

@langhaar Bin leider noch nicht so weit. Wie funktioniert das mit dem Stack genau?

Lg

 

[fastjack]

Du iterierst von vorn nach hinten durch die Liste und packst jedes Element auf einen Stack. Am Ende räumst Du den Stack wieder ab. Damit hast Du reverse order. Wenn die Aufgabenstellung von der Uni/Schule ist, weis ich aber nicht, ob es so in deren Sinne ist...

 

[langhaar!]

Wie funktioniert das mit dem Stack genau?

Der Stack ist eine Datenstruktur, die du dir wie eine Ablage vorstellen kannst. Du kannst nur Daten oben auf einen Stapel legen und kannst immer nur das oberste Element entnehmen.

Wenn du deine Liste Element für Element auf einen Stapel legst, dann ist das erste Element ganz unten und das letzte Element ganz oben. Bei der Entnahme kannst du immer nur das oberste Element nehmen. Somit bekommst du die umgekehrte Reihenfolge.

Übrigens wird Rekursion intern auch mit Stacks verwirklicht. Somit entsprechen sich die hier vorgestellen Lösungen. Die Verwendung von Rekursion ist eleganter und akademischer.

 

[Landei]

Du brauchst keinen Stack (obwohl es so auch funktioniert), nur eine rekursive Methode.

 

[langhaar!]

Umgekehrt könnte man sagen: du brauchst keine Rekursion (obwohl es so auch funktioniert), nur einen Stack.

Da es aber eine Übungsaufgabe ist, wird vermutlich die rekursive Lösung angestrebt sein.

 

[slaner]

Stimmt. Ich soll die Aufgabe Rekursiv lösen. Werd mich gleich mal dran setzten und es versuchen. Habt mir auf jeden Fall schon mal sehr weiter geholfen. :toll:

 

[slaner]

So hat leider etwas gedauert bis ich es versuchen konnte. Leider komm ich nicht dahinter wie es mit der Rekursion funktionieren soll. Hab auch schon mal etwas gegoogelt aber da ist alles irgendwie nicht so für anfänger beschrieben oder ich kapier es einfach nicht ;(. Wie muss ich das angehen? Könnt ihr mir vieleicht noch ein paar Tipps geben?

 

[Marco13]

Du brauchst keinen Stack (obwohl es so auch funktioniert), nur eine rekursive Methode.

Das sollte wohl heißen: "Du brauchst keinen eigenen Stack"

EDIT: Noch @topic: Schreib' vielleicht mal eine Rekursive Methode, die die Elemente vorwärts ausgibt (oder beschreib genauer, wo die Frage liegt)

 

[Firephoenix]

Rekursion ist immer eine Übungssache und auch eine Frage der Kreativität.
In deinem Fall könnte man sich folgendes überlegen:

Du hast eine rekursive Funktion die eine Liste kriegt und diese Rückwärts ausgeben soll.

Als erstes brauchst du einen Rekursionsanker, dieser besteht fast immer aus den trivialfällen.
Diese sind in dem Fall: Liste ist leer und Liste hat nur in Element.

Liste ist leer ist sogar kein Anker, sondern wirklich nur ein Trivialfall.
Wenn die Liste nur ein Element hat gibt man das Element aus und hat sie Rückwärts ausgeben.

Jetzt kommt der Spannende Teil, was machst du wenn die Liste mehr als 1 Element hat (z.b. 3).

Du merkst dir das erste Element der Liste, entfernst es aus der Liste, gibst die restliche Liste rückwärts aus und anschließend das erste Element.

So wenn man jetzt ganz genau aufgepasst hat kommt man schon darauf wo die rekursion stattfindet "gibst die restliche Liste rückwärts aus"...


Beispiel des Ablaufs:

Aufruf mit Liste A,B,C
Größer 0 und Größer 1
Also A merken
---Aufruf mit Liste B,C
---Größer 0 und Größer 1
---Also B merken
------Aufruf mit Liste C
------Größer 0 und gleich 1
------Also C ausgeben
---Das gemerkte B ausgeben
Das gemerkte A ausgeben

Damit sollte die Methode eigentlich leicht machbar sein, falls was nicht klappt einfach deinen Code mal posten.
Gruß