Datenstrukturen verstehen

Im Jahr 1976 veröffentlichte Niklaus Wirth ein Buch mit dem Titel 'Algorithmen + Datenstrukturen = Programme.' Selbst im Jahrzehnt der 2020er Jahre hat diese Aussage immer noch Bestand.

Datenstrukturen sind die Anordnung von Daten im Speicher. Sie sind wichtig, um Daten zu organisieren, zu verarbeiten, abzurufen, darauf zuzugreifen und zu speichern.
Datenstrukturen arbeiten normalerweise mit Algorithmen zusammen. Sie halten die Daten, während Algorithmen Probleme mit den Daten lösen.
Datenstrukturen sind eine der Grundlagen der Informatik. Sie sind der Dreh- und Angelpunkt der Programmierung und ein Muss für jeden Programmierer. Wenn du dich für einen Programmierjob bewerben musstest, wirst du feststellen, dass Datenstrukturen einen großen Teil deiner Bewerbungsgespräche ausmachen.
Bei der Softwareentwicklung geht es darum, Probleme zu lösen und die besten Ergebnisse in kürzester Zeit und mit weniger Ressourcen zu erzielen. So wie ein Zimmermann einen Hammer und Nägel braucht, um zu arbeiten, braucht ein Programmierer Datenstrukturen für seinen Job. Das eigentliche Programmieren ist nur ein Aspekt der Arbeit eines Programmierers. Tech-Firmen verbringen viel Zeit damit, die besten Algorithmen zu entwerfen, um Rechenleistung, Serverzeit und Ladezeiten zu sparen. Dadurch sparen sie Zeit und Geld.

Junge, neue Programmierer stürzen sich oft direkt in die Programmierung und in Frameworks, vergessen dabei aber, dass sie für ihre eigentliche Arbeit ein gutes Wissen über Datenstrukturen benötigen. Jedes Problem in der realen Welt hat mit Daten und Operationen mit diesen Daten zu tun. In Vorstellungsgesprächen prüfen gute Personaler, ob ein Interviewpartner seine Probleme mit den besten Algorithmen lösen kann.
Es gibt verschiedene Datenstrukturen für verschiedene Probleme. Wenn du zum Beispiel nach einem bestimmten Wort im Wörterbuch suchen musst, reicht es nicht aus, die Seiten einzeln durchzugehen. Stattdessen suchst du nach dem ersten Buchstaben des gesuchten Wortes und arbeitest dich dann alphabetisch vor. Dies ist ein Beispiel für eine binäre Suche.
Wenn du einen Algorithmus für Linkedin-Verbindungen entwerfen müsstest, bräuchtest du eine Graph-Datenstruktur, um Verbindungen an erster, zweiter oder dritter Stelle zu platzieren.

Datenstrukturen und Datentypen

1. Primitive Datenstrukturen
2. Nicht-primitive Datenstrukturen.

Nicht-primitive Datenstrukturen werden nicht von der Programmiersprache definiert. Sie werden vom Programmierer erstellt und sind von primitiven Datenstrukturen abgeleitet. Sie werden auch 'Referenzvariablen' oder 'Objektreferenzen' genannt, weil sie auf einen Speicherplatz verweisen, der Daten speichert. Nicht-primitive Methoden haben Methoden, die an sie angehängt sind, um Operationen durchzuführen.
Nicht-primitive Datenstrukturen werden weiter in lineare und nicht-lineare Datenstrukturen unterteilt. Lineare Datenstrukturen sind Daten, die sequentiell angeordnet sind. Werte/Datenelemente sind in einer geraden Linie verbunden, egal ob vertikal oder horizontal. Der Zugriff oder die Indizierung auf ein Element erfolgt sequentiell über eine Schleife. Arrays, Stacks, Linked-Lists und Queues sind Beispiele für lineare Datenstrukturen.
Nicht-lineare Datenstrukturen sind in zufälligen oder baumartigen Strukturen angeordnet, wobei die Nodes ein Element mit einem anderen verbinden. Nicht-lineare Datenstrukturen nehmen eine hierarchische Form an und greifen über Knoten und Punkte auf Daten zu. Graphen, Hashtabellen, Bäume und Heap sind Beispiele für nichtlineare Datenstrukturen.
Folgend werfen wir einen detaillierten Blick auf einige Arten von Datenstrukturen und schauen uns an, wie sie funktionieren.

Arrays

Arrays sind die häufigsten und grundlegenden nicht-primitiven Datenstrukturen. In einigen Sprachen wie JavaScript werden sie Arrays genannt, während sie in anderen wie Python als Listen bezeichnet werden. Unabhängig davon, wie sie genannt werden, können sie durch ihre Struktur und Operationen identifiziert werden.
Arrays werden verwendet, um mehrere Werte in einer einzigen Variablen zu speichern. Sie sind normalerweise homogen. Ihre Werte sind in eckigen Klammern eingeschlossen. Jedes Element eines Arrays hat eine Indexnummer, und auf diese Elemente kann mit Hilfe ihrer Indexnummer zugegriffen werden. Array-Indizes beginnen mit 0.
Es gibt zwei Arten von Arrays. Eindimensionale Arrays und mehrdimensionale Arrays. Mehrdimensionale Arrays sind verschachtelte Arrays oder Arrays innerhalb von Arrays. Mehrdimensionale Arrays werden normalerweise verwendet, um Matrizen zu bilden.
Wir könnten die Min- und Max-Werte eines Zahlenbereichs mit einem Array wie diesem in Python finden,

max_min = [5, 10, 19, 4, 3] 
print(max(max_min), min(max_min)) 
# 19 3

Oder auch die Sortierung einer Liste von Namen in auf- oder absteigender Reihenfolge vornehmen.

countries =  ['Ethiopia', 'Uganda', 'Venezuela', 'America', 'Canada'] 
countries.sort() 
print(countries) 
#['America', 'Canada', 'Ethiopia', 'Uganda', 'Venezuela'] 

Hashtabellen

Hashtabellen werden auch Wörterbücher, Suchtabellen, Maps, assoziative Arrays oder Hash genannt. Diese Struktur ist nicht-linear und die Elemente werden in einem Schlüssel/Wert-Paar gespeichert. Die Adresse oder der Indexwert des Datenelements wird aus einer Hash-Funktion generiert.
Hashtabellen unterscheiden sich von Arrays, weil sie statt Indexelementen mit Positionen einen Schlüssel verwenden. Dies ermöglicht ein schnelleres Einfügen und Suchen von Elementen, da auf jedes Element mit seinem Schlüssel zugegriffen wird.
Die Leistung einer Hashtabelle basiert normalerweise auf der Hash-Funktion, der Größe der Hashtabelle und der Methode zur Kollisionsbehandlung. Offensichtliche Beispiele für die Implementierung von Hashtabellen sind Variablen von Telefonbüchern mit Namen/Telefonnummern, die Planung von Terminen/Ereignissen und die Identifizierung von Personen/physikalischen Merkmalen.
Hier ist ein Beispiel für eine Hashtable. Sie enthält die persönlichen Daten einer Person.

name = {"Name":"Alicia", "Surname": "Knowles", "Age":39, "State":"California", "Hair Color":"Black", "Weight": "56kg"} 
#to get the state 
print(name['State']) 

Der Schlüssel ist 'State' und der Wert ist 'California'.

Graph

Dies ist eine nicht-lineare Datenstruktur, die Nodes und Kanten umfasst. Nodes werden auch als Vertices bezeichnet und entsprechen Objekten. Kanten sind die Verbindungen zwischen den Objekten. Graphen werden verwendet, um Beziehungen darzustellen. Ein Graph kann auch ein Gewicht haben - das gibt die Stärke zwischen den einzelnen Verbindungen der Nodes an.
Es gibt zwei Arten von Graphen - gerichtete und ungerichtete Graphen. Ein gerichteter Graph enthält ein geordnetes Paar von Knoten, während ein ungerichteter Graph ein ungeordnetes Paar von Knoten enthält. Ungerichtete Graphen haben keine bestimmte Richtung, um Kanten darzustellen, während gerichtete Graphen eine bestimmte Richtung der Knoten haben. Ungerichtete Graphen haben in der Regel zweiseitige Beziehungen, da die Kanten in beide Richtungen verlaufen können. Gerichtete Graphen haben in der Regel eine einseitige Beziehung und die Kanten können in eine Richtung transversal sein.
Eine reale Implementierung eines Graphen ist die Modellierung der Freunde auf Facebook.
Hier ist ein Graph in Python, der sechs Knoten hat

graph = {
  'A': ['B', 'C'],
  'B': ['C', 'D'], 
  'C': ['D'], 
  'D': ['C'], 
  'E': ['F'], 
  'F': ['C']
}

Dieser Graph wird durch die Adjazenzliste und die Datenstruktur Dictionary (Hashtable) dargestellt. Die Schlüssel sind die Nodes des Graphen.

Stacks und Queues

Stack ist eine Datenstruktur, die man sich als physischen Stapel oder Stapel vorstellen kann. Es ist eine lineare Datenstruktur, bei der Elemente nur an einem Ende entfernt oder hinzugefügt werden. Das Hauptmerkmal von Stacks ist, dass sie LIFO (Last In First Out) unterstützen. Stell dir einen Stack von Tellern vor, die in einer vertikalen Reihenfolge angeordnet sind. Wenn du einen Teller herausnehmen musst, wird der oberste Teller zuerst herausgenommen. Das ist der Teller, der zuletzt platziert wurde. Genau so funktioniert ein Stack. Auf das Element, das zuletzt eingefügt wurde, wird zuerst zugegriffen.
Queue ist eine lineare Datenstruktur wie Stack. Der Unterschied ist aber, dass Queue FIFO (First In First Out) verwendet. Denke an eine Schlange in einem Café. Die erste Person in der Schlange wird zuerst bedient. Jede andere Person stellt sich einfach hinter die letzte Person, die sie sieht. Sowohl Queue als auch Stack greifen auf Elemente in einer sequentiellen Weise zu.
Die Undo, Redo Funktion in den meisten Anwendungen ist ein reales Beispiel für Stack. Benutzeraktionen werden in einem Stack abgelegt und wenn ein Benutzer eine Aktion 'rückgängig' macht, wird die letzte Aktion herausgeschoben. Dein Computer oder Browser behält auch den Überblick über deine "zuletzt gesehenen" Dateien, den Browserverlauf oder Bilder mit Hilfe von Stack.
Queue wird verwendet, um Daten asynchron zu übertragen. Sie wird auch verwendet, um Ressourcen zwischen verschiedenen Prozessen zu teilen, wie z.B. CPU Scheduling, Disk Scheduling, IO Buffer und Keyboard Buffer.
Ein gängiges Beispiel für eine Queue wäre auch der Netzwerkdrucker, der Dokumente von verschiedenen Computern in einer FIFO Weise druckt.
In Python können wir Stacks mit dem deque Modul von Collections erstellen.

from collections import deque 
newstack = deque() 

newstack.append('x') 
newstack.append('y') 
newstack.append('z') 
 
print(newstack) 
#deque(['x', 'y', 'z']) 
 
print(myStack.pop()) 
#z 
print(myStack.pop()) 
#y 
print(myStack.pop()) 
#x 

Operationen auf Datenstrukturen

Verschiedene Operationen können auf Datenstrukturen durchgeführt werden. Dazu gehören:

• Traversieren: Das Aufsuchen jedes Nodes eines Datenstrukturbaumes.
• Einfügen: Einfügen neuer Elemente in die Datenstruktur.
• Deletion (Löschen): Löschen von Elementen aus einer Datenstruktur.
• Suchen: Den Ort eines Elements finden.
• Sortieren: Anordnen von Elementen einer Datenstruktur in einer Art Reihenfolge.
• Merging (Zusammenführen): Zwei sortierte Arrays zu einem einzigen Subarray zusammenfassen.
• Popping: Um Elemente aus einer Struktur zu entfernen.
• Pushing: Um Elemente zu einer Struktur hinzuzufügen.

Datenstrukturen werden auch als statische und dynamische Datenstrukturen klassifiziert. Statische Datenstrukturen haben eine feste Speichergröße und ihr Inhalt kann nicht verändert werden. Die Größe einer statischen Datenstruktur wird zur Kompilierzeit zugewiesen.
Dynamische Datenstrukturen haben eine flexible Speichergröße und sie kann entweder vergrößert oder verkleinert werden. Die Größe wird zur Laufzeit zugewiesen.

ABSCHLIEßENDE WORTE

Datenstrukturen sind das Herzstück der Programmierung. Sie machen den Unterschied zwischen einem schlechten und einem guten System aus. In diesem Artikel haben wir uns auf vier Datenstrukturen konzentriert, als Leitfaden für andere Arten von Datenstrukturen und deren Implementierung.