2. Abstrakte Datentypen (ADT) vs Datenstrukturen#
Jedes Computerprogramm speichert und verarbeitet Daten. Um diese Daten effizient zu verwalten, müssen sie strukturiert organisiert werden. Hier kommen Abstrakte Datentypen (ADT) und Datenstrukturen ins Spiel.
Ein Abstrakter Datentyp (ADT) definiert ein Interface, also eine Sammlung von Operationen, die auf den Daten ausgeführt werden können – zum Beispiel das Hinzufügen, Entfernen oder Abrufen von Elementen. Der ADT beschreibt, was diese Operationen leisten, ohne jedoch festzulegen, wie sie intern umgesetzt werden. Diese Details übernimmt die Datenstruktur, die dafür sorgt, dass die Daten optimal im Speicher organisiert sind und die Operationen effizient ausgeführt werden können.
In diesem Abschnitt lernst du, wie abstrakte Datentypen wie Listen, Stapel, Warteschlangen und assoziative Arrays funktionieren und welche Datenstrukturen man nutzt, um sie zu implementieren. Verschiedene Datenstrukturen wie Arrays, verkettete Listen oder Bäume können denselben ADT auf unterschiedliche Weise implementieren. Jede dieser Datenstrukturen hat spezifische Vor- und Nachteile, je nach Anwendungsfall.
2.1. Vier wichtige abstrakte Datentypen#
In der Informatik gibt es viele abstrakte Datentypen (ADT) mit unterschiedlichen Anwendungszwecken. Jeder ADT definiert, was wir mit Daten tun können, ohne festzulegen, wie dies genau implementiert wird. Hier lernst du vier der wichtigsten abstrakten Datentypen kennen: Listen, Stapel, Warteschlangen und assoziative Arrays. In den späteren Kapiteln lernst du dann, sie in UMLzu modellieren und die einzelnen Operationen zu implementieren.
2.1.1. Listen#
Eine Liste ist eine geordnete Sammlung von Elementen, bei der jedes Element an einer bestimmten Position (Index) steht. Sie ermöglicht das Hinzufügen, Entfernen und Abrufen von Elementen an jeder Position in der Liste. Listen sind flexibel und werden häufig verwendet, wenn die Reihenfolge der Daten wichtig ist oder man schnell auf ein bestimmtes Element zugreifen muss.
Typische Operationen:
Einfügen eines Elements an einer bestimmten Position (oft Index genannt).
Entfernen eines Elements von einer bestimmten Position.
Zugriff auf ein Element durch seinen Index.
Implementation: Listen können mithilfe von Arrays oder als verkettete Listen implementiert werden. Arrays bieten schnellen Zugriff auf jedes Element, sind aber nur mit Tricks verlängerbar, während verkettete Listen beim Einfügen und Entfernen von Elementen flexibler sind. (Das schauen wir uns im Detail in späteren Kapiteln an.)
2.1.2. Stapel (Stack)#
Ein Stapel (engl. Stack) ist ein ADT, der nach dem Prinzip LIFO (Last In, First Out) funktioniert, was bedeutet, dass das zuletzt hinzugefügte Element als erstes entfernt wird. Stell dir einen Stapel Bücher vor – das zuletzt obenauf gelegte Buch wird zuerst wieder genommen. Stapel werden häufig in Situationen verwendet, in denen es wichtig ist, den Verlauf von Aktionen rückgängig zu machen, wie zum Beispiel beim “Rückgängig”-Machen in Textverarbeitungsprogrammen.
Typische Operationen:
push: Ein Element auf den Stapel legen.pop: Das oberste Element vom Stapel entfernen.top: Das oberste Element ansehen, ohne es zu entfernen.
Implementation: Ein Stapel kann entweder mit einem Array oder einer verketteten Liste realisiert werden. Bei der Array-Implementierung wird das letzte Element eines Arrays als oberstes Stack-Element verwendet. (Details in späteren Kapiteln.)
2.1.3. Warteschlangen (Queue)#
Eine Warteschlange (engl. Queue) funktioniert nach dem Prinzip FIFO (First In, First Out), d. h. das erste hinzugefügte Element wird als erstes entfernt. Ein praktisches Beispiel ist eine Warteschlange im Supermarkt: Der Kunde, der zuerst in die Schlange tritt, wird auch als erstes bedient. Warteschlangen werden oft verwendet, um Aufgaben oder Prozesse in der Reihenfolge zu verarbeiten, in der sie eintreffen, zum Beispiel in Druckaufträgen oder beim Netzwerkdatenverkehr.
Typische Operationen:
enqueue: Ein Element ans Ende der Warteschlange hinzufügen.dequeue: Das erste Element aus der Warteschlange entfernen.peek: Das erste Element ansehen, ohne es zu entfernen.
Implementation: Eine Warteschlange kann ebenfalls mit einem Array oder einer verketteten Liste implementiert werden. Für eine effizientere Umsetzung kann eine zirkuläre Warteschlange verwendet werden, um Speicherplatz zu sparen. (Wir werden aber nur die Implementation als verkettete Liste nutzen.)
2.1.4. Assoziative Arrays (auch: Dictionary/Map)#
Ein assoziatives Array (auch Dictionary oder Map) ist ein ADT, das Daten als Schlüssel-Wert-Paare speichert. Anstatt auf Daten durch einen Index (Position) zuzugreifen, erfolgt der Zugriff über einen eindeutigen Schlüssel, der mit einem bestimmten Wert verknüpft ist. Diese Struktur ist besonders nützlich, wenn du Daten schnell anhand eines eindeutigen Identifikators (z. B. einem Namen oder einer ID) abrufen möchtest, wie in einem Telefonbuch oder einer Datenbank.
Typische Operationen:
Zugriff auf einen Wert durch seinen Schlüssel.
Einfügen eines neuen Schlüssel-Wert-Paares.
Entfernen eines Schlüssel-Wert-Paares.
Implementation: Die häufigste Implementierung eines assoziativen Arrays erfolgt über Hashtabellen, wobei Schlüssel über eine Hashfunktion schnell zu den entsprechenden Werten zugeordnet werden. Eine andere Möglichkeit ist die Verwendung von balancierten Bäumen für geordnete Schlüssel.