Datenstruktur

Wenn du eine Playlist, einen Klassenchat oder deine Schulnoten auf dem Handy öffnest, liegen die Informationen nicht lose herum. Ein Programm braucht Ordnung, damit es etwas schnell speichern, finden oder verändern kann. Genau dafür gibt es in der Informatik passende Ordnungssysteme.

Daten brauchen Ordnung

Daten sind gespeicherte Informationen. Das können Zahlen, Namen, Texte, Bilder oder Wahrheitswerte wie wahr und falsch sein. Ein einzelner Wert reicht oft nicht aus. Programme arbeiten meistens mit vielen zusammengehörigen Werten.

Eine Datenstruktur ist eine festgelegte Art, Daten im Computer zu speichern und zu ordnen. Sie legt fest, wie Daten zusammengehören und wie ein Programm mit ihnen arbeitet.

Definition

Eine Datenstruktur ist eine Organisationsform für Daten. Sie legt fest, wie Daten gespeichert, verbunden und über bestimmte Handlungen bearbeitet werden.

Eine Operation ist eine Handlung, die ein Programm mit einer Datenstruktur ausführt. Typische Operationen sind Einfügen, Lesen, Suchen, Ändern und Löschen.

Ein Algorithmus ist eine genaue Schrittfolge, mit der ein Programm eine Aufgabe löst. Algorithmen nutzen Datenstrukturen, damit sie Daten passend verarbeiten können.

Deine Lernziele

• Du verstehst, was eine Datenstruktur ist.
• Du erkennst typische Handlungen wie Einfügen, Löschen und Suchen.
• Du lernst wichtige Ordnungssysteme für Daten kennen.
• Du kannst erklären, warum die Wahl der Ordnung die Geschwindigkeit eines Programms beeinflusst.

Beispiel

Stell dir eine digitale Klassenliste vor.

Sie speichert Namen, Geburtstage und vielleicht E-Mail-Adressen. Das Programm muss neue Schüler einfügen, einzelne Namen suchen und alte Einträge löschen können. Die Klassenliste ist also nicht nur eine Sammlung von Daten. Sie braucht auch passende Operationen.

Merke

Eine Datenstruktur beantwortet zwei Fragen: Wie liegen die Daten geordnet vor? Und welche Operationen sind damit sinnvoll möglich?

Elemente, Schlüssel und Datentypen

Ein Element ist ein einzelner Eintrag in einer Datenstruktur. In einer Notenliste kann ein Element eine Note sein. In einer Kontaktliste kann ein Element ein ganzer Kontakt sein.

Ein Datentyp legt fest, welche Art von Wert gespeichert wird. Beispiele sind ganze Zahl, Kommazahl, Textzeichen, Zeichenkette oder Wahrheitswert.

Ein Schlüssel ist ein Wert, mit dem ein Element gezielt gefunden wird. In einer Schülerliste kann das eine Schülernummer sein. In einem Wörterbuch ist das gesuchte Wort der Schlüssel.

Beispiel

Ein Kontakt im Handy kann so gedacht werden:

Name: Lea Müller
Telefonnummer: 0176...
Klasse: 9b

Der ganze Kontakt ist ein Element. Die Telefonnummer speichert man meistens als Zeichenkette, weil führende Nullen, Leerzeichen oder Landesvorwahlen wichtig sein können. Der Name oder eine Kontakt-ID kann als Schlüssel dienen.

Gut zu wissen

Ein Schlüssel muss nicht immer ein Name sein. Programme verwenden oft künstliche Schlüssel wie eine ID-Nummer, damit jedes Element eindeutig gefunden werden kann.

Statisch oder dynamisch

Manchmal weiß ein Programm vorher genau, wie viele Werte es speichern muss. Manchmal wächst oder schrumpft die Datenmenge ständig. Deshalb unterscheidet man oft zwischen statischen und dynamischen Datenstrukturen.

Eine statische Datenstruktur hat eine feste Größe oder ein festes Schema. Der Platz wird vorher festgelegt. Wenn später mehr Platz gebraucht wird, muss die Struktur oft neu angelegt oder umgebaut werden.

Eine dynamische Datenstruktur kann ihre Größe während der Programmausführung besser anpassen. Sie eignet sich, wenn viele Einträge hinzukommen oder verschwinden.

Beispiel

Ein Sitzplan für ein Klassenzimmer mit 30 festen Plätzen wirkt statisch. Du planst mit einer festen Anzahl von Plätzen.

Eine Chatgruppe wirkt dynamisch. Nachrichten kommen ständig dazu. Manche werden gelöscht. Die Anzahl verändert sich die ganze Zeit.

Merke

Statisch heißt: Die Struktur ist eher fest geplant. Dynamisch heißt: Die Struktur kann mit der Datenmenge wachsen oder schrumpfen.

Lineare Datenstrukturen

Eine lineare Datenstruktur ordnet Elemente in einer Reihenfolge an. Du kannst sie dir wie eine Reihe vorstellen: erstes Element, zweites Element, drittes Element und so weiter.

Ein Array ist eine lineare Datenstruktur mit nummerierten Plätzen. Die Nummer eines Platzes heißt Index. Über den Index kann ein Programm direkt auf ein bestimmtes Feld zugreifen.

Eine Liste ist eine lineare Datenstruktur, bei der Elemente nacheinander verbunden sind. Bei einer verketteten Liste kennt ein Element meist den Verweis auf das nächste Element. Ein Verweis ist eine gespeicherte Verbindung zu einem anderen Element.

Beispiel

Ein Array für fünf Noten könnte so aussehen:

Index 0: 2
Index 1: 1
Index 2: 3
Index 3: 2
Index 4: 4

Wenn das Programm die Note an Index 2 lesen soll, kann es direkt dorthin springen.

Beispiel

Eine verkettete Liste für eine Playlist kann so gedacht werden:

Lied A zeigt auf Lied B.
Lied B zeigt auf Lied C.
Lied C zeigt auf Lied D.

Wenn du ein Lied zwischen B und C einfügst, müssen vor allem die Verweise angepasst werden.

Merke

Arrays sind stark, wenn du direkt über einen Index zugreifen willst. Listen sind stark, wenn du oft Elemente einfügst oder entfernst, ohne viele andere Elemente zu verschieben.

Stack und Queue

Nicht jede lineare Datenstruktur erlaubt Zugriff auf jedes Element. Manche Strukturen haben absichtlich strenge Regeln. Dadurch werden bestimmte Aufgaben besonders einfach und zuverlässig.

Ein Stack ist ein Stapel. Das zuletzt eingefügte Element wird zuerst wieder entfernt. Dieses Prinzip heißt LIFO. LIFO bedeutet: zuletzt hinein, zuerst heraus.

Beispiel

Stell dir einen Tellerstapel vor. Du legst einen Teller oben drauf. Wenn du später einen Teller nimmst, nimmst du wieder den obersten. Der zuletzt abgelegte Teller kommt also zuerst dran.

Eine Queue ist eine Warteschlange. Das zuerst eingefügte Element wird zuerst wieder entfernt. Dieses Prinzip heißt FIFO. FIFO bedeutet: zuerst hinein, zuerst heraus.

Beispiel

An der Mensakasse stellt sich zuerst Noah an, dann Mira, dann Cem. Wenn fair bedient wird, kommt Noah zuerst dran. Genau so arbeitet eine Queue.

Nichtlineare Datenstrukturen

Eine nichtlineare Datenstruktur ordnet Elemente nicht nur in einer einfachen Reihe an. Elemente können verzweigen oder viele Beziehungen gleichzeitig haben.

Ein Knoten ist ein Element in einem Baum oder Graphen. Eine Kante ist eine Verbindung zwischen zwei Knoten.

Ein Baum ist eine nichtlineare Datenstruktur mit einer hierarchischen Ordnung. Hierarchisch bedeutet: Es gibt Ebenen, zum Beispiel oben, darunter, darunter. Der oberste Knoten heißt Wurzel.

Beispiel

Ein Dateisystem auf dem Computer ist oft baumartig.

Der Ordner Schule liegt oben. Darin liegen die Ordner Mathe, Deutsch und Informatik. Im Ordner Informatik liegen Dateien und weitere Unterordner. Von oben nach unten entstehen Verzweigungen.

Ein Graph ist eine Datenstruktur aus Knoten und Kanten, bei der viele Verbindungen möglich sind. Ein Graph muss keine oberste Wurzel haben. Er eignet sich für Netzwerke.

Beispiel

Ein U-Bahn-Netz kann als Graph dargestellt werden. Stationen sind Knoten. Strecken zwischen Stationen sind Kanten. Von einer Station können mehrere Wege weiterführen.

Hashtabelle und Effizienz

Wenn ein Programm sehr schnell etwas finden soll, reicht eine normale Reihe oft nicht aus. Dann kann eine besondere Struktur helfen.

Eine Hashtabelle speichert Werte über Schlüssel. Eine Hashfunktion berechnet aus einem Schlüssel eine Speicherposition. So kann ein Programm oft sehr schnell zum passenden Eintrag springen.

Beispiel

Du suchst im Handy nach dem Namen Samira. Eine Hashtabelle kann aus dem Schlüssel Samira berechnen, wo der zugehörige Kontakt ungefähr liegt. Das Programm muss dann nicht jeden Kontakt der Reihe nach prüfen.

Manchmal berechnet eine Hashfunktion für zwei verschiedene Schlüssel dieselbe Position. Das heißt Kollision. Eine Kollision ist ein Zusammenstoß von Speicherpositionen. Gute Hashtabellen haben Strategien, um damit umzugehen, zum Beispiel kleine Listen an einer Position.

Effizienz bedeutet in der Informatik, dass ein Programm sparsam mit Zeit und Speicher umgeht. Die Laufzeit beschreibt, wie lange eine Operation ungefähr braucht. Der Speicherbedarf beschreibt, wie viel Speicherplatz benötigt wird.

Beispiel

Wenn du in einer unsortierten Liste mit 1000 Namen suchst, musst du im schlimmsten Fall fast alle Namen prüfen. In einer gut aufgebauten Hashtabelle findest du den Eintrag oft viel schneller.

Dafür braucht die Hashtabelle meist zusätzlichen Speicher und eine gute Hashfunktion.

Gut zu wissen

Es gibt nicht die beste Datenstruktur für alles. Eine Struktur kann beim Suchen stark sein, aber beim Sortieren schwächer. Eine andere kann wenig Speicher brauchen, aber langsamer suchen.

Zusammenfassung

Eine Datenstruktur ordnet Daten so, dass Programme sinnvoll mit ihnen arbeiten können. Sie besteht nicht nur aus gespeicherten Werten, sondern hängt eng mit typischen Operationen wie Einfügen, Suchen, Lesen und Löschen zusammen.

Wichtige lineare Datenstrukturen sind Array, Liste, Stack und Queue. Ein Array nutzt Indizes für direkten Zugriff. Eine Liste verbindet Elemente über Verweise. Ein Stack arbeitet nach LIFO. Eine Queue arbeitet nach FIFO.

Nichtlineare Datenstrukturen wie Baum und Graph speichern Verzweigungen und Beziehungen. Eine Hashtabelle nutzt Schlüssel und eine Hashfunktion, um Werte oft sehr schnell zu finden.

Merke

Die wichtigste Frage lautet nicht: Welche Datenstruktur klingt am besten? Sondern: Welche Operationen braucht mein Programm am häufigsten?