Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Abstrakter Datentyp

Abstrakter Datentyp

ADT bedeutet abstrakter Datentyp. Man fasst Daten und Operationen auf ihnen in einem ADT zusammen. Dieses Konzept ist von der objektorientieren Programmierung bekannt. Ein ADT entspricht hier einer Klasse, welche die Operationen implementiert, die auf einer Datenstruktur ausgeführt werden können. Die Operationen entsprechen hier dem Interface. Die Datentypen, die wir in dieser Vorlesung behandeln werden, sind in der Java Collection API bereits konkret implementiert. Die Collection API bietet diese Operationen über Interfaces an. So gibt es ein Interface List für Listen, ein Interface Set für Mengen und ein Interface Map für die Zuordnung zwischen Schlüsseln und zugehörigen Werten. Die eigentliche Datenstruktur ist dabei die Implementierung in einer Klasse. Die Idee ist demnach, dass wir durch die Definition eines Interfaces Operationen vorgeben und verschiedene Implementierungen von Datentypen realisieren können, welche unterschiedliche Aspekte beleuchten. Wir werden heute die Operationen für eine Liste sehen. Dann werden wir unterschiedliche Arten von Listen kennenlernen, welche diese Operationen implementieren.

ADT abstrakter Datentyp

$\longrightarrow$ Daten und Operationen auf dem ADT gehören zusammen

$\underbrace {Datenstruktur} _{Implementierung}{\text{ }}\underbrace {Operationen} _{Interface}$

Generell kann man, wie aus der Collection API bereits bekannt, in jeder Speicherstruktur jeden beliebigen Datentypen verwalten. Wir werden hier der Einfachheit halber jeweils nur Integer Werte in den Datenstrukturen ablegen. Man kann jedoch wegen der in Java verwendeten generischen Implementierung der Datenstrukturen beliebige Objekte typensicher in ihnen ablegen. Betrachten wir nun die Datentyp Liste: