Frage von SuperSocke2, 42

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.

Antwort
von androhecker, 31

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.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten