Verkette Listen aus Algorithmen und Datenstrukturen mit C mit Generics

Dieses Beispiel ist das gleiche wie auf der vorherigen Seite, es wird nur mit Java Generics gearbeitet. Der Elementtyp wird bei allen Klassen als Typparameter mit angegeben. Dieses liefert an vielen Stellen zur Übersetzungszeit überprüfbare Typsicherheit, erfordert aber an manchen Stellen ineffizientere Objekterzeugung. Es kann nicht mehr mit einem Singleton als Endemarkierung gearbeitet werden.

mit Generics

Eine Klasse für verkettete Listen in Java. Im Gegensatz zu C, wo die Liste durch einen Zeigertyp repräsentiert wurde, die einzelnen Knoten durch einen record, wird hier nur eine Klasse benötigt, da die implizite Indirektstufe durch die Referenzen in den Variablen die Zeiger ersetzt.

Die leere Liste wird aber nicht durch die ungültige Referenz repräsentiert, da mit dieser keine Operationen ausgeführt werden können, es kann also keine Methode isEmpty auf die ungültige Referenz angewendet werden.

Aus diesem Grund wird immer ein Objekt für die leere Liste erzeugt. In diesem Objekt wird die next-Referenz auf null gesetzt. Dieses ist die Stelle, an der die Generics Lösung ineffizienter ist als die Lösung ohne Generics.

Compilation:
javac -source 1.7 -encoding iso-8859-1 LinkedList.java

Eine Klasse für Kommandos (--> Entwurfsmuster) zum Verarbeiten der Elemente in einem Container. Diese Klasse bietet eine allgemein einsetzbare Schnittstelle, nicht nur für die LinkedList Klasse.

Die Klasse wird mit zwei Typen parametrisiert, mit dem Elementtyp und mit dem Typ des zu berechnenden Resultats.

Die Klasse enthält eine Verarbeitungsroutine process zur Verarbeitung eines Elements. Diese Klasse ist abstrakt, d.h. sie legt nur eine Schnittstelle fest. Konkrete Klassen sind NoOfElements für die Berechnung der Anzahl der Elemente, IntegerSum zum Aufsummieren und ToString zum Konvertieren eines ganzen Containers in einen String.

Aufgerufen werden diese Kommandos aus der forall Rountine in der LinkedList Klasse. Dort ist also einmal festgelegt worden, wie der Container verkettete Liste zu durchlaufen ist, in diesem Fall mit einer einfachen while-Schleife.

Mit dieser einen Kontrollstruktur und den allgemein verwendbaren Kommandos lassen sich also z.B. die Längenberechnung, das Aufsummieren, die toString Konversion und viele andere Operationen erzeugen.

Die Kommandos, (die Klassen) NoOfElements, IntegerSum und ToString

Ein Testprogramm, noch unvollständig, das die LinkedList Klasse systematisch testet.

Compilation:
javac -source 1.7 -encoding iso-8859-1 LinkedListTest.java

Testlauf:
java LinkedListTest

das alte Testprogramm, das gar nicht mehr übersetzbar ist.

Compilation:
javac -source 1.7 -encoding iso-8859-1 LinkedListOldTest.java