verkettete Listen

[Mane123]

Hallo zusammen,

ich habe folgendes Listing gegeben:

class Listenelement {
	String daten;
	Listenelement naechster;
}
	
public class verkettete_Liste_V1 {

//Klassenmethoden für die Verarbeitung der Liste
//die Daten für ein Element setzen
//Übergeben wird die Zeichenektte und das Element der Liste
	
static void setDaten (String datenNeu, Listenelement element) {
	
	//die Zeichenkette setzen
	element.daten = datenNeu;
	
	//das Ende markieren
	element.naechster = null;
	
}

//ein neues Elemtn am ende der Liste einfügen
//übergeben wird die Zeichenkette und der Listenanfang
//das Eigentliche einfügen erfolgt über die Methode setDaten()

static void listeAnhaengen (String datenNeu, Listenelement listenAnfang) {
	//eine Hilfskonstruktion zum wandern in der Liste
	
	Listenelement hilfskonstruktion;
	hilfskonstruktion = listenAnfang;
	
	//durch die Liste gehen, bis das Ende erreicht ist
	
	while (hilfskonstruktion.naechster != null)
		hilfskonstruktion = hilfskonstruktion.naechster;
	
	hilfskonstruktion.naechster = new Listenelement ();
	
	hilfskonstruktion = hilfskonstruktion.naechster;

//die Daten eintragen
		setDaten (datenNeu, hilfskonstruktion);
}

//die Ausgabe der kompletten Liste
static void listeAusgeben (Listenelement listenAnfang) {
	//die Hilfskonstruktion
	Listenelement hilfsKonstruktion;
	hilfsKonstruktion = listenAnfang;
	
	//erstets Element ausgeben
	System.out.println (hilfsKonstruktion.daten);
	
	//und nun den Rest
	
	while (hilfsKonstruktion.naechster != null) {
		//bitte in einer Zeile eingeben
		
			
		hilfsKonstruktion = hilfsKonstruktion.naechster;
		
		System.out.println (hilfsKonstruktion.daten);
	}
	
	
	
}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
Listenelement listenAnfang = new Listenelement ();
//die Daten im ersten Listenelement setzen

setDaten ("Element 1", listenAnfang);
//weitere Elemente in eine Schleife einfügen

for (int element = 2; element < 4; element++) {

listeAnhaengen ("Element " + element, listenAnfang);
}

listeAusgeben (listenAnfang);

	}

}

Ich komme hier allerdings mit der Methode listeAnhaengen nicht so ganz zurecht:

Das Listing is ja nicht direkt auf Objekte zugeschnitten und das verwirrt mich als Java-Anfänger schon recht stark.

1.
Bei der oben stehenden Methode gibt es die Schleife while (hilfsKonstruktion.naechster != null)
Wie erkenne ich denn, dass hilfsKonstruktion.naechster auf ein neues Element verweist?

2.
durch die Anweisung hilfsKonstruktion.naechster = new Listenelement ();
wir dadurch nur eine Variable vom Typ Listenelement () angelegt oder ein neues Objekt?

Vielen Dank für eure Hilfe, ich versuch schon seit einigen Stunden das Listing zu verstehen, aber ich steig da nicht so recht durch

 

[Mane123]

Ich hab jetzt ein anderes Listing, welches objektorientiert arbeitet, vielleicht hilft mir das, die verkettete Listen besser zu verstehen:

class Listenelement {
	String daten;
	
	Listenelement naechster;
	
	void setDaten (String datenNeu) {
		//die Zeichenkette setzen
		
		daten = datenNeu;
		
		//das Ende markieren
		
		naechster = null;
	}
	//die Methode zum Anhängen eines neuen Elements
	//sie ruft sich rekursiv auf, bis das Ende erreicht ist
	
	void anhaengen (String datenNeu) {
		
		//wenn das Ende erreicht ist, ein neues Element erzeugen
		
		if (naechster == null) {
			
			naechster = new Listenelement ();
			naechster.setDaten(datenNeu);
		}
		
		//sonst ruft sich die Methode selbst wieder auf
		
		else { 
			naechster.anhaengen (datenNeu);
		}
		
		System.out.println ("Daten " + datenNeu + " wurden eingefügt");
		
	}
	
	//Die MEthode zur Ausgabe der Liste
	//sie ruft sich ebenfalls rekursiv auf, bis das Ende erreicht ist
	
	void ausgeben () {
		
		System.out.println (daten);
		if (naechster != null)
			naechster.ausgeben ();
	}
	
}


public class verkettete_ListeV2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement ();
		
		//die Daten im ersten Listenelemt setzen
		
		listenAnfang.setDaten ("Element 1");
		
		//weitere Element in einer Schleife einfügen
		
		for (int element = 2; element < 4; element ++)
			listenAnfang.anhaengen ("Element " + element);
		
		//die Liste ausgeben
		listenAnfang.ausgeben();
	}

}

Gibt es hier nur ein Objekt? (listenAnfang) Wie werden dann die anderen Elemente (Element 2 und Element 3) bezeichnet, auch als Objekte oder irgendwie anders?

Warum erscheint in Zeile 34 bei der Ausgabeanweisung das "Element 3" doppelt?

Vielen Dank

Viele Grüße

 

[sayang]

Hi.

Zu deinem ersten Listing:
Du hast vor dem Aufruf der methode listeAnhaengen ja gerade das erste Element erzeugt. Dieses Element hat - da es das erste in der Liste ist - keinen Nachfolger (naechster == null).
Nun wird für Element 2 und Element 3 jeweils einmal die Methode listeAnhaengen aufgerufen, aber immer mit deinem ersten Element der liste (als 2. Parameter).

Um nun das Ende der Liste zu finden, muss per Schleife die Liste durchwandert werden.
Dazu wird erstmal eine neue Referenz auf das (selbe) Objekt des ersten Listenelements erzeugt. Zugegeben, die Benennung der Variablen/Referenzen ist hier etwas ungünstig... statt "hilfskonstruktion" wäre so etwas wie "aktuellesElement" wesentlich sprechender.
Nunja. In Zeile 30 ist also dein aktuelles Element (hilfskonstruktion) das erste Element der Liste.
Anschließend wird in der while-Schleife nachgesehen, ob das aktuelle Element einen Nachfolger (naechster) hat oder nicht. Hat es einen Nachfolger wird dieses nächste Element in deiner Variablen hilfskonstruktion gespeichert, ist also nun das aktuelle Element. Dieses wird nun wiederum überprüft, ob es einen Nachfolger hat usw.
Das ganze läuft solange, bis das aktuelle Element keinen Nachfolger mehr hat (naechster == null). Hier bist du nun am Ende der Liste angekommen. Und hier soll wir ein neues Element angefügt werden.
Daher wird auf der Referenz naechster des aktuellen Elementes hilfskonstruktion eine neue Instanz von Listenelement erzeugt (Zeile 37).
Jetzt, wo dieses neue Element an das Ende der Liste angefügt wurde, wird dieses nächste/letzte listenelement in der Variable hilfskonstruktion gespeichert und anschließend die Daten gesetzt (Zeilen 39, 42).
Man muss in Zeile 39 aber nicht notwendigerweise die Referenz afu das nächste Element setzen, um die Daten dort speichern zu können. Möglich wäre auch, Z. 39 komplett wegzulassen und in Z. 42 zu schreiben:

setDaten(datenNeu, hilfskonstruktion.naechster)

Ich hoffe, das beantwortet deine Frage 1 aus dem ersten Beitrag.

Frage 2:
hilfskonstruktion sowie hilfskonstruktion.naechster sind bereits Variablen bzw. Referenzen. Erst durch new Listenelement() wird ein Objekt erzeugt.

Beispiel:

Foo bar; //Anlegen einer Variable/Referenz namens bar vom Typ Foo. Diese Variable ist "leer" (null) bzw. die Referenz zeigt noch nicht auf ein Objekt von Foo
...
...
bar = new Foo(); //Erzeugen einer neuen Instanz von Foo und speichern in bar

Dein 2. Listing schau ich mir morgen an

Lg
sayang

 

[HLX]

Gibt es hier nur ein Objekt? (listenAnfang) Wie werden dann die anderen Elemente (Element 2 und Element 3) bezeichnet, auch als Objekte oder irgendwie anders?

Es gibt zusätzlich zum Listenanfang soviele Objekte wie Elemente hinzugefügt wurden. Bei jedem "new ListenElement" wird ein neues Objekt erzeugt. Die Objekte sind durch Referenzen miteinander verkettet.

Warum erscheint in Zeile 34 bei der Ausgabeanweisung das "Element 3" doppelt?

Weil du die Methode "anhängen" zweimal vollständig durchläufst und daher auch immer an der Ausgabe vorbeikommst. Beim ersten Mal ist das nächste Listenelement nicht null (du hast ja bereits Element 2 angehangen), so dass die Methode erneut aufgerufen wird. Beim zweiten Mal wird das Element 3 angehangen und die gewünschte Ausgabe erfolgt. Anschließend wird der erneute Methodenaufruf verlassen, da die Methode durch ist und du landest direkt nach der aufrufenden Stelle des zweiten Durchlaufs (Zeile 34). Die Ausgabe erfolgt erneut. Verschiebe die Ausgabe dorthin, wo das eigentliche Hinzufügen geschieht:

if (naechster == null) {
     naechster = new Listenelement ();
     naechster.setDaten(datenNeu);
     System.out.println ("Daten " + datenNeu + " wurden eingefügt");
}

 

[Loonatic]

Hi @ all, hab mich gerade erst hier bei euch registriert. also habt ein weinig nachsicht.

Ich hab vollgendes Problem ich hab eine ArrayListe die in x-Richtung von 0,1,2 läuft also 3 Zellen jeder dieser Zellen ist auch eine ArrayListe. In jeder dieser ArrayListe habe ich Punkt die per zufallsgenerator erstellt werden. Nun hab ich per Tastatur einen Punkt eingegeben und jetzt wird der eingegebene Punkt mit allen Punktn aus der ArrayListe berechnet um den Abstand zu erhalten.

so ich habe 10 Punkte insgesammt von jedem hab ich den Abstand zu meinen eingegeben Punkt. Diese 10 Abstände sind in keiner Liste jetzt will ich sie der Größe nach sortieren und den Kleinsten Abstand ausgeben.

Das soll das prinzip der Nachbarsuche sein!!!

Hoffe mir kann jemand helfen sonst lauf ich hier noch amok!!!

 

[Loonatic]

Oh scheiße sorry habe es mit dem java code gerade erst gesehen
mom

public class CellArrayStructur {
    

    public static void main(String[] args) throws IOException {
        int dimX = 3;
        int numPoints=10;
        double lengthX = 1.0;
        double deltaX = lengthX/dimX;
        //System.out.println("deltaX = " + deltaX);

        Point[] points = new Point[numPoints];

        for (int i=0;i<numPoints;i++) {
            points[i] = new Point(Math.random(),Math.random());
            //points[i].print();
        }

        ArrayList[] liste = new ArrayList[dimX];
        for (int i=0;i<dimX;i++) liste[i] = new ArrayList();

        for (int i=0;i<numPoints;i++) {
            int index = (int)(points[i].x/deltaX);
            liste[index].add(points[i]);
        }

        //Y-Werte in jeder Liste aufsteigend sortieren
        for (int i=0;i<dimX;i++) {
                System.out.println("Anzahl der Punkte in Zelle "+i+": "+liste[i].size()+" Punkte");
                System.out.println();
                Collections.sort(liste[i]);

                //Punkte in den Zellen mit X und Y Koordinaten
                int s = liste [i].size();
                for(int k=0; k<s; k++){
                    Point p = (Point)liste [i].get(k);
                    System.out.println("Punkt " +"X " +p.x + " , " +"Y " +p.y +"   ");
                }
                System.out.println("--------------------------------------------------------");
        }

         //Eingabe der X und Y Koordinaten um den nächstgelegenen Punkt zu finden
        InputStreamReader inStream = new InputStreamReader( System.in ) ;
        BufferedReader bf = new BufferedReader( inStream );

        String inData;

        System.out.println("Geben Sie die Punktkoordinaten ein:");
            System.out.print("Für X: ");
            inData = bf.readLine();
            float inX = Float.valueOf(inData);

            System.out.print("Für Y: ");
            inData = bf.readLine();
            float inY = Float.valueOf(inData);

            System.out.println("Sie haben eingegeben: " +"("+ inX  +" / " + inY +")" );
            System.out.println("Abstände der Punkte zum Eingegebenen Punkt: ");

        //Berechnung der Abstände zum Eingegebenen Punkt
        Point ep = new Point (inX, inY);
        for(int i=0; i<dimX; i++){
            for(int j=0; j < liste[i].size(); j++){
              
                double abstand;
                abstand = ep.berechneAbstand((Point)liste[i].get(j));
                
                System.out.println(+abstand);
            }
        }

        for (int i=0; i<dimX; i++){
            int min=0;
            for(int j=0; j<liste.length(); j++) {
                if(liste[j] < liste[min])
                min=i;
            }
        }

        System.out.println("Der kleinste Abstand zum eingegeben Punkt: ");

 

[Mane123]

Hallo,

mir ist die ganze Sache dank eurer Antworten etwas klarer geworden.

Ich möchte die folgende Ausführung so abändern, dass das Listenende nicht immer wieder neu ermittelt werden muss, sondern neue Elemente direkt am Ende der Liste angehängt werden.
Weiterhin soll ich das Ende der Liste jetzt neben dem Anfang der Liste in einer eigenene Instanz speichern.

Also: hier der ursprüngliche Code:

class Listenelement {
	String daten;
	
	Listenelement naechster;
	
	void setDaten (String datenNeu) {
		//die Zeichenkette setzen
		
		daten = datenNeu;
		
		//das Ende markieren
		
		naechster = null;
	}
	//die Methode zum Anhängen eines neuen Elements
	//sie ruft sich rekursiv auf, bis das Ende erreicht ist
	
	void anhaengen (String datenNeu) {
		
		//wenn das Ende erreicht ist, ein neues Element erzeugen
		
		if (naechster == null) {
			
			naechster = new Listenelement ();
			naechster.setDaten(datenNeu);
		}
		
		//sonst ruft sich die Methode selbst wieder auf
		
		else { 
			naechster.anhaengen (datenNeu);
		}
		
		System.out.println ("Daten " + datenNeu + " wurden eingefügt");
		
	}
	
	//Die MEthode zur Ausgabe der Liste
	//sie ruft sich ebenfalls rekursiv auf, bis das Ende erreicht ist
	
	void ausgeben () {
		
		System.out.println (daten);
		if (naechster != null)
			naechster.ausgeben ();
	}
	
}


public class verkettete_ListeV2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement ();
		
		//die Daten im ersten Listenelemt setzen
		
		listenAnfang.setDaten ("Element 1");
		
		//weitere Element in einer Schleife einfügen
		
		for (int element = 2; element < 6; element ++)
			listenAnfang.anhaengen ("Element " + element);
		
		//die Liste ausgeben
		listenAnfang.ausgeben();
	}

}

Hier mein geänderter Code, kann das so stimmen? Ich glaube fast nicht, denn das wäre dann doch irgendwie zu einfach gegangen?? Bitte um Hilfe und - wahrscheinlich ist es auch nötig - um Verbesserung.

Danke!

class Listenelement {
	String daten;
	
	Listenelement naechster;
	
	void setDaten (String datenNeu) {
		//die Zeichenkette setzen
		
		daten = datenNeu;
		
		//das Ende markieren
		
		naechster = null;
	}
	//die Methode zum Anhängen eines neuen Elements
	//sie ruft sich rekursiv auf, bis das Ende erreicht ist
	
	void anhaengen (String datenNeu) {
		
		//wenn das Ende erreicht ist, ein neues Element erzeugen
		
		if (naechster == null) {
			
			naechster = new Listenelement ();
		   
			naechster.setDaten(datenNeu);
			naechster.getEnde ();
		}
		
		//sonst ruft sich die Methode selbst wieder auf
		
		//else { 
			//naechster.anhaengen (datenNeu);
		//}
		
		//System.out.println ("Daten " + datenNeu + " wurden eingefügt");
		
	}
	

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


public class TEST52 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement ();
		Listenelement listenEnde =   new Listenelement ();
		
		//die Daten im ersten Listenelemt setzen
		
		listenAnfang.setDaten ("Element 1");
		
		//weitere Element in einer Schleife einfügen
		listenAnfang.ausgeben ();
		for (int element = 2; element < 6; element ++) {
		listenEnde.anhaengen ("Element " + element);
		listenEnde = listenEnde.getEnde ();
		listenEnde.ausgeben ();
		}
			
	}

}

Viele Grüße

 

[Marco13]

Hmja ... ich glaub' ... das ist es nicht so ganz. Du hast ja jetzt das Durchlaufen der Liste einfach nach draußen in die main gezogen. Und Anfang und Ende haben nichts miteinander zu tun.

Aber erstmal vorneweg: Ich gehe davon aus, dass das eine Hausaufgabe ist. Poste am besten mal die genaue Aufgabenstellung, und was an Code vorgegeben war.

 

[Mane123]

Hallo!

Also eine Hausaufgabe ist das nicht, aus der Schule bin ich schon draußen Ich mach so nen JAva-Kurs neben dem Beruf.

Also die Aufgabenstellung lautet wie folgt:

Erweitern Sie die verkettete Liste (also das erste Listing in meinem letzten Post) so, dass das Listenende beim Anhängen nicht immer wieder neu ermittelt werden muss, sondern neue Elemente direkt am Ende der Liste angehängt werden können.

Hinweise dazu:

- Sie müssen neben dem Anfang der Liste jetzt auch das Ende der Liste in einer Instanz speichern können

- Erstellen Sie eine MEthode, die Ihnen das aktuelle Ende der Liste zurückliefert. Alternativ können Sie sich das Listenende auch von der MEthode zum Anhängen liefern lassen.

- Setzen Sie den Wer der Instanz für das Listenende nach dem Anhängen neuer Element jewiels auf das aktuelle Ende der Liste und Rufen Sie die Methode zum Anhängen neuer Listenelement mit diesem Wert auf.

Wie würdet ihr das dann umsetzten, ist meine Lösung denn auch nich in den Ansätzen korrekt? *verzweifel*

Viele Grüße

 

[Marco13]

Naja... Eherlich gesagt bin ich nicht 100% sicher, wie das umgesetzt werden soll. In der ersten Version, die du gepostet hast (die mit den statics), wäre das einfach. Bezeogen auf die letzte Version... ich gehe eben davon aus, dass sowas gehen sollte wie

Listenelement anfang = new Listenelement();
anfang.setDaten("1");

anfang.anhaengen("2");
anfang.anhaengen("3");
anfang.anhaengen("4");

und bei den letzten drei Aufrufen eben nicht mehr jedes mal das letzte Element gesucht werden sollte. Ein bißchen komisch ist das aber schon. Das Listenende würde dann zwar in jedem Knoten liegen, wäre aber nur im ersten immer gültig.
Naja. Kannst ja mal schauen ob du sowas wie den Code oben hinkriegst, und wenn nicht, nochmal bescheid sagen.

 

[Mane123]

Danke für deine Hinweise. Jetz rate mal wie ich der Sache gegenüber stehe, so richtig zurecht komme ich mit dieser Aufgabe nicht wirklich :/

So wie du es da jetz aufführst, dann würde ich aber kein Element "listenEnde" erzeugen?
Dies ist allerdings in der Aufgabe vorgesehen.
Je länger ich mich mit der Sache beschäftige, umso verrückter werde ich noch.

Viele Grüße

 

[Marco13]

Naja, da würde dann das Listenende in jedem Knoten gespeichert, aber wie gesagt, das ist ziemlich seltsam ???:L

Bist du sicher, dass der Code so gedacht war, wie in dem letzten geposteten Codestück? Ich könnte mir auch sowas vorstellen wie

class SimpleLinkedList
{
    private Listenelement anfang = ...
    private Listenelement ende = ...

    public void anhaengen(String data)
    {
        // Sonderfälle (leere Liste usw) abfragen
        ...

        // Allgemeiner Fall:
        ende.anhangen(data);
        ende = ende.getNaechster();
    }

}

Vorher wäre das eben sowas wie

class SimpleLinkedList
{
    private Listenelement anfang = ...

    public void anhaengen(String data)
    {
        // Sonderfälle (leere Liste usw) abfragen
        ...

        // Allgemeiner Fall: Aufwändiges durchlaufen der Listenelemente....
        Listenelement current = anfang;
        while (current.getNaechster() != null)
        {
            current = current.getNaechster();
        }
        current.anhangen(data);
    }
}

Hat vielleicht noch jemand anderes eine Idee, wie man das "vernünftig" machen könnte? Das Ende in jedem Knoten zu speichern und nur im ersten Element zu benutzen kann ja nicht Sinn der Sache sein....?

 

[Mane123]

Hallo!

Also ich muss den aktuellen Wert in der Instanzvariablen listenEnde speichern. Das mach ja mein Lösungsvorschlag, oder nicht?

Viele Grüße

 

[Marco13]

Das ist ja das irritierende. Das Listenende ist nirgendwo in einer Instanzvariablen gepeichert. Und auch sonst bringt das irgendwie nicht viel. Genau so, wie du jetzt das listenEnde speicherst, hättest du es ja von vornherien speichern können. D.h. man hätte das Durchlaufen der Liste einfach vermeiden können, indem man "anhängen" nicht immer auf dem Anfang, sondern immer auf dem Ende der Liste aufruft.

Hoffentlich meldet sich hier noch jemand der etwas mehr Einfühlungsvermögen in die Intentionen der Steller solcher Aufgaben hat ..

 

[Mane123]

Hallo!

Also ich probier schon die ganze Zeit damit rum und ich komme einfach nicht auf die Lösung des Problems

Hier noch mal der Code:

class Listenelement {
	String daten;
	
	Listenelement naechster;
	
	void setDaten (String datenNeu) {
		//die Zeichenkette setzen
		
		daten = datenNeu;
		
		//das Ende markieren
		
		naechster = null;
	}
	//die Methode zum Anhängen eines neuen Elements
	//sie ruft sich rekursiv auf, bis das Ende erreicht ist
	
	void anhaengen (String datenNeu) {
		
		//wenn das Ende erreicht ist, ein neues Element erzeugen
		
		if (naechster == null) {
			
			naechster = new Listenelement ();
			naechster.setDaten(datenNeu);
		}
		
		//sonst ruft sich die Methode selbst wieder auf
		
		else { 
			naechster.anhaengen (datenNeu);
		}
		
		System.out.println ("Daten " + datenNeu + " wurden eingefügt");
		
	}
	
	//Die MEthode zur Ausgabe der Liste
	//sie ruft sich ebenfalls rekursiv auf, bis das Ende erreicht ist
	
	void ausgeben () {
		
		System.out.println (daten);
		if (naechster != null)
			naechster.ausgeben ();
	}
	
}


public class verkettete_ListeV2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement ();
		
		//die Daten im ersten Listenelemt setzen
		
		listenAnfang.setDaten ("Element 1");
		
		//weitere Element in einer Schleife einfügen
		
		for (int element = 2; element < 6; element ++)
			listenAnfang.anhaengen ("Element " + element);
		
		//die Liste ausgeben
		listenAnfang.ausgeben();
	}

}

Ich habe aber nun zumindest rausgefunden, dass dieser Quelltext in eine doppelt verkettet Liste umgewandelt werden muss.
Aber ich schaff das nicht. Kann mir hier jemand bitte helfen?

Viele Grüße

 

[Marco13]

Das mit dem Listenende und dem "doppelt verkettet" hat jetzt aber nichts miteinander zu tun?! Wie auch immer.
Vorher hatte ein Listenelement die Eigenschaften
String daten;
Listenelement naechster;
und jetzt muss noch ein
Listenelement vorheriger;
dazukommen.

 

[Mane123]

Das mit dem neuen Listenelement vorheriger in der Klasse Listenelement hätte ich auch gemacht, aber wie das dann weiter geht, weiß ich nicht. ;(

Ich möchte dann später auch noch die Liste rückwärts ausgeben lassen. Dann brauche ich wohl doch eine Element "listenEnde"?

Viele Grüße

 

[Marco13]

Hm. Überleg' dir mal, was in der Methode "anhaengen" alles gemacht werden muss, wenn ein neues Element am Ende angehängt wird:
Das "nächste" vom letzten Element ist das neue
Das "vorige" vom neuen ist das bis dahin letzte...
Versuch' das mal so zu schreiben, und poste dann den Code. Um die Liste rückwärts auszugeben braucht man dann schon das letzte Element. Das klingt immer mehr nach sowas wie

class SimpleLinkedList
{
    Listenelement erstes;
    Listenelement letztes;

    public void anhängen(String daten) { .. . }
    public void ausgeben() { .. . }
    public void rückwärtsAusgeben() { .. . }
}

 

[Mane123]

Danke für die Hnweise, ich hätte die Methode "anhaengen so geändert, damit ich eine Verknüpfung zum vorherigen Listenelement herstellen kann?

void anhaengen (String datenNeu) {
		Listenelement hilfsElement;
		
		hilfsElement = this; //hilfsElement auf das aktuelle Element setzen

		//wenn das Ende erreicht ist, ein neues Element erzeugen
		
		if (naechster == null) {
			
			naechster = new Listenelement ();
			vorheriger = hilfsElement.naechster; //Verknüpfung mit dem vorherigen element aufbauen?
			naechster.setDaten(datenNeu);
		}
		
		//sonst ruft sich die Methode selbst wieder auf
		
		else { 
			naechster.anhaengen (datenNeu);
		}
		
		System.out.println ("Daten " + datenNeu + " wurden eingefügt");
		
	}

Viele Grüße

 

[Marco13]

Nicht so ganz. Die Methode "anhaengen" hangelt sich bis zum Ende, bis das letzte Element gefunden wurde, und dann wird folgendes gemacht:

        hilfsElement = this; // hilfsElement auf das aktuelle Element setzen

        if (naechster == null)  // Ja, jetzt bin ich beim letzten Element angekommen
        {
            // 'this' ist also das bisher letzte Element. 
            // An dieses Element wird jetzt hinten das neue Element angefügt.
            this.naechster = new Listenelement ();

            // Der vorgänger vom Ende ist... AUCH das neue Element? Nee....
            this.vorheriger = hilfsElement.naechster; 

            ...
        }

Versuch' mal, dir wirklich aufzumalen, was dort gemacht werden muss. Im Sinne von

Vor dem Anhängen:

         -----------------
        | Letztes Element |
        |                 |
        |     next------------>null
        |                 |
.....<---- previous       |
        |                 |
         -----------------



Nach dem Anhängen:

         -----------------      ---------------
        | Letztes Element |    | Neues element |
        |                 |    |               |
        |     next------------>|         next------>null
        |                 |    |               |
.....<---- previous       |<----- previous     |
        |                 |    |               |
         -----------------      ---------------

Das hilfsElement braucht man nicht - das ist ja nur "this". Und vielleicht noch als Tipp: Jedes Element ist der Vorgänger seines Nachfolgers....

 

[Mane123]

Also wirklich ich versteh das jetz alles nicht mehr. Ich hab diese blöden doppelt verketteten Listen noch nicht mal richtig in meinem Lehrbuch druchgenommen. Da kann ich mir nicht vorstellen, dass die Lösung für diese Aufgabe so kompliziert sein kann....

Wie das in der Theorie abläuft kann ich mir ja auch vorstellen, ich hab auf Grafiken in meinem Buch, die die einfach verkettete Liste darstellen, dort hab ich mir auch noch ein neues Listenelement dazugezeichnet, welches auf das vorherige Element zeigt.

Aber wie man das in die Praxis umsetzt...

Viele Grüße

 

[Mane123]

Also ich hab mir das noch einmal aufgezeichnet.
Müsste ja so stimmen?

Aber ich glaube, dass über das Element 3 noch das listenEnde gehört?

Viele Grüße

 

[Marco13]

Ein Screenshot wäre besser. Hab' hier kein Word. Notfalls schau ich morgen auf der Arbeit mal.

 

[Mane123]

Hallo!

Also auf ein neues, ich habe nun den Lösungsansatz gefunden. Ich brauche keine doppelte Liste, um die Aufgabe zu lösen.

Hier mal der Code:

class Listenelement {
	String daten;
	
	Listenelement naechster;
	
	void setDaten (String datenNeu) {
		//die Zeichenkette setzen
		
		daten = datenNeu;
		
		//das Ende markieren
		
		naechster = null;
	}
	//die Methode zum Anhängen eines neuen Elements
	//sie ruft sich rekursiv auf, bis das Ende erreicht ist
	
	
	void anhaengen (String datenNeu) {
		
		//wenn das Ende erreicht ist, ein neues Element erzeugen
		
		if (naechster == null) {
			
			naechster = new Listenelement ();
			naechster.setDaten(datenNeu);
		
		
		}
	
	
		
		//sonst ruft sich die Methode selbst wieder auf
		
		else { 
			naechster.anhaengen (datenNeu);
		}
		
	System.out.println ("Daten " + datenNeu + " wurden eingefügt");
		
	}
	Listenelement getEnde () {
		
		return naechster;
		
	}
	//Die MEthode zur Ausgabe der Liste
	//sie ruft sich ebenfalls rekursiv auf, bis das Ende erreicht ist
	
	void ausgeben () {
		
		System.out.println (daten);
		if (naechster != null)
			naechster.ausgeben ();
	}
	
}


public class Aufgabe53 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement ();
		Listenelement listenEnde = new Listenelement ();
		
	
		
		//die Daten im ersten Listenelemt setzen
		
		listenAnfang.setDaten ("Element 1");
		
		//weitere Element in einer Schleife einfügen
		
		for (int element = 2; element < 6; element ++) {
			listenAnfang.anhaengen ("Element " + element);
			
		}
		
		//die Liste ausgeben
		listenAnfang.ausgeben();
	}
}

Ich gehe jetzt einfach strikt den Hinweisen in der Aufgabenstellung nach:

Also ich habe ein neues Listenelement "listenEnde" erzeugt.

Nun muss ich mir das akutelle Ende der Liste nach jedem anhängen von der Methode "void anhaengen" zurückliefern lassen.

Ich schaff es allerdings nicht, die Methode so abzuändern, dass mir der das akutelle Ende zurückgeliefert wird.
Bitte um Hilfe.

Viele Grüße

 

[Marco13]

    Listenelement anhaengen (String datenNeu) {

        //wenn das Ende erreicht ist, ein neues Element erzeugen

        if (naechster == null) {

            naechster = new Listenelement ();
            naechster.setDaten(datenNeu);
            System.out.println ("Daten " + datenNeu + " wurden eingefügt");
            return naechster;

        }



        //sonst ruft sich die Methode selbst wieder auf

        else {
            return naechster.anhaengen (datenNeu);
        }


    }

getEnde liefert jetzt aber NICHT immer das Ende. Nur nebenbei.

 

[Mane123]

Hallo!

Danke für die Hinweise.
Diese Ausführung habe ich bei mir auch schon mal als eine meiner vielen Lösungsalternativen probiert, ich hab diese aber als falsch deklariert.
Begründung:
- die Methode muss ja genauso wie die ursprüngliche Version immer wieder das aktuelle Listenende neu "suchen" (anhaengen wird rekursiv aufgerufen).
- Bei der Ausgabe wird das "Element 5" nicht ausgegeben.

Ich hab mir da eher so was vorgestellt:

Das Objekt "listenEnde" erhält in der for-Schleife in Main immer den aktuellen Wert von "anhaengen" und ruft sich dann anschließend "anhaengen" immer mit dem aktuellen Wert auf.
Die Methode "anhaengen" beginnt dann gleich bei dem letzten Element und muss nich immer wieder von vorne durchlaufen werden.

Ist das nicht möglich, oder habe ich einen falschen Denkansatz?

P.S. Vielleicht ist das auch ein Tip: Ich habe mit "listenAnfang" nichts gemacht, das Objekt könnte ich eigentlich weg lassen. Stimmt das, oder ist hier schon der erste Denkfehler?

Viele Grüße

 

[Marco13]

Natürlich kann man in der for-Schliefe in der main jeweils das Element speichern, das man bei "anhaengen" zurückgegeben bekommt, und beim nächsten Aufruf dan DAran anhängen, um das rekursive Suchen zu verhindern.

Den Listenanfang wird man aber auf jeden Fall speichern müssen, wenn man die Liste von Anfang an Ausgeben will.

 

[Landei]

Ganz einfache Implementierung als Queue (nur an den Enden kann gelöscht oder geschrieben werden), weitere Operationen sind leicht zu implementieren:

(ungetestet)

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Collection;

public class DoubleLinkedList<T> implements Iterable<T> {
  
  private Node<T> start;
  private Node<T> end;
  private int size = 0;
  
  public DoubleLinkedList(T ... ts) {
    for(T t : ts) insertLast(t);
  }

  public DoubleLinkedList(Collection<? extends T> ts) {
    for(T t : ts) insertLast(t);
  }
  
  public int getSize() { return size; }
  
  public void insertFirst(T value) {
    Node<T> node = new Node<T>(value);
    if (start == null) {
      start = node;
      end = node;
    } else {
      start.prev = node;
      node.next = start;
      start = node;
    }
    size++;
  }
  
  public void insertLast(T value) {
    Node<T> node = new Node<T>(value);
    if (end == null) {
      start = node;
      end = node;
    } else {
      end.next = node;
      node.prev = end;
      end = node;
    }
    size++;
  }
  
  public T getFirst() { return start == null ? null : start.value; }
  public T getLast() { return end == null ? null : end.value; }
  
  public T removeFirst() {
    if (start == null) {
      return null;
    } else {
      T t = start.value;
      start = start.next;
      if (start != null) { start.prev = null; }
      size--;
      return t;
    }
  }

  public T removeLast() {
    if (end == null) {
      return null;
    } else {
      T t = end.value;
      end = end.prev;
      if (end != null) { end.next = null; }
      size--;
      return t;
    }
  }

  public Iterator<T> iterator() {
    return new Iterator<T>() {
      Node<T> nextNode = start;
      
      public boolean hasNext() {
        return nextNode != null;
      }

      public T next() {
        if (! hasNext()) { throw new NoSuchElementException(); }
        T value = nextNode.value;
        nextNode = nextNode.next;
        return value;
      }

      public void remove() {
         throw new UnsupportedOperationException();
      }

    };
  }

  public Iterator<T> reverseIterator() {
    return new Iterator<T>() {
      Node<T> nextNode = end;

      public boolean hasNext() {
        return nextNode != null;
      }

      public T next() {
        if (! hasNext()) { throw new NoSuchElementException(); }
        T value = nextNode.value;
        nextNode = nextNode.prev;
        return value;
      }

      public void remove() {
         throw new UnsupportedOperationException();
      }

    };
  }

  
  private static class Node<T> {
    private Node<T> prev;
    private Node<T> next;
    private T value;
    private Node(T value) {
      this.value = value;
    }
  }

}

 

[Mane123]

@ Landei

Danke für die Hilfe, aber das ist nicht das wonach ich suche, ich möchte die Liste so wie oben beschrieben erstellen.

@ Marco13:

Genau das möchte ich auch machen, aber mit der Version die oben steht klappt das nicht.

Wenn ich das Listing so erstellt habe:

class Listenelement {
	String daten;
	
	Listenelement naechster;
	
	void setDaten (String datenNeu) {
		//die Zeichenkette setzen
		
		daten = datenNeu;
		
		//das Ende markieren
		
		naechster = null;
	}
	//die Methode zum Anhängen eines neuen Elements
	//sie ruft sich rekursiv auf, bis das Ende erreicht ist
	
	Listenelement anhaengen (String datenNeu) {
		
		//wenn das Ende erreicht ist, ein neues Element erzeugen
		
		if (naechster == null) {
			
			naechster = new Listenelement ();
			naechster.setDaten(datenNeu);
			System.out.println ("Daten " + datenNeu + " wurden eingefügt");
			return naechster;
			
		}
	
		//sonst ruft sich die Methode selbst wieder auf
		
		else { 
		System.out.println ("Rekurstion durchgeführt");
		return naechster.anhaengen (datenNeu);
			
		
		}
	
		
	}
	
	//Die MEthode zur Ausgabe der Liste
	//sie ruft sich ebenfalls rekursiv auf, bis das Ende erreicht ist
	
	void ausgeben () {
		
	System.out.println (daten);
		if (naechster != null) {
		
			naechster.ausgeben ();
		}
	}
	
}


public class Aufgabe53 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement ();
		Listenelement listenEnde = new Listenelement ();
		
		//die Daten im ersten Listenelemt setzen
		
		listenAnfang.setDaten ("Element 1");
		
		//weitere Element in einer Schleife einfügen
		
		for (int element = 2; element < 6; element ++)
			listenEnde.anhaengen ("Element " + element);
		
		
		
		//die Liste ausgeben
		
		listenAnfang.ausgeben ();
		listenEnde.ausgeben ();
	}
}

ist leider eine Rekursion in anhaengen () enthalten

funktioniert die Ausgabe nicht

wenn ich wie in der Aufgabe gefordert die Methode zum Anhängen neuer Listenelemente mit dem akutellen Ende aufrufe, dann sind die Werte eben in listenEnde enthalten.
Aber ich habe dann keine Werte in listenAnfang stehen... ::/

Viele Grüße

 

[Marco13]

???:L Ähm. Langsam wird's konfus. Beschreib' ggf. nochmal in ganzen, zusammenhängenden Sätzen, was du meinst.

Meinst du sowas wie

for (int element = 2; element < 6; element ++)
{
    Listenelement angehaengtesElement = listenEnde.anhaengen ("Element " + element);
    listenEnde = angehaengtesElement;
}

(könnte man auch in einer Zeile schreiben, nur zu Verdeutlichung)

 

[Mane123]

Okay, ich werde morgen Abend alles noch mal zusammenschreiben.

Die for-Schleife die du geschreiben hast, speichert in "angehaengtesElement" den akteullen wert von listenEnde zwischen und weißt dann anschließend diesen Wert "listenEnde" zu.

Dadurch müsste zumindest mal die Rekursion in "anhaengen" vermieden werden, und ich kann die if-verzwiegung durch eine while-Schleife ersetzen.

Dann gibt es allerdings noch ein Problem mit der Ausgabe, denn diese funktioniert nicht, da in listenAnfang ja keine Werte gespeichert sind.?

Viele Grüße

 

[Marco13]

Jetzt wird's noch konfuser

Die for-Schleife die du geschreiben hast, speichert in "angehaengtesElement" den akteullen wert von listenEnde zwischen und weißt dann anschließend diesen Wert "listenEnde" zu.

Dort wird nicht der aktuelle Wert von "listenEnde" gespeichert, sondern das, was bei "anhängen" zurückgegeben wird - nämlich genau das (neue!!!) letzte Element. Man könnte auch schreiben:
listenEnde = listenEnde.anhaengen("Element " + element);
oder wenn man die Methode denn so nennen wollte:
listenEnde = listenEnde.anhaengenUndAlsNeuesEndeZurückgeben("Element " + element);

Das mit dem if und while kann ich gerade nicht einordnen.

Dann gibt es allerdings noch ein Problem mit der Ausgabe, denn diese funktioniert nicht, da in listenAnfang ja keine Werte gespeichert sind.?

Ja, weil du am Anfang ein Listenelement für den Anfang und eines für das Ende anlegst, und NUR an das Ende etwas anhängst. Wenn man diese Liste am Ende "einfach" verwendbar machen wollte, wäre eine Hilfsmethode praktisch, bzw. eine "SimpleLinkedList"-Klasse, wie ich sie schon ein paar mal angedeutet hatte. Der Ablauf ist ja eigentlich sowas wie:

// Am Anfang ist die Liste leer
Listenelement listenAnfang = null;
Listenelement listenEnde = null;

// Wenn das ERSTE Element eingefügt wird, dann ist das der listenAnfang...
listenAnfang = new Listenelement();
listenAnfang.setDaten("1");

// Aber solange nur EIN Element da ist, sind Anfang und Ende gleich!
listenEnde = listenAnfang;

Jetzt können neue Elemente angehängt werden. Ursprünglich war das dann sowas (in einer for-Schleife, aber das ist egal) :

listenAnfang.anhaengen("2");
listenAnfang.anhaengen("3");
...

Da besteht aber noch das Problem, dass man bei jedem Anhängen vom Anfang bis zum Ende laufen muss. Deswegen ist es besser, immer am ENDE anzuhängen - und das neu angehängte Element ist danach das Ende. (Der Anfang ändert sich nie).

// Neues Element anhängen, und das neue ELement als neues listenEnde merken:
Listenelement angehaengtesElement = listenEnde.anhaengen("2");
listenEnde = angehaengtesElement;

// Noch eins...:
angehaengtesElement = listenEnde.anhaengen("3");
listenEnde = angehaengtesElement;

...

Das könnte man auch einfach schreiben als

listenEnde = listenEnde.anhaengen("2");
listenEnde = listenEnde.anhaengen("3");
listenEnde = listenEnde.anhaengen("4");
...

Zum Ausgeben verwendet man dann den listenAnfang:

listenAnfang.ausgeben ();

 

[Mane123]

Guten Morgen,

Dort wird nicht der aktuelle Wert von "listenEnde" gespeichert, sondern das, was bei "anhängen" zurückgegeben wird - nämlich genau das (neue!!!) letzte Element.

mit aktuellen Wert meinte ich den neuen Wert. Hab mich da nicht so verständlich ausgedrückt, sorry.


Ist überhaupt eine Hilfsmethode nötig?
Ich habe die Änderungen wie folgt umgesetzt:

 class Listenelement {
	String daten;
	
	Listenelement naechster;
	
	void setDaten (String datenNeu) {
		//die Zeichenkette setzen
		
		daten = datenNeu;
		
		//das Ende markieren
		
		naechster = null;
	}
	//die Methode zum Anhängen eines neuen Elements
	//sie ruft sich rekursiv auf, bis das Ende erreicht ist
	
	Listenelement anhaengen (String datenNeu) {
		
		
		
			
			naechster = new Listenelement ();
			naechster.setDaten(datenNeu);
			System.out.println ("Daten " + datenNeu + " wurden eingefügt");
			
			
	
		return naechster;
		
	}
	
	//Die MEthode zur Ausgabe der Liste
	//sie ruft sich ebenfalls rekursiv auf, bis das Ende erreicht ist
	
	void ausgeben () {
		
	System.out.println (daten);
		if (naechster != null) {
		
			naechster.ausgeben ();
		}
	}
	

}




public class Aufgabe53 {


	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement ();
		Listenelement listenEnde = new Listenelement ();
		
		//die Daten im ersten Listenelemt setzen
		
		listenAnfang.setDaten ("Element 1");
		
		listenEnde = listenAnfang;
		
		//weitere Element in einer Schleife einfügen
		
		for (int element = 2; element < 6; element ++) {
			 Listenelement angehaengtesElement = listenEnde.anhaengen ("Element " + element);
	    listenEnde = angehaengtesElement; 
	   
		}
		
		
		
		//die Liste ausgeben
		
	listenAnfang.ausgeben ();
		
	}
}

Hier müssten doch die geforderten Punkte erfüllt sein?

- das aktuelle Ende wird von anhaengen zurückgeliefert

- die Rekursion in anhaengen ist weg

- die Methode anhaengen wird immer mit dem akutellen Wert von listenEnde aufgerufen.

- die Ausgabe von listenAnfang funktioniert auch.

Ist das so korrekt?

Viele Grüße

 

[Marco13]

Im Prinzip ja.

 

[Mane123]

Danke! Aber das "im Prinzip" stört mich etwas, gehört da noch irgendwas verbessert?

Wie funktioniert dann die rekursive Ausgabe vom listenEnde aus?
Also:

Element 5
element 4
Element 3
Element 2
Element 1

Viele Grüße

 

[HLX]

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

 

[Mane123]

Hallo!

Auf die unten stehende Lösung bin ich auch grad gekommen. Diesmal sogar selber

Meine Methode schaut so aus:

void endeAusgeben () {

if (naechster != null) {

naechster.endeAusgeben ();
System.out.println (daten);

}

else
     System.out.println (daten);

}

Ich hab's druch try and error rausbekommen. So ganz bin ich noch nicht durchgestiegen, aber zumindest klappts.
Ich schau mir die Methode heute Abend noch mal genau an.
Endlich hab ich die Aufgabe durch

Viele Grüße

 

[Marco13]

"Im Prinzip" weil jetzt eben relativ viele "Verwaltungsaufgaben" bei demjenigen liegen, der diese Klasse benutzen soll. Und Benutzen sollte immer möglichst einfach sein, und möglichst wenige Fehlerquellen liefern. Wenn man das, was jetzt in der Main steht, in eine Klasse Packen würde, könnte man sie einfach so handhaben:

SimpleLinkedList list = new SimpleLinkedList();
list.ausgeben(); // Gibt "[]" aus

list.anheangen("Bla");
list.anhaengen("Blub");
list.ausgeben(); // Gibt "[Bla, Blub]" aus

...

Abgesehen davon sollte man am Anfang nicht zwei Listenelemente erstellen, sondern nur eins:

Listenelement listenAnfang = new Listenelement ();
listenAnfang.setDaten("1");
Listenelement listenEnde = listenAnfang;

Und genau SOwas könnte dann eben in der "anhaengen"-Methode der Klasse "SimpleLinkedList" gemacht werden:

private Listenelement listenAnfang;
private Listenelement listenEnde;

public void anhangen(String daten)
{
    if (listenAnfang == null)
    {
        listenAnfang = new Listenelement ();
        listenAnfang.setDaten("1");
        listenEnde = listenAnfang;
    }
    else
    {
         listenEnde.anhengen(...)
         ...
    }
}

 

[Mane123]

Hallo!

Danke für die Tipps und Hinweise.
Ich bin ja noch ziemlich am Anfang mit Java lernen (4. Monat, in der Woche ca. 7 Std.)
und es geht bei dieser Aufgabe hauptsächlich darum, dass man das alles versteht.

Ich poste morgen das gesamte Listing noch einmal (bin jetzt gerade an einem anderen PC).
Aber so wie es oben steht und ich die rekursiche Rückwärtsausgabe gemacht habe, stimmt es ja?

Viele Grüße

 

[Marco13]

Ja, die Rückwärtsausgabe stimmt so wohl.