Einfach verkettete Liste

[deeP]

Hallo,
ich bin mehr als nur ein Anfänger. Ich versuche gerade für die kommende Informatik Klausur (Einführung in die Informatik für Ingenieure), einfach verkettete Listen zu verstehen.

Aber ganz ehrlich ich versteh nur Bahnhof. 90 Prozent der Vorlesung habe ich verstanden. Jetzt kommt sowas und ich steh sowas von auf den Schlauch.


Also so viel habe ich in den 2 Stunden jetzt verstanden:

Es gibt ein Kopf das ist das Einzige Element ohne Vorgänger. und ein Null. Das letzte Element in der Kette.

Was ist aber bitte "weiter"?

ich mein zB. habe ich folgenden Methode zum einfügen von Elemente ganz vorne der Kette:

[HIGHLIGHT="Java"]public void einfuegenVorn(int k) {
Element e= new Element(k);
e.weiter=Kopf(k);
Kopf=e;
}[/HIGHLIGHT]
Also ich versuche gerade die Methode zu verstehen aber klappt irgendwie nicht...

Also es wird ein Objekt der klasse Element erzeugt dieses heisst e. Es wird eine Zahl übergeben sagen wir mal die 7.

Was heisst nun die 2. Zeile? e.weiter = kopf(k) ???

Die dritte Zeile bedeutet ja der Kopf zeigt auf das objekt e. Aber die 2. versteh ich überhaupt nicht. Was soll dieses weiter? Und Kopf "in Klammern k" ?

Ich hoffe ihr könnt mir helfen. Für euch ist das Kindergarten aber für mich sehr wichtig wegen Klausur.

Ich hoffe ihr könnt mir helfen

Lieben gruß

deeP

 

[fjord]

Falls du es noch nicht getan hast, guck dir mal den wiki Artikel zu Listen an.

Einfach gesagt hat jedes Element der Liste, bis auf das letzte, einen Verweis auf seinen Nachfolger. Dieser Verweis ist in deinem Beispiel e.weiter. Wenn du ein neues Element in der Liste vorne einfügst, dann wird das ehemals 1. Element zum 2. Element. Also muss der neue Kopf einen Verweis auf den alten Kopf haben.

Bist du sicher, dass die Zeile

e.weiter=Kopf(k);

ist? Oder ist es eher

e.weiter=Kopf

?

 

[ARadauer]

das ganze mit papier und bleistift mal auszuprobieren ist sehr hilfreich.

mal dir ein paar Element Knoten auf, Kopf ist der erste, jeder Knoten hat ein weiter das auf den nächsten zeigt...
so jetzt vorne einfügen...
neuen knoten machen ... Element e= new Element(k);
das weiter des neuen knoten auf den akutellen kopf setzen ..e.weiter=Kopf(k);
und kopf muss jetzt auf den neuen knoten zeigen.. Kopf=e;

aufmalen hilft...

 

[Marco13]

Aufmalen.... oder basteln Wenn man die Referenzen über Bindfäden modelliert, versteht man vielleicht eher, warum man manche Sachen so macht, wie man sie macht: Wenn man die Bindfäden losläßt sind sie weg...

 

[ARadauer]

cool! basteln... daran hab ich noch gar nie gedacht, das wär mal was für ein gutes video tutorial ;-)

 

[deeP]

Vielen vielen Dank. Jetzt bin ich schon mal um 100 prozent schlauer. Also

bei mir im Heft steht e.weiter=kopf(k);

vllt habe ich es falsch abgeschrieben und es stand e.weiter=kopf; was für mich auch mehr sinn ergeben würde.

Also ich stelle mir das jetzt so vor . Hoert sich lustig an aber naja... Also wir haben den Kopf der zeigt auf Null. Kein Knoten ist vorhanden. Nun rufe ich die Methode einfügenVorn auf: ich erstelle ein neues objekt der Klasse Element sagen wir mal die 7. Der weiterzeiger zeigt auf Kopf also übernimmt das neue Element den weiter Zeiger des Kopfes. Nun ist kann die Kette nicht unterbrochen werden und der Kopf "schwingt sich rüber" und koppelt sich an die 7 .

Also so wie ich das verstanden habe ist Kopf immer das erste Element. Was mir nicht ganz klar ist, ist immer noch diese Zeile. e.weiter=Kopf; Also heisst das, dass der weiter Zeiger den weiter zeiger von Kopf übernimmt, bzw seinen Zeiger übernimmt?


Lieben Gruß

deeP

 

[Marco13]

Also ich stelle mir das jetzt so vor . Hoert sich lustig an aber naja... Also wir haben den Kopf der zeigt auf Null. Kein Knoten ist vorhanden. Nun rufe ich die Methode einfügenVorn auf: ich erstelle ein neues objekt der Klasse Element sagen wir mal die 7. Der weiterzeiger zeigt auf Kopf also übernimmt das neue Element den weiter Zeiger des Kopfes. Nun ist kann die Kette nicht unterbrochen werden und der Kopf "schwingt sich rüber" und koppelt sich an die 7 .

Hört sich eher kompliziert als lustig an.

Ich will zwar nicht wissen, wie oft dieser Sachverhalt schon aufgezeichnet wurde (von dir vermutlich noch nicht, sonst würdest du nicht mehr nachfragen....) aber... gut

Ausgangssituation:

             ______      ______
            |  ... |--->|  ... |--->null
            |______|    |______|    
             Kopf






Nach: Element e = new Element(k);

             ______      ______
            |  ... |--->|  ... |--->null
            |______|    |______|    
             Kopf


 ______     
|  k   |--->null
|______|    





Nach e.weiter=Kopf;


 ______      ______      ______
|  k   |--->|  ... |--->|  ... |--->null
|______|    |______|    |______|    
              Kopf




Nach Kopf=e;


 ______      ______      ______
|  k   |--->|  ... |--->|  ... |--->null
|______|    |______|    |______|    
  Kopf

Oder konkret in bezug auf die Frage:
Was mir nicht ganz klar ist, ist immer noch diese Zeile. e.weiter=Kopf; Also heisst das, dass der weiter Zeiger den weiter zeiger von Kopf übernimmt, bzw seinen Zeiger übernimmt?
Nein. Das bewirkt, dass der "weiter"-Zeiger danach auf das Zeigt, was bisher der Kopf war. Wenn VOR dem Kopf etwas eingefügt wird, ist das, was HINTER diesem Element kommt....? Der Kopf, ja. Danach muss man mit
Kopf=e;
noch sagen, dass nas neueste (vorderste) Element in Zukunft der Kopf sein soll.


Zur Auflockerung nochmal die Tragödie der verketteten Listen:

 

[Leroy42]

Was mir nicht ganz klar ist, ist immer noch diese Zeile. e.weiter=Kopf; Also heisst das, dass der weiter Zeiger den weiter zeiger von Kopf übernimmt, bzw seinen Zeiger übernimmt?

Kopf ist ja am Anfang (also vor dem 1. Einfügen) NULL; dieser Wert (NULL) wird
jetzt dem weiter-Zeiger des neuen Elements zugewiesen.

Mit Kopf = e wird nun das neue Element zum Kopf.

Beim erneuten Einfügen bewirkt e.weiter=Kopf, daß e.weiter hier auf das
soeben eingefügte Element verweist (also dem neuen Kopf)....

 

[Leroy42]

@Marco13

Ich war jetzt zwar zu langsam, aber dafür habe ich
das nicht so schön aufgezeichnet wie du!

 

[deeP]

Gut danke sehr.

Noch eine Frage :

Die Augangssituation wenn ich kein Element in der Liste habe ist doch so:


----
|Kopf | ---->|Null| . Nun einfügenVorn(7);
----

|7| -> |Kopf| - > |Null| . (e.weiter=Kopf) , Nun Kopf=e;

| 7 | -------> | | -----> Null.Jetzt meine Frage was steht im Mittleren Knoten
| Kopf | ? Für Kopf wurde doch kein Wert gespeichert?
Ist dieser Knoten leer?

Ps: Ich hoffe ich strapazier euch nicht zu sehr...

Lieben Gruß

deeP


Also letzte gezeichnete Zeile soll heissen 7 ist der Kopf. Keine Ahnung warum der das so komisch darstellt bei mir im edit menü sah es anders aus

 

[0x7F800000]

Wieso? Im Kopf bleibt einfach nur das stehen, was da vorher schon war.
Initialisieren sollte man das wohl mit null. Wenn man dann zB. elemente 1,2,3 einfügt sieht es dann so aus:

Initialisiert: Kopf=null
1 Hinzufügen: Kopf=1->null
2 Hinzufpgen: Kopf=2->1->null
3 Hinzufügen: Kopf=3->2->1->null

und so weiter...

Diese Implementierung finde ich eh unschön und unpraktisch. Es ist viel besser, wenn man den Kopf als ein Dummy-Element ganz vorne abspeichert, dann hat man weniger stress beim iterieren, braucht keine Fallunterscheidungen und sowas. Dann hat man im Kopf eben einfach immer "irgendwas" (sagen wir mal so ein unbestimtes #-dings), was aber nie gebraucht wird, dann sieht's nämlich so aus:

Initialisiert: #->null
1 Hinzufügen: #->1->null
2 Hinzufügen: #->2->1->null
3 Hinzufügen: #->3->2->1->null

dann braucht man sich zB bei solchen sachen wie hasNext() und next() keine Sorgen über die spezialfälle zu machen. Aber das war jetzt wohl eher verwirrend? Also, mit bleistiften zeichnen & selbst implementieren ist eine ziemlich gute Idee.

 

[deeP]

Danke euch.

Ich bin jetzt einigermaßen weiter gekommen und habe die Aufgabe eine Methode anzahl zu erstellen, die die Anzahl der Elemente der liste zurück gibt.Falls sie leer ist, so soll ich false returnen wenn nicht die anzahl.

Ich habe mir folgendes überlegt:

[HIGHLIGHT="Java"]public int anzahl() {
int n=0;
if(Kopf!=null) {
int n=1;
while(e.weiter!=null) {
n++;
e=e.weiter;
}
return n;
}
else {
return n;
}
}[/HIGHLIGHT]
was meint ihr klappt das?

Lieben gruß



Ergänzung ah ich glaube ich habe einen fehler gemacht und zwar muss er ja wissen wo er anfäng deswegen muss ich glaube ich noch

e=Kopf setzen oder?

 

[0x7F800000]

Falls sie leer ist, so soll ich false returnen wenn nicht die anzahl.

Äääääh? Hast du selbst verstanden, was du da eben gesagt hast? Ich hab's jedenfalls nicht verstanden. 0 ist imho auch eine recht schöne ganze Zahl.

Ich habe mir folgendes überlegt:

public int anzahl() {
   int n=0;
   if(Kopf!=null) {
       int n=1;
       while(e.weiter!=null) {
         n++;
         e=e.weiter;
       }
     return n;
    }
    else { 
      return n;
    }
}

was meint ihr klappt das?

Joah, sieht im prinzip ganz gut aus, allerdings ist das eine ziemlich lahme Lösung, weil du ja jedes mal die gesamte liste durchlaufen musst, bei einer Liste mit 123131323123 einträgen dauert das dann erstmal zwei Tage...
Normalerweise wird einfach eine member-variable "size" angelegt, die anfangs mit 0 initialisiert wird, und jedes mal wenn was hinzugefügt wird, inkrementiert man die variable, wenn etwas gelöscht wird, macht man sie wieder kleiner. Dann brauchst du bei dieser methode nur diese zahl zurückzugeben, das geschieht sofort mit konstanten Aufwand.

 

[deeP]

klar nicht return n, sondern return false meine ich natürlich.

Ja ich glaube für uns ingenieure reicht das . size hatten wir auch gar nicht .

Musste ich eigentlich noch e=Kopf; setzen. damit er weiß, wo er anfangen soll?


lg

 

[Marco13]

Ich glaube es ging gerade darum, sich so durch diese Liste zu hangeln - Effizienz hin oder her.

Aus rein akademischen Gründen noch die rekursive Variante:

int anzahl()
{ 
    return anzahl(kopf);
}

private int anzahl(Knoten k)
{
    if (k==null) return 0;
    return 1+anzahl(k.weiter);
}

 

[0x7F800000]

return false meine ich natürlich

Geht der Salat wieder los...

 

[deeP]

was soll da denn falsch sein? Die Liste ist leer --> also returne ich false. wenn nicht returne ich das n aus der schleife oder bin ich total durch den wind?

 

[0x7F800000]

okay, na dann leg los. Wenn du Integer und Booleans zu irgendeinem sinnvollen Typ gewrappt hast, und dir außerdem irgendeine halbwegs plausible Begründung für diese sinnfreie Vorgehensweise überlegt hast, kannst du hier gerne mal die methode posten, ich will auch mal sehen, wie man eine size()-methode einer collection auf 500 Zeilen Code verteilen kann^^

 

[deeP]

ok stimmt ist ja ein boolean und kein int ,. Mein Kopf ist schon total durch einander brauche mal ne pause

 

[deeP]

Hallo Leute,
ich habe mache gerade noch eine Aufgabe und zwar soll follgende Methode schreiben:

"letztesElement" , diese gibt das letzte Element der Liste zurück. Es soll NICHT der Wert sondern die Referenz auf das Element zurückgegeben werden. Ist die Liste leer, so wird null zurückgegeben.

Jetzt meine Frage. Wie soll ich das denn machen, dass eine Referenz zurück gegeben wird?


ich mein sonst war es ja so :

public int/double xY() gibt wert zurück
public boolean xY() gib boolean zurück usw

wie geht das nun mit der Referenz?


lieben Gruß

 

[deeP]

ok ich glaube ich habe es verstanden einfach den Klassen namen vor den Methoden namen. Ich versuchs mal:

[HIGHLIGHT="Java"]public Element letztesElement() {
if(Kopf!=null) {
Element e=Kopf;
while(e.weiter!=null) {
e=e.weiter;
}
return e;
}

}[/HIGHLIGHT]