verkettete Listen - Klasse Knoten

[Katzenstreik]

Hallo!

ich habe ein Verständnisproblem was die Klasse Knoten bei bspw. einer einfach verketteten Liste betrifft:

meine Klasse Knoten sieht wie folgt aus:

class Knoten {
  public vergleichbar Schluessel;
  public String text;
  public Knoten naechster
  public Knoten (vergleichbar schluessel, String text)
      {
        this.schluessel = schluessel;
        this.text = text;
    }
}

jetzt möchte ich z.B. einen neuen Knoten in meine Liste einfügen:

class Realisierung
//...
while (ticker.naechster != null)
   ticker = ticker.naechster;
ticker.naechster = neuerKnoten;
//...

Nun zu meiner Frage: Wo wird festgelegt das Knoten naechster; wirklich der nächste Knoten in meiner Liste ist? Also woher weiß meine Klasse Realisierung, dass wenn ticker.naechster angesprochen wird er den nächsten Knoten nach ticker ansprechen soll???

Was seh ich nicht oder was seh ich falsch?

Danke für eure Antworten

 

[Landei]

So ganz verstehe ich deine Frage nicht: Jeder Knoten hat genau einen "nächsten" Knoten, und dieser wieder u.s.w. (außer dem letzten, der zeigt auf null), wie Hinweise bei einer Schnitzeljagd. Das sieht etwa so aus (O ist der Knoten, -> die Referenz auf den nächsten):
O-> O-> O-> null
Mit deinem Code suchst du das letzte O (dessen -> auf null zeigst) und fügst einen neuen Knoten Ö da an, wo vorher null war:
O-> O-> O-> Ö-> null
Ganz einfach, und der "Weg" ist immer eindeutig.

 

[XHelp]

Weil du immer ans Ende anfügst. Wenn du also das Ende erreicht hast (kein Nachfolger -> naechster == null), dann packst du dein neues Element dahin.
P.S.
"public vergleichbar Schluessel;" ganz verkehrt: Klassennamen soltlen mit Großbuchstaben anfangen, Variablen mit Kleinbuchstaben. Außerdem ist der Name "Vergleichbar" nichtssagend. Genau so wie die Klasse "Realisierung".

 

[Katzenstreik]

genau das ist ja mein Problem. Ich verstehe nicht, wieso er weiß, dass er zum nächsten Knoten gehen soll. Ich würde es verstehen, wenn irgendwo gesagt wird Knoten != null (also schon eienr vorhanden) dann gehe zu Knoten+1 in der Liste. Aber nirgendwo wird eine solche Operation ausgeführt?!?

zu XHelp:

du hast recht, aber das ist nur ein Ausschnitt meines Codes. Der Rest ist aber für meine Frage nicht relevant.

 

[XHelp]

A,B,C,D... sind Knoten nicht du nacheinander hinzufügst:
A -> null
du willst B anhängen. Also suchst du einen Knoten, der beim nachfolger "null" hat (Ende der Liste). Es ist also A. Bei A setzt du B als nachfolger. Und B hat von vorne rein "null" als nachfolger. Die neue Liste sieht so aus:
A -> B -> null
Jetzt willst du C dran packen. Suchst wieder den letzten Knoten, diesmal ist es B. Der Nachfolger von B wird C:
A -> B -> C -> null
usw...

 

[Katzenstreik]

hmm..

also wenn A mein erster Knoten ist, wieso ist Knoten.naechster dann B? Wer sagt das "naechster" bestimmt das B auf A folgt? Ich hab doch nirgendwo festgelegt das die Variable naechster der Nachfolger vom ersten Knoten ist.

 

[fastjack]

Schreib mal die while-Schleife anders:

while (ticker.naechster != null) { // hier wird geprüft, ob es zum aktuellen ticker einen Nachfolger gibt
   ticker = ticker.naechster; // wenn ja, soll der aktuelle ticker auf seinen Nachfolger zeigen (dein: knoten+1)
}
ticker.naechster = neuerKnoten; // wenn nein, wird der Nachfolger des aktuellen tickers auf den neuen Knoten gesetzt, sprich die liste um ein element erweitert.

Bei diesen Aufgaben ist es sinnvoll, sich die Knoten als Kreise aufs Papier zu malen und die Zeiger durch Pfeile darzustellen. Am besten mit Bleistift Irgendwann werden nämlich doppelt verkettete Listen, vor- und zurückgehen, vorne einfügen, mittendrin einfügen etc. kommen. Dadurch hast Du die aktuelle "Lage" und Zeiger immer auf dem Papier. Und wirst auch selten einen Zeiger vergessen.

 

[XHelp]

Schau dir doch Zeile 5 deiner Realisierungsklasse an, da steht es doch :bahnhof:

 

[Andi_CH]

hmm..

also wenn A mein erster Knoten ist, wieso ist Knoten.naechster dann B? Wer sagt das "naechster" bestimmt das B auf A folgt? Ich hab doch nirgendwo festgelegt das die Variable naechster der Nachfolger vom ersten Knoten ist.

a.naechster ist null und gar nichts anderes ;-)
Dem kannst du dann zuweisen was du willst. Was die Variable für eine Bedeutung hat definierst nur du!

Es macht natürlich Sinn, dass eine variable die "naechster" heisst auch auf den nächsten Knoten zeigt.

Knoten a = new Knoten();
a.text = "A";
// a.naechster ist null und gar nichts anderes ;-)
Knoten b = new Knoten();
b.text="B";
a.naechster = b;
// a.naechster zeigt jetzt auf den neuen Knoten
b = new Knoten();
b.text = "C";
// Der Knoten "B" ist jetzt nur noch über a.naechster greifbar
// a.naechster.naechster ist null
.........

 

[Katzenstreik]

a.naechster ist null und gar nichts anderes ;-)

wenn a.naechster immer null ist bevor ich ihm was anderes zuweise, dann macht meine while schleife ja gar keinen sinn mehr.

Weil ich bevor ich mit der while schleife beginne ich der variablen naechster nichts zugewiesen habe?!?

Wenn ich dann Werte eintrage, dann kommt naechster ja nie über null hinaus, weil am anfang gefragt wird ticker.naechster != null. und das trifft immer zu, weil die schleife doch immer am anfang der liste beginnt.

Edit: Wo weise ich der variable naechster denn das erste mal etwas zu?

 

[ARadauer]

Ich würde es verstehen, wenn irgendwo gesagt wird Knoten != null (also schon eienr vorhanden) dann gehe zu Knoten+1 in der Liste. Aber nirgendwo wird eine solche Operation ausgeführt?!?

hä??

while (ticker.naechster != null)
   ticker = ticker.naechster;

machst du ja eh... man sollte den code auch lesen den man postet ;-)

 

[Katzenstreik]

aber ticker.naechster wird doch erst zu ticker, nachdem die Bedingung in der while schleife erfüllt ist. Die while schleife prüft ob ticker.naechster nciht null ist, beim ersten durchlauf ist ticker.naechster doch immer null?!? (Weil ich vorher naechster keinen wert zugewiesen habe)

 

[Katzenstreik]

Keiner mehr eine Idee oder besser einen Erklärungsansatz?

 

[XHelp]

Und du hast bereits, wie mehrmals abgedeutet, alles auf einem Stück Papier nachgespielt? Alles was in der Schleife passiert, wie so eine Liste aussieht etc. Wenn ja - was verstehst du denn nicht?

 

[Katzenstreik]

ich verstehe nur nicht, welchen Wert mein Knoten naechster kurz vor der while schleife hat und wie er diesen bekommt, wenn ich bspw. annehme ich habe bereits drei Elemente in meiner Liste.

 

[XHelp]

Davor wird wohl irgendwo stehen:

Knoten ticker = ersterKnoten;

Dem entsprechen zeigt vor der Schleife "naechster" entweder auf dein 2. Element oder es ist null.

 

[Katzenstreik]

genau,..

aber wieso weiß ticker, dass wenn ich ihm sage ticker.naechster, das das darauffolgende element gemeint ist? Der Variable "naechster" muss doch irgendwo gesagt werden, dass es auf den nächsten Knoten verweist. Ich verstehe und sehe nicht wo das passiert.

 

[XHelp]

Steht doch in Zeile 5 da...
Wie gesagt, mach das auf Papier wenn du es sonst nicht verstehst.

 

[Katzenstreik]

ich glaube ich habs verstanden. Ich habs nochmal ausführlich gemacht, danke für den tipp und das Durchhaltevermögen.

 

[Andi_CH]

EDIT: Das hat sich ja erledigt - ich hatte nur ein update-Problem im Browser