Was ist eine Datenstruktur?

Datenstrukturen kombinieren primitive Datentypen wie Zahlen, Zeichen, boolesche Werte und ganze Zahlen in einem zusammenhängenden Format. Für sich genommen besitzt jeder dieser primitiven Datentypen nur einen einzigen Wert. Wenn sie in einer Datenstruktur kombiniert werden, ermöglichen sie übergeordnete Datenoperationen wie Sortieren, Suchen, Einfügen und Löschen.

Stellen Sie sich zum Beispiel ein Vertriebsteam vor, das tägliche Verkaufszahlen verfolgen möchte. Anstatt jeden Datenpunkt einzeln zu protokollieren, könnte das Team diese Daten in einer Art Datenstruktur speichern, die als „Array“ bezeichnet wird. (Weitere Informationen finden Sie unter „Arten von Datenstrukturen“.)

In Python könnte das Array wie folgt aussehen:

daily_sales = [500, 800, 600, 1200, 950]

Die Verwendung eines Arrays ermöglicht es dem Team, all diese Daten zusammenzuhalten, Datenpunkte bei Bedarf einfach abzurufen und Funktionen sowohl für einzelne Elemente als auch für das gesamte Array auszuführen.

Computerprogrammierer verlassen sich bei der Erstellung effektiver Anwendungen auf Datenstrukturen. In den Bereichen Informatik und Data Science sind Datenstrukturen fürBetriebssysteme, Datenbanken, Websites, Grafiken, Analysen, Blockchain, Anwendungen des maschinellen Lernens (ML) und mehr unerlässlich.

Da Datenstrukturen für das Schreiben von effektivem Code von grundlegender Bedeutung sind, gehören sie oft zu den ersten Lektionen, die Anfängern bei der Programmierung beigebracht werden. Sie sind auch ein häufiges Thema bei Vorstellungsgesprächen für Bewerber im Bereich Computerprogrammierung.

Datenstrukturen sind wichtig, weil sie es Computern erleichtern, große, komplexe Informationsmengen zu verarbeiten. Durch die logische Organisation von Datenelementen erhöhen Datenstrukturen die Effizienz von Computercode und machen den Code leichter verständlich.

Programmierer verwenden Datenstrukturen, um die Geschwindigkeit und Stärke von Algorithmen zu verbessern, bei denen es sich um Anweisungen zur Erledigung einer Rechenaufgabe handelt. In der Computerprogrammierung ist diese Kombination als „DSA“ für „Datenstrukturen und Algorithmen“ bekannt. DSA hilft Programmierern, die beiden Herausforderungen der zeitlichen und räumlichen Komplexität zu bewältigen.

Zeitkomplexität ist ein Maß dafür, wie lange ein Algorithmus benötigt, um eine Aufgabe basierend auf der Eingabemenge zu erledigen. Raumkomplexität ist ein Maß dafür, wie viel Speicher der Algorithmus basierend auf der Eingabemenge verbraucht.

Mit der mathematischen Metrik Big O, der Notation, können Programmierer die räumliche und zeitliche Komplexität messen. Sie können dann ermitteln, welche Datenstrukturen und Algorithmen für eine bestimmte Aufgabe die schnellste Laufzeit und die größte Platzeffizienz bieten.

Datenstrukturen spielen auch eine wichtige Rolle bei der dynamischen Programmierung, einer Technik zur schnellen Lösung komplexer Probleme.

Die dynamische Programmierung verwendet die Rekursion, um ein Problem in kleinere Komponenten zu unterteilen. Dann findet das Programm Lösungen für diese Komponenten und setzt die Unterlösungen wieder zusammen, um eine vollständige Lösung für das ursprüngliche Problem zu erhalten.

Datenstrukturen ermöglichen eine dynamische Programmierung, indem sie dem Programm die Möglichkeit geben, jede Teillösung zu speichern und abzurufen, und indem sie die Datenelemente während des Prozesses logisch organisieren.

Berechnete Werte können beispielsweise in einem Array gespeichert werden. Anstatt diese Werte neu zu berechnen, wenn es an der Zeit ist, die vollständige Lösung zu formulieren, kann das Programm sie aus dem Array abrufen.

Mit diesen Funktionen können Programmierer Zeit sparen und Probleme effizienter lösen.

Datenstrukturen werden in zwei Hauptkategorien unterteilt: lineare und nichtlineare.

In einer linearen Datenstruktur werden die Daten in einer Zeile angeordnet, wobei jedes Datenelement nacheinander angeordnet wird. Diese Anordnung macht es einfach, die Elemente in der richtigen Reihenfolge zu durchlaufen und darauf zuzugreifen.

Lineare Datenstrukturen gelten als unkompliziert und einfach zu implementieren. Zu den gängigen Datenstrukturen in dieser Kategorie gehören Arrays, verknüpfte Listen und Warteschlangen.

In einer nichtlinearen Datenstruktur ist die Organisationslogik etwas anderes als eine lineare, sequentielle Anordnung. So können beispielsweise Datenpunkte hierarchisch angeordnet oder in einem Netzwerk verbunden werden.

Da sie nicht in einer einzigen Linie miteinander verbunden sind, können die Elemente in einer nichtlinearen Struktur nicht alle in einem einzigen Durchlauf durchlaufen und darauf zugegriffen werden, wie dies in einer linearen Datenstruktur möglich ist. Beispiele für nichtlineare Datenstrukturen sind Bäume und Diagramme.

Es gibt verschiedene Arten von Datenstrukturen, die Programmierer verwenden können, je nachdem, welche Systeme sie aufbauen und was sie mit den Daten machen müssen. Zu den gängigen Datenstrukturen gehören:

• Arrays
• Warteschlangen
• Stacks
  
• Verknüpfte Listen
• Bäume
• Graphen
• Hash 

Arrays sind eine der grundlegendsten und am weitesten verbreiteten Arten von Datenstrukturen. Sie speichern Datenelemente ähnlicher Art an benachbarten Speicherorten. Dank dieser Struktur sind Elemente desselben Typs leicht zu finden und zugänglich.

Verwendungszwecke: Zu den üblichen Verwendungszwecken für Arrays gehören das Sortieren, Speichern, Suchen und Zugreifen auf Daten. Arrays können auch als Grundlage für die Implementierung anderer Datenstrukturen wie Warteschlangen und Stack verwendet werden.

Beispiel: Eine Reihe von durchschnittlichen Kundenzufriedenheitswerten eines Call-Centers für jeden Tag könnte so aussehen:

average_customer_score = [4, 3.5, 3.7, 4.1, 3.4, 4.9]

Eine Warteschlangendatenstruktur führt Datenoperationen in einer vorgegebenen Reihenfolge aus, die als „FIFO“ (first in, first out) bezeichnet wird. Das bedeutet, dass das erste Datenelement, das hinzugefügt wird, auch das erste ist, das entfernt wird. Programmierer verwenden diese Datenstruktur häufig, um Prioritätswarteschlangen zu erstellen, die Wartelisten ähneln.

Verwendungen: Warteschlangen-Datenstrukturen können verwendet werden, um den nächsten Song in einer Wiedergabeliste zu bestimmen, den nächsten Benutzer, der Zugriff auf einen gemeinsam genutzten Drucker hat, oder den nächsten Anruf, der in einem Call-Center entgegengenommen wird.

Beispiel: Kunden, die darauf warten, mit einem Cal-Ccenter-Mitarbeiter zu sprechen, könnten in eine solche Warteschlange gestellt werden:

queue = [customer 1, customer 2, customer 3]

Wenn ein Mitarbeiter verfügbar ist, verbindet er sich automatisch mit dem ersten Kunden in der Warteschlange, der dann aus der Liste gestrichen wird. Die Warteschlange sieht nun wie folgt aus:

queue = [customer 2, customer 3]

Ähnlich wie Warteschlangen führt eine Stapeldatenstruktur Datenoperationen in einer vorbestimmten Reihenfolge aus. Anstelle des FIFO-Prinzips wird bei der Stapeldatenstruktur jedoch das LIFO-Format („last in, first out“) verwendet. Das zuletzt hinzugefügte Datenelement wird hierbei als erstes entfernt.

Verwendungen: Stapel können verwendet werden, um das korrekte Öffnen und Schließen von Klammern oder Tags in Computercodes sicherzustellen, den aktuellen Browserverlauf zu verfolgen oder die letzten Operationen in einer Anwendung rückgängig zu machen.

Beispiel: Viele Apps verwenden Stacks, um Benutzeraktionen zu verfolgen, damit diese leicht rückgängig gemacht werden können. Ein Texteditor könnte beispielsweise einen Stack führen, der so aussieht:

recent_actions = [typing ‘.’, space, typing ‘T’]

Wenn ein Benutzer auf die Schaltfläche „Rückgängig machen“ klickt, wird die letzte Aktion im Stapel – „die Eingabe von ,T'“ – rückgängig gemacht. Der Stapel sieht nun wie folgt aus:

recent_actions = [typing ‘.’, space]

Verknüpfte Listen speichern Datenelemente in einer linearen Reihenfolge, wobei jedes Element mit dem nächsten Element in der Liste verbunden ist. Diese Struktur erleichtert das Einfügen neuer Elemente oder das Löschen vorhandener Elemente, ohne die gesamte Datensammlung verschieben zu müssen.

Verwendungszwecke: Verknüpfte Listen werden häufig für häufige Einfügungen und Löschungen in Szenarien verwendet, z. B. für Webbrowser-Verläufe, Media-Player-Wiedergabelisten und das Rückgängigmachen oder Wiederholen von Vorgängen in Anwendungen.

Beispiel: Eine vereinfachte Version einer verknüpften Liste von Videos in einem Media-Player könnte in etwa wie folgt aussehen:

Video 1 – Video 2 – Video 3

Jedes Objekt in der Liste verweist auf das nächste, sodass nach dem Ende von Video 1 der Mediaplayer angewiesen wird, Video 2 zu starten. 

Eine Baumdatenstruktur, die manchmal auch als Präfixbaum bezeichnet wird, ist nützlich, um hierarchische Beziehungen zwischen Datenelementen herzustellen. Ein einzelner übergeordneter Knoten befindet sich an der Spitze der Baumstruktur, wobei sich untergeordnete Unterknoten auf den folgenden Ebenen darunter verzweigen.

Verschiedene Klassen von Bäumen, wie z. B. binäre Suchbäume, AVL-Bäume und b-Bäume, haben unterschiedliche Eigenschaften und unterstützen unterschiedliche Funktionen. In einem binären Suchbaum hat jeder Knoten beispielsweise höchstens 2 untergeordnete Knoten. Diese Struktur unterstützt die schnelle Suche nach Datensätzen. 

Verwendungen: Bäume werden häufig zur Darstellung von Hierarchien in Organisationskarten, Dateisystemen, Domain-Namensystemen, Datenbankindizierung und Entscheidungsbaum in Anwendungen für maschinelles Lernen verwendet.

Beispiel:

Eine Datenstruktur eines Graphen organisiert die Beziehungen zwischen verschiedenen Objekten durch die Verwendung von Scheitelpunkten und Edges. Scheitelpunkte sind Datenpunkte, die durch Punkte „dargestellt“ werden, und Kanten sind Linien, die die Scheitelpunkte verbinden.

Auf einer Karte wären die Städte beispielsweise Eckpunkte und die Straßen, die sie verbinden, wären Edges. Auf Facebook wären die Nutzer Eckpunkte und die Freundschaften, die sie verbinden, Edges.

Verwendung: Graphdatenstrukturen werden häufig mit Suchalgorithmen verwendet, die Daten in komplexen Beziehungsgeflechten suchen. Zu den gängigen Beispielen gehören die Breitensuche, bei der die Daten Ebene für Ebene durchsucht werden, und die Tiefensuche, bei der mehrere Datenebenen per Drilldown durchsucht werden, um Informationen zu finden.

Beispiel:

Eine Hash-Datenstruktur, manchmal auch als „Hash-Tabelle“ oder „Hash-Map“ bezeichnet, verwendet eine Hash-Funktion, um Datenwerte zu speichern. Die Hash-Funktion erstellt einen Hash, bei dem es sich um einen eindeutigen digitalen Schlüssel handelt, der der Position eines bestimmten Datenwerts im Speicher entspricht.

Die Hash-Tabelle enthält einen durchsuchbaren Index jedes Hash- und Datenwertpaars, mit dem Sie schnell und einfach auf Daten zugreifen sowie Daten zur Tabelle hinzufügen und entfernen können.

Benutzungen: Hash-Datenstrukturen können helfen, Daten aus Telefonbüchern, Wörterbüchern und Personalverzeichnissen schnell abzurufen. Sie können auch verwendet werden, um Datenbanken zu indizieren, Passwörter zu speichern und IT-Systeme auszugleichen.

Beispiel: Eine vereinfachte Version einer Hash-Tabelle, die die Kontaktliste eines Smartphones organisiert, könnte in etwa so aussehen:

Die Hash-Funktion ordnet jeden Schlüssel dem entsprechenden Index zu. Wenn ein Benutzer also einen Schlüssel (den Namen eines Kontakts) eingibt, gibt die Hash-Tabelle den zugeordneten Wert am selben Index (die Nummer des Kontakts) zurück.

Datenstrukturen sind für die Entwicklung von Softwareanwendungen von entscheidender Bedeutung, da sie die konkreten Formen abstrakter Datentypen implementieren.

Ein abstrakter Datentyp ist ein mathematisches Modell, das klassifiziert, wie sich ein Datentyp verhält und welche Vorgänge damit ausgeführt werden können. Zum Beispiel definiert der abstrakte Datentyp einer Warteschlange das Verhalten der Warteschlange (nach dem Prinzip von FIFO). Die Warteschlangendatenstruktur bietet eine Möglichkeit, Daten in eine Warteschlange zu formatieren, so dass ein Computerprogramm das FIFO-Prinzip auf diese Daten anwendet.

Viele Programmiersprachen wie Python, Java und JavaScript enthalten integrierte Datenstrukturen, die Entwicklern helfen, effizienter zu arbeiten.

Zu den gängigen Anwendungsfallen für Datenstrukturen in Computerprogrammen gehören:

• Datenspeicher und Unternehmen
• Indizierung
• Datenaustausch
• Suche
• Skalierbarkeit

Datenstrukturen können Daten logisch und effizient mit hoher Datenpersistenz speichern, sodass Daten aus Datenbanken und anderen Anwendungen leicht zugänglich bleiben. Datenstrukturen können auch eine logische Unternehmen für große Datenmengen bieten, sodass diese einfacher sortiert, geordnet und verarbeitet werden können.

Eine Website kann beispielsweise verknüpfte Listen verwenden, um Protokolle der Benutzeraktivität zu speichern. Die Listen können Ereignisse in chronologischer Reihenfolge aufzeichnen, und Verknüpfungen zwischen Ereignissen können dazu beitragen, ein vollständiges Bild davon zu zeichnen, was ein Benutzer während jeder Sitzung tut.  

Datenstrukturen können Informationen indizieren, indem sie Datenwerte den entsprechenden Datenelementen in einer Datenbank zuordnen, was das Auffinden und den Zugriff auf diese Datensätze erleichtert.

Eine E-Commerce-Website verwendet beispielsweise eine Hash-Tabelle, um Produkte in Kategorien zu indizieren. Wenn ein Benutzer nur eine Kategorie anzeigen möchte, kann die Website den Hash-Wert verwenden, um alle zugehörigen Produkte schnell abzurufen, anstatt die Datenbank jedes einzelnen Produkts zu durchsuchen.

Datenstrukturen organisieren Daten, sodass sie problemlos zwischen Anwendungen gemeinsam genutzt werden können. Beispielsweise verwenden viele Apps Warteschlangen, um Pakete über Protokolle wie TCP/IP zu verwalten und zu senden. Warteschlangen tragen dazu bei, dass Pakete in der Reihenfolge gesendet und empfangen werden, in der sie erstellt wurden. 

Datenstrukturen erleichtern die Suche und das Auffinden von Daten, indem sie Daten so organisieren, dass sie für Anwendungen und Endbenutzer leichter verständlich sind.

Beispielsweise können Diagrammdatenstrukturen es Benutzern erleichtern, Personen zu finden, die sie auf Social-Media-Websites kennen. Diagrammdatenstrukturen zeichnen Beziehungen zwischen Scheitelpunkten oder Knoten auf. Suchalgorithmen können Verbindungen von Knoten zu Knoten folgen, um verwandte Benutzer effizient zu finden.

Datenstrukturen unterstützen die Skalierbarkeit von Systemen, indem sie Computerprogrammen helfen, große Datensätze zu verarbeiten, komplexe Probleme zu lösen und Ressourcen effizienter zu nutzen.

So können beispielsweise sowohl Hash-Tabellen als auch Baumstrukturen das Auffinden relevanter Informationen in großen Datensätzen erleichtern. Anstatt jedes Element zu überprüfen, müssen Systeme nur den richtigen Schlüssel verwenden oder dem richtigen Pfad durch den Baum folgen. Dies hilft die Leistung hoch zu halten, da das System nicht viele Ressourcen für die Suche in riesigen Datenmengen aufwenden muss.