Doppelt verkettete Liste, Java?
Wir haben in Informatik einfach und doppelt verkettete Listen gemacht. In den Folien gibt es auch ein Implementierungsbeispiel einer einfach verketteten Liste. Ich soll jetzt die gleichen bzw. ähnlichen Methoden für eine doppelt verkettete Liste programmieren.
Mein Problem ist, dass ich nicht verstehe, wie ich das machen soll. Ich habe mir verschiedene Beispiele angeguckt und versucht mich schlau zu lesen, aber die Beispiele schienen mir (jedenfalls bei der Implementierung) furchtbar umständlich.
Überall steht, dass sowohl auf den Nachfolger als auch auf den Vorgänger gezeigt wird. Ok, klingt logisch bei doppelt verkettet.
Aber wie sieht bei der Implementierung aus ?
Ich muss ein Element einfügen, entfernen und suchen.
2 Antworten
Am besten bei solche sachen: aufmalen.
Mal einfach mal drei Kästchen hintereinander auf, als ob du drei Zug-Waggons malen würdest.
Jetzt zeigt Waggon Nummer 1 auf Waggon Nummer 2 und umgekehrt. Dazu malst du da zwei Pfeile dran. Das machst du jetzt zwischen zwei und drei ebenfalls.
Wenn du jetzt noch die Pfeile gedanklich durch Referenzen ersetzt, hast du die Hälfte schon.
Beispiel Psudocode:
Waggon {
Waggon prev; // vorheriger Waggon
Waggon next; // nächste Waggon
//...
}
Zug {
Waggon lok // erster Waggon
void hintenAnkoppeln(Waggon waggon){
Zug z = lok;
while(z.hasNext()){
z = z.next();
}
z.insert(waggon);
}
boolean insert(Waggon waggon){...}
//...
}
In der Methode "insert(Waggon waggon)" muss nun ein Waggon auf die "next"-Referenz gesetzt werden und dessen "prev"-Refernz auf das Objekt, auf dem du insert aufrufst.
Wichtig: immer Skizzen machen!
LinkedLists sind relativ einfach umzusetzen (gibts sogar in Collections):
Zuerst mal brauchst du natürlich eine Klasse (die Liste) mit TypVariable, diese speichert das Element an der Stelle 0 und noch die größe (wahlweise auch das letzte Element).
Dann brauchst du noch eine private interne Klasse welche du zB Container nennst, diese hat auch eine TypVariable und speichert ganz simpel das Objekt, den Container davor und den Container danach.
Einfügen:
An der letzten Position ist das ganz einfach (da ist es nützlich die letzte zu haben), da musst du einfach nur an den letzten Container einen neuen hinzufügen, und musst natürlich den letzten Container ersetzen und die größe erhöhen. Selbes gilt für einfügen an der ersten Posititon.
Mittendrin ist auch nicht so schwierig, du ersetzt einfach die Verweise von den Containern davor und danach durch welche für den neuen Container und passt wieder die größe an.
Entfernen:
Das ist im Prinzip das gleiche wie Einfügen, bloß umgekehrt.
Suchen:
Auch relativ einfach, wenn du eine contains Methode haben willst dann einfach alle Container durchsuchen. Ein Objekt an einer bestimmten Position zu bekommen ist auch nicht gerade schwierig, man muss einfach nur solange den nächsten Container aufrufen bis man an einer bestimmten Position ist.
Falls du noch spezifischere Besipiele brauchst, kannst du ja wie schon gesagt einfach die LinkedList von Java selber anschauen, die ist jedenfalls ziemlich gut gemacht.