Home > Informatik > Stufe Q1 > ADTs

14.6 Der ADT List

Allgemeines - Abstrakte Datentypen - Stack - Queue - Dictionary - List

Allgemeines

Bei dem ADT Liste werde ich mich mal komplett an die Vorgaben zum Zentralabitur Informatik in NRW halten. Zunächst einmal zitiere ich wortgetreu die Beschreibung der "generischen Klasse List" aus der Aufgabe IF GK HT 1 (GG), die im Frühjahr 2023 im Zentralabitur NRW gestellt wurde:

"Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste können durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden."

Als Nächstes schauen wir uns mal die offizielle Dokumentation der Klasse List an (Version 2023):

Dokumentation der Klasse List, Teil 1 Dokumentation der Klasse List, Teil 2

Erläuterungen

Wir wollen diese vielen Operationen jetzt mal veranschaulichen. Dazu malen wir uns mal eine einfache Liste auf. Die Listen-Elemente sollen jetzt nur int-Zahlen sein; in Wirklichkeit kann der ADT List auch Objekte einer Klasse speichern.

Die offizielle NRW-Klasse List<ContentType> kann allerdings keine primitiven Datentypen wie int oder double als Elementtypen verwenden, sondern nur Objekttypen. Will man ganze Zahlen oder Kommazahlen in einer solchen Liste speichern, verwendet man daher die Wrapper-Klassen Integer bzw. Double. Java kann die entsprechenden Zahlenwerte automatisch in Objekte dieser Klassen umwandeln (Autoboxing).

Veranschaulichung der Listen-Operationen

Implementation

Wir betrachten nun eine statische Implementation des ADT List, die unter Verwendung eines Arrays erstellt wurde. Auf der folgenden Vertiefungsseite wird zunächst die komplette Implementation vorgestellt. Den Quelltext können Sie sich über die Zwischenablage herunterladen, außerdem finden Sie Links auf die Quelltexte der Klassen.

Eine alternative Implementation der Klasse List mit Hilfe von Zeigertypen wird in einer späteren Folge dieses Kurses erläutert. Auch die Klasse List, die von Java zur Verfügung gestellt wird, ist dynamisch implementiert worden und nicht statisch.