Java-Bibliothek für verkettete Listen

In den letzten Tagen war ich fleißig und habe wieder viel mit Java gearbeitet. Zum üben habe ich unter anderem eine Hierarchie mit verschiedenen Listen aufgebaut um verkettete Listen in Java zu implementieren. In diesen Listen könnt ihr beliebig viele Elemente beliebigen Typs hinzufügen, einfügen, löschen sowie zahlreiche weitere Operationen durchführen. Das Ganze könnt ihr auf GitHub anschauen. Meine Bibliothek ist in erster Linie zum testen und zum lernen gedacht, ich werde sie aber vermutlich auch in ein paar zukünftigen Projekten nutzen und weiter optimieren.

Meine Listen sind mit LinkedLists aus der Java-API vergleichbar. Meine Bibliothek stellt euch eine „SimpleList“ sowie eine „BidirectionalList“ zur Verfügung. Eine SimpleList solltet ihr unter keinen Umständen nutzen, das ist lediglich ein Beispiel um sich anzuschauen wie es geht. Diese Liste ist allerdings sehr langsam, da immer wieder von Anfang an alle Elemente iteriert werden müssen um das Listenende zu erreichen, erst dann können Elemente hinzugefügt werden. Hingegen ist meine BidirectionalList echt hübsch, da sie jederzeit den Listenanfang sowie ihr Ende kennt (die Referenzen zu den jeweiligen Listeneinträgen sind bekannt) sowie jedes Listenelement seine Vorgänger und Nachfolger kennt. So können recht schnell Elemente zum Listenende hinzugefügt werden oder an einem bestimmten Index Elemente eingefügt werden.

Wer wissen will wie ein Iterator in Java funktioniert um eine Datenstruktur für eine Foreach-Schleife zugänglich zu machen, der kann sich den Code ja auch mal anschauen. Dafür sind die Methoden iterator(), next() und hasNext() zuständig. Die Implementierung ist eigentlich sehr simpel.

Ich habe einen simplen Test geschrieben laut dem meine Implementierung nur ein paar ms langsamer ist als die Standardimplementierung LinkedList. Das ist ja schon mal ganz gut. Im Test ging es übrigens um das Einfügen von mehreren Zehntausend Elementen. Ganz cool ist, dass ihr mit meiner Implementierung zum Beispiel auch einen Stack realisieren könnt, hier für ist die pop()-Methode vorhanden. Alle Features findet ihr aufgelistet bei GitHub. Eine Beispielimplementierung von Türme von Hanoi mit Hilfe meiner Listen findet ihr hier.

Ein aktuelles JAR-Archiv zum importieren in eure Projekte könnt ihr von meinem Server downloaden. Wenn ihr Lust habt könnt ihr die Listen ja gerne mal testen und eventuell Feedback geben.

Philipp Schuster

Ich bin Philipp, studiere Informatik an der TU Dresden und arbeite als Werkstudent im Bereich Software-Entwicklung bei T-Systems MMS. Ich bin 22 Jahre alt und beschäftige mich in meiner Freizeit gerne mit meinem Blog, Programierung, Technik, aber auch mit Joggen und vielen anderen Dingen. Get To Know Me oder schreibt mich an!

Das könnte Dich auch interessieren …

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.