Datenstrukturen

Wenn man in der Informatik von einer Datenstruktur spricht, meint man meistens die Organisation von Daten. Zur Speicherung der Daten werden sogenannte Objekte verwendet, um eine Datenkapselung zu erreichen und um diese effizienter im Speicher verwalten zu können. Es gibt dennoch unterschiedliche Arten von Datenstrukturen. Neben der bereits bekannten statischen Datenstruktur gibt es in der Informatik auch noch eine dynamische Datenstruktur.

Statische Datenstrukturen

Unter die statischen Datenstrukturen werden z.B. die primitiven Datentypen in Java gezählt oder auch Arrays, sogenannte Felder um mehrer Daten der gleichen Art abzulegen. Statische Datenstrukturen haben ein festes Datenschema und müssen somit bei neuen Daten ständig neu erstellt werden. Bei dynamischen Datenstrukturen hingegen liegt kein festes Speicherschema fest und beim Hinzufügen oder Löschen von Daten erweitert sich der Speicher wie der Name schon sagt “dynamisch”. Du lernst in den Kapiteln “Datentypen in Java” und “Arrays in Java” alles nötige um statische Datenstrukturen zu verstehen.Aber was machen nun dynamische Datenstrukturen anders als statische Datenstrukturen?

Dynamische Datenstrukturen

Dynamische Datenstrukturen arbeiten mit Objekten und Objektadressen, d.h. wenn der Benutzer aktuell ein bestimmtes Objekt abfragen will, geschieht das mit hilfe eines Zeigers, der dann auf das Objekt verweist. Und das Objekt verweist wieder auf das nächste naheliegende Objekt. Die Daten sind folglich in einer Kette oder in einem Netz organisiert und ein Objekt zeigt auf ein oder mehrere Objekte in seiner Nähe. Dynamische Datenstrukturen können in folgender Form organisiert sein:  Listen (einfach und doppelt Verkettet), Stacks, Binärbaum oder Hashtabellen. Wir werden dir nun einige dieser Formen der dynamischen Datenstrukturen vorstellen:

Stack

Ein Stack lässt sich als Stapel oder Kellerspeicher ins Deutsche übersetzen. Aber was kann man sich unter einem Kellerspeicher vorstellen? Ein Kellerspeicher findet man z.B. in einer Kantine wenn man sich die Teller dort etwas genauer anschaut. Die Teller sind alle aufeinander gestapelt und es ist nur möglich von oben einen Teller zunehmen, da sonst der ganze Stapel herunterfallen würde.

Hier sieht man einen Tellerstapel. Der Tellerstapel stellt eine dynamische Datenstruktur dar.
Quelle:
https://pixabay.com/de/photos/teller-stapel-geschirr-tellerstapel-629970/

Man muss sich somit Teller für Teller durch den Stapel durcharbeiten bis man den letzten Teller erreicht. Das Prinzip, das hinter einem Stapel steckt, nennt man LIFO (Last In First Out). Aber wie benutzt man nun einen Stack in Java?

Wir werden dir im Folgenden ein einfaches Programm zeigen, dass seine Daten mit hilfe eines Stacks verwaltet:

Du kannst dir das Programm auch gerne hier downloaden oder als PDF anschauen:

Listen

Neben dem Stack gibt es in Java auch noch Listen, um dynamische Datenstrukturen zu realisieren. Listen bestehen in ihrem Aufbau aus einem Head und einem Foot. Zwischen Head und Foot befinden sich beliebig viele Items (Daten), des gleichen Datentyps. Die Items ähneln in ihrem Verhalten sehr stark einem Array. Dennoch besteht ein Item nicht nur aus einem Datensatz. Neben den Datensätzen enthalten Items auch noch Adressen. Du fragst dich nun sicher warum die Items in einer Liste Adressen enthalten, die nicht auf die Datensätze verweisen. Der Zugriff auf Listen in Java erfolgt sequentiell, d.h. dass der Zugriff durch einen Zeiger erfolgt, der Schritt für Schritt jeden Datensatz abklappert bis er den gesuchten Datensatz gefunden hat. Um sich in der Liste zurecht zu finden müssen die Items verkettet werden. In Java gibt es einfach und doppelt verkettete Listen. Einfach verkettete Listen haben neben dem Datensatz noch eine Adresse, die auf das nächste Item zeigt. Somit kann sich der Zeiger sequentiell in eine Richtung durch die Liste bewegen. Eine doppelt verkettete Liste hat an jedem Item zwei Adresse, die auf das vorherige und das nachfolgende Item zeigen. Somit kann sich der Zeiger in beide Richtungen durch die Liste arbeiten. Damit du dir den Aufbau von einfach und doppelt verketteten Listen besser vorstellen kannst, haben wir für dich zwei Grafiken angefertigt:

Einfach verkettete Liste

Doppelt verkettete Liste

Nun müsste dir der prinzipielle Aufbau einer einfach und doppelt verketteten Liste klar geworden sein. Aber was passiert nun wenn wir die Liste anpassen durch neue Items oder bestehende Items aus der Liste löschen wollen. Wie wir wissen müsste das Löschen und Einfügen in die Liste funktionieren, da es sich um eine dynamische Datenstruktur handelt. Wir werden dir nun zeigen wie du aus beiden Listentypen Daten löschst und einfügst:

Löschen aus einer einfach verketteten Liste

Einfügen in eine einfach verkettete Liste

Löschen aus einer doppelt verketteten Liste

Einfügen in eine doppelt verkettete Liste