Abstrakte Datentypen

In Programmiersprachen können Operationen oder Algorithmen, die durch eine Folge von Anweisungen gegeben sind, in einer Prozedur isoliert und somit leicht ausgetauscht oder geändert werden, ohne daß andere Programmteile betroffen sind. Andere Programmteile wissen nicht, wie bestimmte Operationen realisiert sind, sie kennen nur den Aufruf der entsprechenden Prozedur. In ähnlicher Weise versucht man, die Organisation der Daten zu isolieren, so daß Änderungen an der Datenstruktur vorgenommen werden können ohne Änderungen ganzer Programme.

...Ein abstrakter Datentyp sagt nichts über seine Realisation durch eine bestimmte Datenstruktur in einem Programm aus. Wird die Implementation eines Datentyps durch eine bestimmte Datenstruktur in einem Programmteil isoliert, so kann diese Implementation später leicht geändert oder gegen eine andere ausgetauscht werden, ohne daß andere Programmteile, die nur die Definition des Datentyps verwenden, geändert werden müssen.

Abstrakte Datentypen

Das entscheidende Merkmal eines abstrakten Datentyps besteht darin, daß nichts, was sich außerhalb der Definitionen der Datenstruktur und der mit ihr operierenden Algorithmen befindet, auf irgendetwas Bezug nehmen darf, was sich innerhalb befindet, außer über Funktions- oder Prozeduraufrufe für die grundlegenden Operationen.

Der hauptsächliche Anlaß für die Entwicklung von abstrakten Datentypen bestand darin, daß ein Mechanismus für die Organisation umfangreicher Programme benötigt wurde. Durch abstrakte Datentypen ergibt sich ein Weg, um die Größe und Komplexität der Schnittstelle zwischen (potentiell komplizierten) Algorithmen und zugehörigen Datenstrukturen und (einer potentiell großen Anzahl) von Programmen, die die Algorithmen und Datenstrukturen verwenden, in Grenzen zu halten. Dadurch wird es leichter, das umfangreiche Programm zu verstehen, und es wird einfacher, die grundlegenden Algorithmen zu verändern oder zu verbessern.

Stapel und Schlangen sind klassische Beispiele von abstrakten Datentypen: Die meisten Programme brauchen sich nur mit ein paar wohldefinierten elementaren Operationen zu beschäftigen, aber nicht mit den Details von Verkettungen und Indizes.

Die Eigenschaften der abstrakten Datentypen (ADTs)

Universalität (implementation independence)

Der einmal entworfene und implementierte ADT kann ohne Probleme in jedes beliebige andere Programm einbezogen und dort benutzt werden. Unabdingbare Voraussetzung dafür ist jedoch eine

präzise Beschreibung (precise specifications)

Die Schnittstelle zwischen Implementation und Anwendung muß eindeutig und vollständig sein. Eine entsprechende Beschreibung unterstützt auch arbeitsteiliges Vorgehen, das vor allem bei umfangreichen Software-Projekten angebracht ist. So können etwa bestimmte Teams einen oder mehrere ADTs bereitsstellen, während gleichzeitig andere das eigentliche Programm, das sie anwendet, verfassen.

Einfachheit (simplicity)

Diese Eigenschaft ermöglicht es dem Anwender, sich auf das eigentliche Programmieren zu konzentrieren. Man betrachte dazu den ADT Feld, in Pascal bekanntlich implementiert als ARRAY. Wie bequem kann der Anwender doch damit hantieren, ohne sich um dessen Repräsentation und Verwaltung im Speicher kümmern zu müssen!

Verbergen von Information (information hiding)

Ein ADT soll als black-box aufgefaßt werden. Der Anwender kennt den Wertebereich und die Operationen, die darauf definiert sind; wie die Daten innen abgebildet und verarbeitet werden, brauchen ihn nicht zu interessieren und sollen es auch nicht. Diese Schnittstelle soll als eine hermetische Grenze aufgefaßt werden. Der Anwender soll sehr genau wissen, was ein ADT tut, aber keinesfalls, wie er es tut. Das stellt auch einen gewissen Schutz dar:

Geschütztheit (integrity)

Zugriffe, vor allen Dingen verändernde Zugriffe auf Daten eines ADT geschehen grundsätzlich sehr kontrolliert, indem sie nur über die entsprechenden Operationen möglich sind. Der Anwender kann in die interne Struktur der Daten nicht eingreifen, da sie ihm verborgen ist. Die Gefahr, Daten ungewollt zu löschen bzw. zu verändern oder durch Systemabsturz zu verlieren, ist durchaus herabgesetzt. Auch viele Programmierfehler sind durch die Datenintegrität nicht mehr möglich.

Modularität (modularity)

Der ADT verkörpert sehr klar das modulare Prinzip. Das erlaubt übersichtliches und damit sicheres Programmieren und leichten Austausch von Programmteilen. Bei der Fehlersuche können einzelne Module, die ja eindeutige Schnittstellen und klar formulierten Input und Output haben, sehr isoliert betrachtet werden. Viele Verbesserungen können über ADTs nachträglich ohne die geringste Änderung in sämtlichen Umgebungs- bzw. Anwendungsprogrammen übernommen werden, da in einem solchen Falle ja nur das Wie, nicht aber das Was geändert wird.