einfach verkettete Liste verstehen

matze86

Bekanntes Mitglied
Im folgenden habe ich ein Code, welcher zur Schulung dient, trotz mehrfacher Durcharbeitung des Heftes bin ich noch nicht mit der Objektorientierung warm geworden. Das heißt im folgenden Code habe wir Referenzen auf Instanzvariablen. Aber es ist oft die Rede von "Listen", nur es sind doch nur schein Listen, also Referenzen oder?

Meine Probleme liegen hauptsächlich bei den Variablen und Referenz-Variablen. Ich habe im unteren Code mal etwas kommentiert, vielleicht kann mir das jemand mal mit einfachen Worten erklären.

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

public class lernen {
    static void setDaten(String datenNeu, Listenelement element) {

        element.daten = datenNeu;
        element.naechster = null;
    }
    
    static void listeAnhaengen(String datenNeu, Listenelement listenAnfang) {
        Listenelement hilfsKonstruktion; //warum wird hier hilfsKonstruktion den Typ Listenelement (also der Klasse) zugewiesen und dann in der nächsten Zeile
        hilfsKonstruktion = listenAnfang; // die Referenz hilfsKonstruktion auf listenAnfang gesetzt?
        while (hilfsKonstruktion.naechster != null) { //wie kann hilfsKonstruktion.naechster mehrere inhalte haben?
            hilfsKonstruktion = hilfsKonstruktion.naechster;}//warum wird das gesetzt?
    
        hilfsKonstruktion.naechster = new Listenelement();
    
        hilfsKonstruktion = hilfsKonstruktion.naechster;
    
        setDaten(datenNeu, hilfsKonstruktion);
    }
    
    static void listeAusgeben(Listenelement listenAnfang) {
        Listenelement hilfsKonstruktion;
        hilfsKonstruktion = listenAnfang;
        System.out.println(hilfsKonstruktion.daten);

        while (hilfsKonstruktion.naechster != null) {
            hilfsKonstruktion = hilfsKonstruktion.naechster;
            System.out.println(hilfsKonstruktion.daten);
        }
    }
    
    public static void main(String[] args) {
        Listenelement listenAnfang = new Listenelement();
    
        setDaten("Element 1", listenAnfang);
    
        for (int element = 2; element < 4; element++)
            listeAnhaengen("Element " + element, listenAnfang); //hier wird jedes mal immer das startelement übergeben?
    
        listeAusgeben(listenAnfang);
    }
    }
 
Das heißt im folgenden Code habe wir Referenzen auf Instanzvariablen.
Hier bitte aufpassen: Du hast nur Referenzen auf Instanzen. Nicht auf Instanzvariablen!

Und bei dem Code gilt dann:
Listenelement hilfsKonstruktion; //warum wird hier hilfsKonstruktion den Typ Listenelement (also der Klasse) zugewiesen und dann in der nächsten Zeile
Hier wird nichts zugewiesen! Es wird lediglich eine neue lokale Variable hilfsKonstruktion erstellt, in der Referenzen auf Listenelement gespeichert werden können.

hilfsKonstruktion = listenAnfang; // die Referenz hilfsKonstruktion auf listenAnfang gesetzt?
Genau, hier wird der Variablen etwas zugewiesen - und zwar der Listenanfang.

while (hilfsKonstruktion.naechster != null) { //wie kann hilfsKonstruktion.naechster mehrere inhalte haben?
hilfsKonstruktion.naechster hat immer nur einen Inhalt. Und es wird hier geschaut, ob dieser Inhalt null ist oder nicht. Ist es nicht null, dann wird in die Schleife gegangen.

hilfsKonstruktion = hilfsKonstruktion.naechster;}//warum wird das gesetzt?
Damit wird hilfsKonstruktion auf das nächste Listenelement gesetzt. Und dann erfolgt die nächste Prüfung.

Wir können uns das einmal bildlich vorstellen: Du hast einen Zug (entspricht der Liste). Du kannst aber nur von der Zugmaschine aus nach hinten gehen. Also von der Lok zum 1. Waggon, dann zum 2. Waggon u.s.w. - es gibt also keinen Weg zurück.

Was Du nun im Code hast ist folgendes:
- Wir wollen da jetzt einmal durchlaufen. Dazu brauchen wir eine Referenz auf einen Waggon (Entspricht der Variablen vom Typ Listelement).
- Wir fangen da an, wo wir anfangen können: An der Lok: Wir setzen diese Referenz also auf den ersten Waggon nach der Lok. (listenAnfang wäre dann der erste Waggon, die Liste selbst wäre sozusagen die Lok - die auch nur den ersten Waggon kennt!)
- Nun bauen wir eine Schleife: Wir schauen nach, ob am aktuellen Waggon noch ein weiterer Waggon hängt (next != null).
- Ist dies der Fall, dann rücken wir einen Waggon weiter. (Der aktuelle Waggon ist dann der nächste Waggon)

So können wir also bis zum letzten Waggon gehen. Nach der Schleife wissen wir: wir sind am Ende!
 
OK, sehr gut erklärt danke. Aber was ich noch nicht verstehe wo kommt die Liste her?
Und wenn wir bei den Zug bleiben, wo werden die Waggon's gespeichert? Denn man hat ja nur "listenAnfang".
Also wird bei jeden Durchlauf so zusagen ein anderer Wert für hilfsKonstruktion.naechster gespeichert?
Wenn ja was wird da gespeichert? Wenn ich es ausgebe kommen nur undefinierbare Zeichen.
 
Der Zug (Liste) wird in der main() erzeugt (Wobei Zug eher ein Waggon ist. Es gibt keine explizite Lok. Jeder Waggon kann hier der Anfang des Zuges sein.):
Listenelement listenAnfang = new Listenelement();

Im Anschluss wird der Waggon "gefüllt":
setDaten("Element 1", listenAnfang);
Damit ist im ersten Waggon "Element 1" gespeichert.

In der nun folgenden Schleife wird von 2 bis 3 gezählt (<4 - geht also bis 3):
for (int element = 2; element < 4; element++)

Nun wird für jede Zahl die Methode listeAnhaengen aufgerufen. Dabei wird der Zug, der bisher erzeugt wurde, mitgegeben sowie die Zeichenkette.

Diese Methode geht dann bis zum letzten Waggon (Wie bereits erklärt.) Dann geht es aber noch wie folgt weiter:

Es wird ein neuer Waggon erzeugt und angehängt:
hilfsKonstruktion.naechster = new Listenelement();

Da nun ein neuer Waggon erzeugt und angehängt wurde, können wir einen Waggon weiter gehen:
hilfsKonstruktion = hilfsKonstruktion.naechster;

Und zuletzt können die mitgegebenen Daten in dem Waggon hinterlegt werden:
setDaten(datenNeu, hilfsKonstruktion);

Wenn ich es ausgebe kommen nur undefinierbare Zeichen.
Was genau versuchst Du zum Ausgeben? Die Methode listeAusgeben?
Da sollten Dir nacheinander eigentlich - jeweils in einer Zeile - der Inhalt der "Waggons" ausgegeben werden. Also etwas wie
Element 1
Element 2
Element 3
 
Damit meinte ich "System.out.println(hilfsKonstruktion.naechster)".
println() ruft die toString() Methode der Klasse auf ("naechster" ist vom Typ "Listenelement". Da du diese nicht überschrieben hast, wird die von Object geerbte verwendet und die gibt den Klassennamen und einen Hash aus.

Entweder du überschreibst toString() mit deiner gewünschte Ausgabe oder du gibst direkt das aus, was du sehen möchtest, z. B. "hilfsKonstruktion.naechster.daten". Ich hoffe ich habe mich beim Überfliegen nicht verguckt. 😉
 
Damit meinte ich "System.out.println(hilfsKonstruktion.naechster)".
Das ist ja eine Instanz von Listenelement. Das kannst du so erst einmal nicht ausgeben, da es die toString Methode nicht überschreibt und daher nur die Klasse@Hashcode ausgibt.

Aber du willst ja auch nicht das Listenelement ausgeben sondern den gespeicherten Wert, also das Daten Element. (Siehe die Ausgabe Methode, die das so macht)
 
Nun wird für jede Zahl die Methode listeAnhaengen aufgerufen. Dabei wird der Zug, der bisher erzeugt wurde, mitgegeben sowie die Zeichenkette.
Genau da steckt noch mein Unverständnis. Wie kann ich in einer Variable listenAnfang mehrere Elemente (in dem Fall Waggon's) speichern?

Ich wollte mal in 'hilfsKonstruktion.naechster' schauen, was so gespeichert wurde, weil es nicht "null" ist. Ist nur für mich zum nachvollziehen.
 
Dadurch, dass Du eine Referenz auf ein nächstes Element hast, kannst Du da beliebig viele Elemente aneinander hängen. Also so wie bei Zügen. In einen Waggon kannst Du nur eine Ladung stecken. Aber Du kannst an den ja noch ein Waggon hängen. Und an den wieder. u.s.w.

Und wenn Du da rein schauen willst, dann kannst Du entweder die toString Methode überschreiben oder Du gibt die Elemente von Hand aus (Also data und dann wieder naechster.) Wie das gehen kann siehst Du ja in der Ausgabe Methode.
 
Hallo auf die Frage wo kommt die Liste her.


Die Liste bildest du selber.
Du willst oder ihr sollte eigentlich selber eine ArrayListe erstellen, und nicht die fertige aus Java benutzen.
Deshalb findest du auch nicht was sich Liste nennt wie du es vileicht gewohnt bist.


Die liste entsteht im speicher indem du immer wider neue Objekte erstellt in der anhäng methode machst du ja new Listenelement.
und übergibst dem neuen Objekt die daten und als ref null. was das ende der Liste ist.

1 objekt1 hallo ref -> objekt2
2 objekt2 test ref -> objekt3
3 objekt3 test2 ref -> Null
 
Zuletzt bearbeitet:
OK, ich habe das ganze noch paar mal durchgespielt, außer eine Zeile weiß ich jetzt bescheid.
Hier nochmal ein Codeausschnitt mit den hoffentlich richtigen Kommentaren.
Java:
    static void listeAnhaengen(String daten,Listenelement anfang) {
        Listenelement hilfsvariable; // variable vom Typ der Klasse
        hilfsvariable = anfang; // hilfsvariable bekommt den Wert anfang zugewiesen (also den Anfang des ganzen ab 1. Element")
        while (hilfsvariable.naechster != null){ // wenn in hilfsvariable.nächster keine null steht, wird
            hilfsvariable = hilfsvariable.naechster; //hier eine neue Referenz gebildet. //Aber genau hier weiß ich nicht, warum beim nächste Durchlauf etwas anderes in hilfsvariable.naechster stehen soll
        }
        hilfsvariable.naechster = new Listenelement(); //hier wird in "hilfsvariable.naechster" eine neue Referenz zugewiesen, wo ".naechster"  den Wer null hat und das ende markiert
        hilfsvariable = hilfsvariable.naechster; //zuweisung der variable
        
        setDaten(daten, hilfsvariable);
    }
 
Java:
hilfsvariable = hilfsvariable.naechster; //hier eine neue Referenz gebildet. //Aber genau hier weiß ich nicht, warum beim nächste Durchlauf etwas anderes in hilfsvariable.naechster stehen soll
Es wird keine neue ref gebildet. Es wird die Liste durchgegangen und wenn die ref gleich Null ist. Ist in dieser Variablen die ref auf das letzte Objekt.

Und disem Objekt gibst du anschließend die ref des neuen Objekt.
Die ref des neuen setzt du ja später auf null. Was dann das neue Ende ist.


Tipp gehe deine while doch mal im Debugger von Hand durch. Lasse dir zum test doch die ref mal in der Schleife bei jedem Durchlauf in der Konsole ausgeben.
Und vergkeiche nachdem
du etwas hinzugefügt hast.
 
Das ist das, was ich in #2 beschrieben hatte.

Die Referenz wird immer ein Element weiter gesetzt bis es kein weiteres Element mehr gibt.
 
Jetzt habe ich es glaube gefasst.
Wenn wie im Code im #1
hilfsKonstruktion.naechster gleich null ist, wird mit
hilfsKonstruktion.naechster = new Listenelement();
eine neues Element erzeugt, also eine neue Referenz.

Dadurch hat hilfsKonstruktion.naechster nach mehreren Durchläufen auch mehrere Referenzen.
Die Referenzen werden in der while-schleife so lange "abgearbeitet" bis hilfsKonstruktion.naechster den Wert null hat.
Das ist jetzt richtig oder?
 
Mir ist gerade etwas aufgefallen, dass wenn ich im code #1 in der main Methode vor der for-Schleife listenAnfang.naechster
ausgebe, zeigt es auf null - logisch.
wenn ich aber nach der for-Schleife listenAnfang.naechster ausgebe, zeigt es auf das 1. Element, obwohl ja mehrere vorhanden sind.
 
Mir ist gerade etwas aufgefallen, dass wenn ich im code #1 in der main Methode vor der for-Schleife listenAnfang.naechster
ausgebe, zeigt es auf null - logisch.
wenn ich aber nach der for-Schleife listenAnfang.naechster ausgebe, zeigt es auf das 1. Element, obwohl ja mehrere vorhanden sind.
"naechster" zeigt ja nur auf ein einzelnes Element, das wiederum ein nächstes Element enthält (oder auch nicht, wenn es das Letzte ist).
 
"listenAnfang" ist vom Typ ListenElement und enthält eine Instanzvariable "naechster" die ebenfalls vom Typ ListenElement ist.

"listenAnfang.naechster" zeigt also entweder auf "null", wenn es kein nächstes Element gibt oder auf das nächste Element. Darauf könntest du dann mit "listenAnfang.naechster.naechster" zugreifen und auf das darauf Folgende dann mit "listenAnfang.naechster.naechster.naechster" usw.

Willst du die Daten dazu sehen, dann mit "listenAnfang.daten", bzw. "listenAnfang.naechster.daten" oder "listenAnfang.naechster.naechster.daten", usw.

"listenAnfang" ist der Ausgangspunkt für die gesamte Liste. Im Prinzip könntest du die Variable auch "meineListe" nennen.

Nochmal in einer aufgedröselten Form:
Java:
ListenElement erstes = listenAnfang;
ListenElement zweites = erstes.naechster;
ListenElement drittes = zweites.naechster;
ListenElement viertes = drittes.naechster;
// usw.
 
Zuletzt bearbeitet:

Zurück
Oben