Abstrakter Datentyp (ADT) Liste

Definition (abstrakter Datentyp):
Bei der Spezifikation werden Datenobjekte und Operationen ohne Bezugnahme auf ihre interne Struktur beschrieben. Der Zugriff auf den ADT erfolgt nur über diese vereinbarten Operationen (Zugriffsoperationen). Der ADT wird auf der Grundlage eines Modells definiert und implementiert.

Eigenschaften von Abstrakten Datentypen

  1. ein ADT ist universal - einmal entworfen und implementiert kann er in jedes beliebige Programm einbezogen werden.
  2. ein ADT ist einfach - bei der Anwendung muss man sich nicht um seine interne Realisation kümmern.
  3. ein ADT ist gekapselt - der Anwender sollte wissen, was der ADT tut, aber nicht, wie er es tut.
  4. ein ADT ist geschützt - der Anwender kann in die interne Struktur der Daten nicht eingreifen.
  5. ein ADT ist modular - er stellt Grundfunktionen zur Verfügung, die von anderen genutzt werden können.
  6. ein ADT muss präzise sein - seine Beschreibung sollte dem entsprechen, was er wirklich tut.

Spezifikation des abstrakten Datentyps "Liste"
(ADT Liste)

(A) Wertebereich:

Eine (einfach verkettete) Liste besteht aus Elementen, die in linearer Folge angeordnet sind. Eine solche Liste kann nur von vorn nach hinten durchlaufen werden. Ist die Liste nicht leer, dann gibt es das erste Element, das letzte Element und ein aktuelles Element. Enthält eine Liste genau ein Element, dann ist dieses Element sowohl aktuelles, erstes als auch letztes Element. Für jedes Element einer Liste, mit Ausnahme des letzten Elementes, gibt es das nächste Element.

(B) Operationen:

  1. Operation: Erzeugen
    Eine leere Liste wird angelegt. Diese Operation ist Voraussetzung für alle anderen Operationen.
    Die Java-Programmierer benutzen statt dessen wie üblich:
    adtListe NameMeinerListe = new adtListe;
  2. Operation: EinfuegenElement
    Ein Element wird vor dem aktuellen Element eingefügt. Wird diese Operation auf eine leere Liste angewandt, dann enthält die Liste anschließend genau ein Element. Das neue Element wird zum aktuellen Element.
  3. Operation: AnhaengenElement
    Ein Element wird nach dem letzten Element angefügt. Wird diese Operation auf eine leere Liste angewandt, dann enthält die Liste anschließend genau ein Element. Das neue Element wird zum aktuellen Element.
  4. Operation: LoeschenElement
    Das aktuelle Element wird gelöscht. Das erste Element wird dann zum aktuellen Element. Ist die Liste leer, dann passiert nichts. Enthält die Liste genau ein Element, dann wird dieses gelöscht; dadurch entsteht eine leere Liste.
  5. Operation: GeheErstes
    Das erste Element wird zum aktuellen Element. Ist die Liste leer, dann passiert nichts.
  6. Operation: GeheLetztes
    Das letzte Element wird zum aktuellen Element. Ist die Liste leer, dann passiert nichts.
  7. Operation: GeheNaechstes
    Das nächste Element wird zum aktuellen Element. Diese Operation darf nicht angewandt werden, wenn das letzte Element aktuelles Element ist. Ist die Liste leer, dann passiert nichts.
  8. Operation: HoleEintrag
    Der Inhalt des aktuellen Elementes wird bereit gestellt. Das aktuelle Element bleibt aktuelles Element. Diese Operation darf nicht angewandt werden, wenn die Liste leer ist.
  9. Operation: SchreibeEintrag
    Der Inhalt des aktuellen Elementes wird überschrieben. Das aktuelle Element bleibt aktuelles Element. Diese Operation darf nicht angewandt werden, wenn die Liste leer ist.
  10. Operation: ListeLeer
    Diese Operation liefert den Wert TRUE, wenn die Liste leer ist. Ansonsten liefert sie den Wert FALSE.
  11. Operation: ListenEnde
    Diese Operation liefert den Wert TRUE, wenn das letzte Element aktuelles Element ist. TRUE wird auch geliefert, wenn die Liste leer ist. Ansonsten liefert die Operation den Wert FALSE.

Die Dateien des ADT Liste im Zip-Format: Download
(fehlerbereinigte Version vom 13.04.2006)