Grundlagen Datenstrukturen

Datenstrukturen dienen zur Organisation und Speicherung von Daten, damit schnell auf sie zugegriffen und effizient mit ihnen gearbeitet werden kann.

Erklärung

Eine Datenstruktur ist ein Objekt, in dem Daten gespeichert werden. Daten können hier zum Beispiel Zahlen, Buchstaben oder Wörter sein.

Durch diese Datenstrukturen werden die darin gespeicherten Daten korrekt im Speicher angelegt und durch Algorithmen organisiert.

Dafür müssen auf den Datenstrukturen folgende Operationen angewendet werden können:

• Einfügen
• Löschen
• Suchen

Es gibt zwei Arten von Datenstrukturen:

• statische Datenstrukturen
• dynamische Datenstrukturen

Statische Datenstrukturen

Statische Datenstrukturen haben ein festes Speicherschema. Das heißt, die Größe wird zu Beginn einmalig festgelegt und kann danach nicht mehr verändert werden.

Wenn doch mehr Daten gespeichert werden sollen, als zunächst geplant, muss eine neue Datenstruktur angelegt werden.

Die drei wichtigsten Arten von statischen Datenstrukturen sind:

• Datentypen
• Array
• Record

Datentypen

Die einfachsten statischen Datenstrukturen sind die primitiven Datentypen, wie:

• Integer: ganze Zahlen
• Boolean: wahr oder falsch
• Double: Kommazahlen
• Char: Buchstaben

Sie gehören zu den statischen Datenstrukturen, da sie Daten speichern können und auch ihre Größe begrenzt ist.

Datentypen sind jedoch fest in den meisten Programmiersprachen eingebaut, weswegen sie nicht angepasst werden können.

Array

Du kannst dir eine Array wie einen Schrank mit vielen Schubladen vorstellen:

Dabei kannst du in jede Schublade genau ein Objekt legen oder wieder herausnehmen.

So ist es auch bei der Datenstruktur.

Der Vorteil einer Arrays ist, du kannst direkt auf die einzelnen Felder zugreifen.

Ein Nachteil ist jedoch, dass du schon vorher die Größe kennen musst (also die Menge an Daten, die im Array gespeichert werden soll). Auch können nur Daten mit dem gleichen Typ in einem Array gespeichert werden.

Record

Um Beziehungen zwischen Werten verschiedenen Typs herzustellen, kannst du Records (deutsch Verbunde) verwenden. Diese kannst du dir wie Steckbriefe vorstellen:

Bei einem Steckbrief werden verschiedene Daten festgehalten:

Geburtsdatum, Alter, Vorname, Nachname, Beruf, Lieblingsessen und so weiter.

So ist das auch bei Records. Auch hier können Daten unterschiedlichen Typs in einem Record zusammengefasst werden.

Aber auch Records haben eine feste Größe.

Dynamische Datenstrukturen

Dynamischen Datenstrukturen haben nicht das Problem der festen Größe, das heißt ihre Größe ist veränderbar.

Beim Einfügen und Löschen wird der Speicher also immer angepasst. Du musst dir also nicht mehr vorher überlegen, wie viele Daten du speichern möchtest.

Bei dynamischen Datenstrukturen werden Zeiger verwendet. Ein Zeiger ist ein Verweis auf ein Objekt. Bei den dynamischen Datenstrukturen verweist ein Objekt meist auf das nächste. Wie das genau funktioniert ist abhängig von der verwendeten Datenstruktur.

Es gibt 5 wichtige dynamische Datenstrukturen, die du kennen solltest:

• Liste
• Queue
• Stack
• Baum
• Hashtabelle

Liste

Eine Liste ist eine Aneinanderreihung von Elementen. Du kannst dir eine Liste wie eine Menschenkette vorstellen:

Jedes Element zeigt auf seinen Nachfolger (manchmal zusätzlich auch Vorgänger). Es gibt dabei mehrere Arten, wie die einfach, doppelt oder kreisförmig verkettete Liste.

Queue

Eine Queue ist wie eine Warteschlange vor einer Kasse.

Der/Die Erste, der/die sich anstellt, wird auch als Erstes bedient.

Stack

Ein Stack ist wie ein Tellerstapel an einem Buffet:

Neue Teller werden oben auf den Stapel gestellt und diese werden auch als erstes wieder vom Stapel genommen.

Baum

Ein Baum ist aufgebaut wie sein Namensgeber:

Ein Baum besteht aus einer Wurzel, Blättern und inneren Knoten in denen jeweils Informationen hierarchisch gespeichert werden können.

Auch bei den Bäumen gibt es verschiedene Arten, wie den Binärbaum.

Hashtabelle

Eine Hashtabelle kannst du dir wie einen Umzug vorstellen:

Du hast eine bestimmte Anzahl an Kartons, in die du deine Habseligkeiten verpacken möchtest. Dabei packst du beispielsweise 3 Dinge in Kiste 1, 4 in Kiste 2 und so weiter.

So funktioniert auch eine Hashtabelle. Sie kann mithilfe der Hash-Funktion auf verschiedene Weisen befüllt werden.

Nutzungskontext

Ohne Datenstrukturen ist moderne Software-Entwicklung gar nicht möglich, da sie die Grundlage für alle Anwendungen bilden.

Daher gibt es in fast allen Programmiersprachen ein Set an Datenstrukturen, die bereits implementiert sind.

Das bedeutet jedoch nicht, dass in jeder Sprache alle Datenstrukturen enthalten sind.