Wenn du Programmierer:in werden möchtest, solltest du die grundlegenden Datenstrukturen beherrschen. So hebst du dich von der Masse ab und wertest deinen Lebenslauf mit gefragten Skills auf.
Das Erlernen von Algorithmen ist ebenso sinnvoll, da sie mithilfe der Daten, die du strukturierst, für die Lösung verschiedener Probleme eingesetzt werden.
In diesem Leitfaden stellen wir die acht gängigsten Datenstrukturen vor und geben dir eine einfache Anleitung zum Schreiben von Algorithmen. Doch zunächst zu den Grundlagen!
Anmerkung der Redaktion: GoDaddy betreibt jetzt ein Hosting-Center in Indien, das schnellere Ladezeiten und mehr Sicherheit für Kundenwebsites ermöglicht.
Was ist eine Datenstruktur?
Eine Datenstruktur ist eine spezielle Methode zum Speichern und Organisieren von Daten auf einem Computer, um sie effizient bearbeiten zu können.
Unstrukturierte Daten sind nicht organisiert oder haben kein definiertes Datenmodell.
So eignen sie sich nicht für Analysen oder Operationen. Unstrukturierte Daten sind ein stark verbreitetes Problem. Weltweit sind schätzungsweise 80 % der Daten unstrukturiert.
Die meisten Organisationen erfassen und speichern Daten unorganisiert, was die Nutzung der Daten erschwert.
Es gibt verschiedene Arten von Datenstrukturen, die für manche Vorgänge geeignet sein können, für andere jedoch nicht.
Daher ist es die Aufgabe der Programmierer:innen, herauszufinden, welche Datenstruktur sich für eine effiziente Datenanalyse eignet, um Probleme zu lösen oder Ziele zu erreichen.
Datenstrukturen bilden die Grundlage der Softwareentwicklung und Informatik und werden in den meisten Softwaresystemen verwendet.
Anmerkung der Redaktion: Eine der besten Möglichkeiten, Kunden zu beeindrucken, ist ein professionelles Web-Zertifikat der GoDaddy Academy. Die videobasierten Zertifizierungen werden online von Branchenexperten unterrichtet und enden mit einer Live-Projektprüfung.
Die häufigsten Arten von Datenstrukturen
Im Folgenden betrachten wir acht der gängigsten Datenstrukturen.
1. Arrays
Die erste unserer grundlegenden Datenstrukturen ist eine der einfachsten. Ein Array ist eine Struktur mit fester Größe, die mehrere Elemente desselben Datentyps sequenziell speichert.
Ein Array enthält dieselben, durch eine feste Größe definierten Elemente eines Datentyps (auch Variablen genannt). Daher lässt sich die Größe des Arrays nicht ändern. In einem Array-Index beginnt jedes Element mit „0“.
Ein Array enthält Elemente in jedem Container und in einer Sequenz angeordnete kleine Container.
Da Arrays eine feste Größe haben, ist es nicht möglich, weitere Elemente in ein Array einzufügen oder zu löschen.
Um ein Element einzufügen, musst du ein neues Array mit erhöhter Größe (+1) erstellen, die vorhandenen Elemente kopieren und ein neues Element hinzufügen.
Arrays werden hauptsächlich als Struktur zum Erstellen komplexerer Datenstrukturen und für Sortier-Algorithmen verwendet.
2. Verkettete Listen
Eine verkettete Liste (linked list) ist eine lineare Datenstruktur, in der die Elemente linear angeordnet und miteinander verknüpft sind. Deshalb ist der Zugriff auf Daten nicht zufällig möglich; der Zugriff muss sequentiell erfolgen.
In einer verknüpften Liste wird das erste Element als “Kopf” (head) und das letzte als „Ende“ (tail) bezeichnet.
Jedes Element wird als „Knoten“ bezeichnet und enthält einen Zeiger und einen Schlüssel in der verknüpften Liste. Der Zeiger verweist dabei immer auf den nächsten Knoten.
Durch das Erstellen einer einfach verknüpften Liste kann jedes Element von Kopf bis Ende (vorwärts) durchlaufen werden. Ebenso kann eine doppelt verknüpfte Liste in beide Richtungen durchlaufen werden: von Kopf bis Ende (vorwärts) und von Ende bis Kopf (rückwärts).
Sie werden zum Wechseln zwischen Programmen zur Verwaltung von Symboltabellen verwendet.
3. Stapel
Als Nächstes auf unserer Liste der wichtigsten Datenstrukturen steht der Stapel. Der Stapel (stack) ist ebenfalls eine lineare Ordnungsstruktur, arbeitet jedoch nach dem LIFO-Prinzip (Last In First Out). Daher wird er auch als LIFO-Struktur bezeichnet. Das bedeutet, dass das zuletzt platzierte Element zuerst aufgerufen werden kann.
Du kannst ein Element hinzufügen (push) oder entfernen (pop) – wie ein Tellerstapel in der realen Welt.
Stapel werden hauptsächlich in der rekursiven Programmierung verwendet, um Funktionsaufrufe und mathematische Ausdrücke für Parsing oder Auswertungen zu implementieren.
4. Warteschlangen
Warteschlangen (queues) entsprechen der Stapel-Struktur, folgen aber nicht dem LIFO-Modell. Eine Warteschlange folgt dem FIFO-Modell (First In First Out). Das bedeutet, dass das erste Element zuerst aufgerufen werden kann.
Eine Schlange von Menschen, die ein Gebäude betreten, ist ein gutes Beispiel. Die erste Person, die die Schlange beginnt, betritt das Gebäude vor allen anderen, und die Person am Ende der Schlange betritt das Gebäude als Letzte.
Auf die gleiche Weise kannst du am Ende der Struktur ein neues Element hinzufügen (enqueue) und am Anfang ein Element aus der Warteschlange entfernen (dequeue).
Sie werden hauptsächlich im Multithreading zur Verwaltung von Threads sowie zur Ausführung von Prioritätswarteschlangen-Systemen verwendet.
5. Hash-Tabellen
Die Hashtabellen-Datenstruktur verknüpft jeden Wert mit einem Schlüssel (key) und speichert ihn.
Mithilfe eines Schlüssels kannst du Werte effizient nachschlagen.
Aus einer Gruppe ähnlicher Objekte lässt sich leicht ein bestimmtes Objekt finden.
Eine Hash-Tabelle lässt sich als Studenten-ID (key) verstehen, die eine Hochschule Studierenden zuweist. Alle Details zu einem Studierenden lassen sich anhand der Studenten-ID leicht finden.
Um Datensätze beliebiger Größe auf eine feste Größe abzubilden, verwendet die Hash-Tabelle die Hash-Funktion. Die von einer Hash-Funktion zurückgegebenen Werte werden als Hashwerte bezeichnet.
Sie werden hauptsächlich zum Erstellen von verknüpften Arrays, Datenbank-Indizes und einem „Set“ verwendet.
6. Bäume
Eine weitere grundlegende Datenstruktur ist ein Baum. In der Baumstruktur sind Daten wie in einer verknüpften Liste miteinander verbunden, jedoch hierarchisch organisiert, ähnlich wie in der visuellen Darstellung eines Stammbaums.
Es gibt verschiedene Baumtypen, wie zum Beispiel:
- Binärer Suchbaum (BST)
- Rot-Schwarz-Baum
- B-Baum, Treap
- Splay-Baum
- N-ärer Baum
- AVL-Baum
Jeder Typ eignet sich für bestimmte Anwendungen.
Beispielsweise speichert die BST-Datenstruktur Werte (Daten) sortiert. Jeder Knoten in einem BST enthält die folgenden Attribute:
- Der Schlüssel (key) ist der im Knoten gespeicherte Wert.
- Links ist der Zeiger auf den linken Kindknoten (child).
- Rechts ist der Zeiger auf den rechten Kindknoten (child).
- P ist der Zeiger auf den Elternknoten (parent).
BST-Strukturen werden häufig für verschiedene Suchanfragen verwendet. Andere Baumstrukturen werden zur Erstellung von Ausdruckslösern und in drahtlosen Netzwerken eingesetzt.
7. Heaps
Ein Heap ist ein spezieller Typ eines binären Baums, bei dem die Elternknoten mit ihren Kindknoten verglichen und die Werte entsprechend in den Knoten angeordnet werden.
Ein Heap kann als Array oder Binärbaum dargestellt werden, wie die folgenden Abbildungen zeigen:
Binärbaum-Darstellung
Array-Darstellung
Es gibt zwei Arten von Heaps:
- Das Min-Heap, bei dem der Schlüssel des übergeordneten Elementes gleich oder kleiner als die Schlüssel seiner untergeordneten Elemente ist.
- Das Max-Heap, bei dem der Schlüssel des übergeordneten Elementes größer als die Schlüssel seiner untergeordneten Elemente ist.
Heaps werden häufig verwendet, um die größten und kleinsten Werte in einem Array zu ermitteln und Prioritätswarteschlangen in Algorithmen zu erstellen.
8. Graphen
Ein Graph ist eine nichtlineare und abstrakte Datenstruktur, die aus einer festen (endlichen) Menge von Knoten oder Eckpunkten (vertices) besteht und durch Kanten (edges) verbunden ist. Kanten sind die Bögen oder Linien, die die Knoten im Graphen verbinden.
Graphen eignen sich hervorragend zur Lösung realer Probleme sowie zur Darstellung digitaler Netzwerke. Sie werden auch für die Darstellung von Netzwerken wie Schaltkreis-Netzwerken verwendet.
Was ist ein Algorithmus?
Ein Algorithmus ist eine begrenzte Anzahl an Schritt-für-Schritt-Anweisungen (der Reihe nach geschrieben), um ein bestimmtes Problem zu lösen oder das gewünschte Ergebnis zu erzielen.
Algorithmen werden in der Regel unabhängig von der zugrundeliegenden Sprache entwickelt. Das bedeutet, dass ein Algorithmus in mehreren Programmiersprachen verwendet werden kann.
Wie bereits erwähnt, dienen Datenstrukturen zum Speichern und Organisieren von Daten. Algorithmen lösen Probleme mithilfe dieser Daten.
Hier sind einige Merkmale eines guten Algorithmus:
- Eingabe und Ausgabe eines Algorithmus müssen präzise definiert sein.
- Im Algorithmus muss jeder Schritt klar und eindeutig sein.
- Ein Algorithmus muss die effizienteste Methode zur Lösung eines Problems im Vergleich zu anderen Methoden darstellen.
- Ein Algorithmus sollte so geschrieben sein, dass er auch in anderen Sprachen verwendet werden kann.
Ein Algorithmus ist kein vollständiges Programm oder Code, sondern lediglich die Lösung oder Kernlogik eines Problems, die mithilfe eines Flussdiagramms oder als Pseudocode (einfache Beschreibung mit Schritten) ausgedrückt werden kann.
Eigenschaften eines Algorithmus
Nicht jeder einzelne Prozess (Lösung) kann als Algorithmus betrachtet werden. Ein Algorithmus muss folgende Eigenschaften erfüllen:
- Eindeutigkeit: Ein Algorithmus muss eindeutig und klar sein. Jeder Schritt (Phase), jede Eingabe und Ausgabe muss eindeutig sein und nur eine Bedeutung haben.
- Eingabe: Der Algorithmus sollte null oder mehr Eingaben enthalten.
- Ausgabe: Es sollte mindestens eine Ausgabe geben, die mit der erwarteten Ausgabe übereinstimmt.
- Endlichkeit: Der Algorithmus sollte eine endliche Anzahl von Schritten umfassen.
- Machbarkeit: Der Algorithmus sollte mit den verfügbaren Ressourcen realisierbar sein.
- Unabhängig: Der Algorithmus muss klar definierte Anweisungen haben und unabhängig von Code oder Programm sein.
Ein Algorithmus ist effizient, wenn er eine kürzere Ausführungszeit und weniger Speicherplatz benötigt.
Deshalb wird die Leistung eines Algorithmus anhand folgender Eigenschaften gemessen:
Zeitliche Komplexität
Dies ist die Zeit, die ein Algorithmus während der Ausführung benötigt.
Speicherkomplexität
Dies ist der Speicherplatz, den ein Algorithmus während der Ausführung benötigt.
Algorithmus-typen
Hier sind einige wichtige Kategorien von Algorithmen aus der Sicht der Datenstruktur..
- Suchen: Für die Suche eines Elements in der Datenstruktur.
- Sortieren: Zum Sortieren von Elementen in einer bestimmten (gewünschten) Reihenfolge.
- Einfügen: Für das Hinzufügen/Einfügen von Elementen in die Datenstruktur.
- Aktualisieren: Zum Aktualisieren vorhandener Elemente in der Datenstruktur.
- Löschen: Zum Löschen von Elementen aus der Datenstruktur.
Wie man Algorithmen schreibt
Es gibt keine Standardregel für das Schreiben eines Algorithmus.
Ein Algorithmus wird nie geschrieben, um einen bestimmten Code zu unterstützen. Es gibt einige grundlegende Code-Konstrukte, die in jeder Programmiersprache verwendet werden, wie z. B. Ablaufsteuerung, Schleifen und andere.
Du kannst diese grundlegenden Code Konstrukte zum Schreiben eines Algorithmus verwenden.
Programmierer:innen verwenden zum Schreiben von Algorithmen meist einen Schritt-für-Schritt-Ansatz, der jedoch nicht immer erfolgreich ist.
Jeder Algorithmus muss entsprechend der Problem-Domain geplant und geschrieben werden. Du musst die Problem-Domaine genau verstehen, um einen Algorithmus zur Lösung dieses Problems schreiben zu können.
Beispiel für einen Algorithmus
Hier ist ein Beispiel für einen Algorithmus zum Subtrahieren zweier Zahlen und zur Anzeige des Ergebnisses.
Schritt 1 – START
Schritt 2 – Die drei Ganzzahlen x, y und z festlegen
Schritt 3 – Werte von x und y definieren
Schritt 4 – Werte von x und y subtrahieren
Schritt 5 – Ausgabe von Schritt 4 in z speichern
Schritt 6 – z ausgeben
Schritt 7 – STOP
Derselbe Algorithmus lässt sich auch wie folgt schreiben:
Schritt 1 – START SUBTRACT
Schritt 2 – Werte von x und y ermitteln
Schritt 3 – z ← x - y
Schritt 4 – z ausgeben
Schritt 5 – STOP
Es gibt viele weitere Möglichkeiten, dasselbe Ergebnis (Subtraktion) zu erhalten.
Die Frage ist: Welche Methode oder welcher Algorithmus ist am effizientesten?
In den obigen Beispielen ist die zweite Methode effizienter und nützlicher als die erste. Hier sind die Gründe:
- Der Algorithmus enthält keine unnötigen Definitionen oder Schritte, sodass er für Programmierer:innen leichter zu analysieren ist.
- Außerdem benötigt er weniger Zeit für die Ausführung.
Algorithmen geben Programmierer:innen eine Anleitung zum Erstellen (Coden) eines Programms.
Schlussworte zu grundlegenden Datenstrukturen
Wir haben in diesem Leitfaden die acht gängigsten Datenstrukturen untersucht, die Programmierer:innen kennen sollten, und erklärt, wie man Algorithmen schreibt. Sobald du ein Grundverständnis beider Methoden hast, kannst du sogar das Erstellen neuer Strukturen üben.
Häufig gestellte Fragen
Was sind die wichtigsten Datenstrukturen?
Eine Datenstruktur ist eine Methode zum Speichern und Organisieren von Daten, sodass sie einfach für Operationen verwendet werden kann, um die gewünschten Ergebnisse zu erzielen. Arrays, verknüpfte Listen, Stapel, Warteschlangen, Hash-Tabellen, Bäume, Heaps und Graphen gehören zu den grundlegenden Datenstrukturen.
Was ist die wichtigste Datenstruktur?
Arrays sind die wichtigsten Datenstrukturen, denn viele weitere leiten sich von ihnen ab, wie beispielsweise Stapel und Warteschlangen.
Warum sollte man Datenstrukturen verwenden?
Datenstrukturen organisieren Daten so, dass Operationen mit ihnen einfacher durchgeführt werden können.
Programmierer:innen können durch die Verwendung der richtigen Datenstrukturen viel Zeit sparen und effizienter arbeiten.
Außerdem ist es ohne die Hilfe von Datenstrukturen unmöglich, die effizientesten Algorithmen zu entwickeln.
Wie werden Datenstrukturen klassifiziert?
Datenstrukturen werden in zwei Kategorien eingeteilt: primitive und nicht-primitive Datenstrukturen.
Primitive Datenstrukturen sind grundlegende Datenstrukturen und können direkt gemäß den Anweisungen der Maschine verwendet werden.
Nicht-primitive Datenstrukturen sind komplexere oder fortgeschrittenere Datenstrukturen, die von primitiven Datenstrukturen abgeleitet sind.
Wie werden Datenstrukturen in der Praxis eingesetzt?
Es gibt unzählige Anwendungsmöglichkeiten für Datenstrukturen. Hier sind einige Beispiele für die Anwendung von Datenstrukturen in der Praxis.
- In einem Schachspiel, um die möglichen Züge zu speichern.
- Auf einer Social-Networking-Website (wie Facebook), um die Freundschafts-Informationen zu speichern (d. h. wer mit wem verknüpft ist).
- In einem Internetbrowser, um die Rückschritt-Funktion zu implementieren.
- Und viele mehr…
Sollte ich Datenstrukturen und Algorithmen lernen, bevor ich programmiere?
Du musst Programmieren lernen, bevor du Datenstrukturen und Algorithmen lernst. Du benötigst Grundkenntnisse in der Programmierung, um mit dem Erlernen von DSA (Datenstrukturen und Algorithmen) zu beginnen.
Was ist ein Binärbaum?
Es handelt sich um eine Datenstruktur, in der jeder Datensatz (übergeordneter Knoten) maximal zwei untergeordnete Knoten (auch linker und rechter Knoten genannt) haben kann.
Hast du ein paar Minuten Zeit?
Anmeldedaten suchen, endlose Updates durchführen, Produktkäufe erklären … Nein danke. Wir haben den Hub von GoDaddy Pro entwickelt, damit du durchschnittlich drei Stunden pro Monat für jede von dir betreute Kundenwebsite sparen kannst.
Verleihe dir einen professionellen Auftritt und stärke dein Selbstvertrauen mit einer persönlichen Website, die deine Fähigkeiten und dein Portfolio präsentiert. Hole dir einen Domainnamen, der dich persönlich oder deinen Firmennamen repräsentiert. GoDaddy bietet alle Tools, die du für deinen Erfolg als Unternehmer:in benötigst, darunter Webhosting, Website-Builder und eine professionelle E-Mail-Adresse.
Bildnachweis: Unsplash, Fotograf:in Markus Spiske
