Der ADT List
In der Folge 14 hatten wir Abstrakte Datentypen kennengelernt, unter anderem den durchaus auch für das Abitur in NRW sehr wichtigen ADT List. Wir hatten den ADT List dann mit Hilfe eines Array implementiert.
Wir wollen in diesem Abschnitt nun den ADT List mit Hilfe von Referenzen implementieren. Wenn Sie die Methoden der Klasse List nicht mehr in Erinnerung haben, gehen Sie doch bitte auf die entsprechende Seite in Folge 14.
Betrachten wir erst mal ein Bild:
Um mit der dynamischen Liste vernünftig arbeiten zu können, benötigen wir drei Referenzen. Der Zeiger first zeigt auf das erste Listen-Element, der Zeiger last auf das letzte Listen-Element, und der Zeiger act auf das aktuelle Listen-Element, falls überhaupt eines vorhanden ist. Eine Liste muss ja laut Definition nicht unbedingt ein aktuelles Element haben. Um dies festzustellen, gibt es ja die sondierende Methode hasAccess, welche false zurückliefert, wenn kein aktuelles Element existiert.
Hier haben wir drei weitere Bilder, die Listenoperationen zeigen. Durch die Operation toFirst() wird der first-Zeiger auf das erste Listen-Element gesetzt, entsprechendes gilt für die Operation toLast(), die hier nicht gezeigt wurde.
Die Operation Next() bewegt den act-Zeiger auf das nächste Listen-Element, sofern überhaupt noch ein solches Element rechts neben dem aktuellen Element existiert.
Die Operation Insert() schließlich schiebt ein neues Listen-Element vor das aktuelle Listen-Element, falls ein solches existiert.
Über die genaue Arbeitsweise der (anderen) Operationen können Sie sich in Folge 14.6 informieren, in der der ADT List ausführlich dargestellt wird.
Implementation in Java
Betrachten wir nun eine Implementierung des ADT List in Java, die Gebrauch von Referenzen macht. Da der Quelltext mit den notwendigen Erläuterungen sehr lang ist, habe ich ihn in eine eigene Datei ausgelagert.
Zum Vergleich stelle ich hier auch den offiziellen Quelltext der Klasse List zur Verfügung, der im Jahre 2015 von der "Qualitaets- und UnterstuetzungsAgentur - Landesinstitut fuer Schule" in NRW veröffentlicht wurde.