Datenstruktur

Sobald Daten eine komplexere Form annehmen als eine einzelne Variable verarbeiten kann, müssen sie in speziellen Datenstrukturen organisiert werden.

Diese Datenstrukturen unterscheiden sich im Hinblick auf die Zugriffsmöglichkeiten, die sie auf die Daten bieten, sowie auf die Zeit, die dafür nötig ist.

Array

Siehe auch Array

Ein Array, in der deutschsprachigen Literatur auch Feld genannt, ist eine der einfachsten Datenstrukturen. Ursprünglich ist ein Array eine Reihe von hintereinander liegenden Speicherzellen. Bei der Erstellung des Arrays wird ein Block an Speicherzellen mit einer festen Größe reserviert. Deswegen muss man z.B. in C oder Java immer noch bei der Initialisierung eines Arrays dessen Größe angeben und kann diese nachträglich nicht mehr verändern.

Auf die Werte eines Arrays wird mit einem Index zugegriffen, der typischerweise bei 0 beginnt.

Verkettete Liste

Eine verkettete Liste

Siehe auch Verkettete Liste

Eine verkettete Liste (engl. linked list) ist eine Datenstruktur, die beliebig viele Elemente in linearer Form speichern kann, d.h. zu jedem Element außer dem letzten existiert genau ein Nachfolger und zu jedem Element außer dem ersten existiert genau ein Vorgänger.

Praktisch an verketteten Listen ist, dass man mit relativ geringem Aufwand mittendrin Elemente löschen oder einfügen kann, ohne dass Lücken entstehen oder potenziell größere Datenmengen verschoben werden müssen. Auch für die Implementierung von Stacks oder Queues sind sie geeeignet.

Nachteilig ist, dass Operationen wie Suchen eine Laufzeit in ${\mathcal {O}}(n)$ aufweisen.

Tupel

Siehe auch Tupel

Als Tupel werden verschiedene Datenstrukturen bezeichnet. In Python werden als Tupel unveränderter Listen von fester Länge bezeichnet. Diese Tupel können gut genutzt werden, um eine Funktion mehrere Daten auf einmal zurückgeben zu lassen, da die Elemente eines Tupels direkt als Variablen gespeichert werden können.

Tupel im mathematischen Sinne sind die Einträge in relationalen Datenbanken wie SQL

Menge

Eine Menge von geometrischen Formen

Siehe auch Menge

Der Mathematiker Georg Cantor definierte 1895 eine Menge wie folgt:

„Unter einer ‚Menge‘ verstehen wir jede Zusammenfassung $M$ von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die ‚Elemente‘ von M genannt werden) zu einem Ganzen.“

Wohlunterschieden meint hier, dass jedes Element einer Menge einzigartig ist, d.h. eine Menge kann nicht zweimal dasselbe Element enthalten.

In Python werden Mengen mit geschweiften Klammern notiert, in Java müssen dafür Klassen wie HashSet oder TreeSet benutzt werden.

Stack

Ein Stack

Siehe auch Stack

Auch bekannt als Stapel oder Kellerspeicher. Ein Kellerspeicher funktioniert wie ein vollgerümpelter Keller: man kann nur auf das zuoberst liegende Objekt zugreifen (pop) und weitere Objekte werden oben auf dem Stack abgelegt (push). Dieses Prinzip heißt Last-in-first-out (LIFO).

Stacks bilden die Grundlage des Arbeitsspeichers bei der Assembler-Programmierung und sind außerdem die einzige Datenstruktur in der Programmiersprache Shakespeare.

Queue

Eine Warteschlange

Siehe auch Warteschlange

In Warteschlangen gilt, egal ob in der Programmierung oder an der Kasse: Wer zuerst kommt, ist auch zuerst dran. Dieses Prinzip heißt First-in-first-out (FIFO). Warteschlangen können zum Beispiel bei der Breitensuche verwendet werden, um die Reihenfolge zu speichern, in der die Knoten eines Graphen betrachtet werden sollen.

Eine besondere Form der Warteschlange ist die Prioritätswarteschlange (Priority Queue), in der jedem Element eine Priorität zugewiesen wird und die Elemente nach Priorität sortiert der Liste entnommen werden.

Schlüssel-Wert-Paare

Ein Wörterbuch ist eine analoge Schlüssel-Wert-Datenstruktur

Siehe auch Schlüssel-Wert-Datenstruktur

Auch bekannt als Assoziatives Array, Wörterbuch, Dictionary, Map (in Java) oder Hash (in Perl)

In einer Schlüssel-Wert-Datenstruktur werden Paare von Daten gespeichert, wobei eines der Daten als Suchschlüssel dient. Mit diesem Schlüssel können die Daten sehr effizient gefunden werden. Das Prinzip ist dasselbe wie bei einem Wörterbuch: wenn ich in einem lateinisch-deutschen Wörterbuch die deutsche Bedeutung von pathicus herausfinden möchte, geht das sehr schnell. Andersherum ist es sehr aufwändig, die lateinische Bedeutung von einem deutschen Wort herauszufinden.

Baum

Ein Baum

Siehe auch Baum

Bäume sind eine sehr flexible Datenstruktur, in der Daten ähnlich wie in einer verketteten Liste abgelegt werden, nur dass jedes Element nicht nur auf seinen direkten Nachfolger verweist, sondern auf mehrere andere Elemente. Häufig verwendet man Binärbäume, bei denen jedes Element auf zwei andere verweist. Viele andere Datenstrukturen werden "unter der Haube" als Bäume implementiert. Auch die Daten einer Datenbank werden in Baumstrukturen abgelegt, um die Anzahl der langsamen Festplattenzugriffe zu minimieren.

Heap

Siehe auch Heap

Ein Sonderfall von Bäumen sind Heaps, auch Halden oder Haufen genannt, mit denen etwa Prioritätswarteschlangen implementiert werden können. Die Heap-Eigenschaft legt fest, dass jeder Knoten größer ist als seine Kinder. Ein Heap ist damit nicht sortiert, aber erleichtert es sehr, das größte Element zu finden und zu extrahieren.

Graph

Ein Graph

Siehe auch Graph Ein Graph ist eine sehr vielseitige Datenstruktur, die aus so genannten Knoten besteht, die mit Kanten verbunden sind. Damit lassen sich verschiedenste Sachverhalte modellieren, etwa die Abhängigkeiten von Aufgaben oder Beziehungen zwischen Objekten.