Datenstrukturen – Array, Tree, Graph & Hash Table

Inhaltsverzeichnis

Schnellübersicht

Auf dieser Seite lernen Sie alles über Datenstrukturen in der Programmierung:

Definition: Was sind Datenstrukturen und warum sind sie wichtig?
Lineare Strukturen: Array, Linked List, Stack, Queue
Nicht-lineare Strukturen: Tree, Graph, Hash Table, Heap
Visualisierungen: Wie sehen Datenstrukturen aus?
Big O Komplexität: Zeit- und Speicheraufwand im Vergleich
Einsatzgebiete: Wo werden welche Strukturen verwendet?
FAQ: Häufige Fragen zu Datenstrukturen

1. Was sind Datenstrukturen?

Definition

Eine Datenstruktur ist eine spezielle Art, Daten in einem Computer zu organisieren, zu speichern und zu verwalten. Sie definiert, wie Daten miteinander in Beziehung stehen und welche Operationen (Einfügen, Löschen, Suchen, Sortieren) effizient durchgeführt werden können.

Die Wahl der richtigen Datenstruktur ist entscheidend für die Performance eines Programms. Eine ungeeignete Datenstruktur kann dazu führen, dass ein Programm langsam wird oder zu viel Speicher verbraucht. Die richtige Datenstruktur kann dagegen Operationen von Stunden auf Millisekunden beschleunigen.

Die zwei Hauptkategorien: Lineare Datenstrukturen (Elemente in einer Sequenz: Array, List, Stack, Queue) und Nicht-lineare Datenstrukturen (Elemente in einer Hierarchie oder einem Netzwerk: Tree, Graph, Hash Table).

             Warum sind Datenstrukturen so wichtig?
            Effizienz: Die richtige Struktur beschleunigt Operationen um den Faktor 1000+
Speichernutzung: Manche Strukturen sind speichereffizienter als andere
Wartbarkeit: Gut organisierte Daten sind leichter zu verstehen und zu ändern
Skalierbarkeit: Mit wachsenden Datenmengen wird die Wahl immer wichtiger
Interviews: Datenstrukturen sind Standard-Thema in technischen Vorstellungsgesprächen
Algorithmen: Viele Algorithmen basieren auf spezifischen Datenstrukturen

        

2. Lineare Datenstrukturen

Bei linearen Datenstrukturen sind die Elemente in einer Sequenz angeordnet. Jedes Element hat einen Vorgänger und einen Nachfolger (außer dem ersten und letzten).

01

Array

Kontinuierlicher Speicher · Feste Größe

Eine Sammlung von Elementen gleichen Typs, die in zusammenhängendem Speicher gespeichert werden. Zugriff über Index (0-basiert).

Zugriff: O(1) – extrem schnell über Index
Suche: O(n) – linear, oder O(log n) wenn sortiert
Einfügen/Löschen: O(n) – Elemente müssen verschoben werden
Größe: Fest (statisch) oder dynamisch (mit Resizing)
Vorteil: Cache-freundlich, schneller Zugriff

Typische Anwendung: Bilder (Pixel-Arrays), Tabellen, Puffer, Matrix-Operationen

02

Linked List

Verkettete Liste · Dynamische Größe

Jedes Element (Node) enthält Daten und einen Zeiger auf das nächste Element. Kein zusammenhängender Speicher nötig.

Zugriff: O(n) – sequentiell, kein direkter Index
Suche: O(n) – linear
Einfügen/Löschen: O(1) – wenn Position bekannt
Größe: Dynamisch – wächst und schrumpft
Varianten: Einfach, Doppelt, Zirkulär

Typische Anwendung: Implementierung von Stack/Queue, Musik-Playlists, Undo-Funktionen

03

Stack

LIFO – Last In, First Out

Ein Stapel, bei dem das zuletzt eingefügte Element zuerst entfernt wird. Wie ein Stapel Teller – oben drauflegen, oben wegnehmen.

Push: Element oben drauflegen – O(1)
Pop: Oberstes Element entfernen – O(1)
Peek: Oberstes Element ansehen – O(1)
Prinzip: LIFO (Last In, First Out)
Implementierung: Array oder Linked List

Typische Anwendung: Funktionsaufrufe (Call-Stack), Undo/Redo, Browser-History, Klammer-Prüfung

04

Queue

FIFO – First In, First Out

Eine Warteschlange, bei der das zuerst eingefügte Element zuerst entfernt wird. Wie eine Schlange im Supermarkt.

Enqueue: Hinten anstellen – O(1)
Dequeue: Vorne entfernen – O(1)
Peek: Vorderstes Element ansehen – O(1)
Prinzip: FIFO (First In, First Out)
Varianten: Priority Queue, Deque, Circular Queue

Typische Anwendung: Druckwarteschlangen, Task-Scheduling, BFS-Algorithmus, Message Queues

3. Visualisierungen

So sehen die wichtigsten Datenstrukturen in der Praxis aus:

Datenstrukturen visuell

Array (Index-basiert)

[0] A

[1] B

[2] C

[3] D

[4] E

Zusammenhängender Speicher · Direkter Zugriff über Index

Stack (LIFO)

Top → E (zuletzt rein)

D

C

B

A (zuerst rein)

Push: Oben drauf · Pop: Oben weg · LIFO-Prinzip

Queue (FIFO)

Front → A

B

C

D ← Rear

Enqueue: Hinten anstellen · Dequeue: Vorne entfernen · FIFO-Prinzip

Binary Search Tree

Root: 8

4

12

2

6

10

14

Hierarchische Struktur · Links kleiner, rechts größer

4. Nicht-lineare Datenstrukturen

Bei nicht-linearen Datenstrukturen sind die Elemente in einer Hierarchie oder einem Netzwerk angeordnet. Ein Element kann mehrere Nachfolger haben.

05

Tree

Hierarchische Struktur · Parent-Child

Eine Baumstruktur mit einer Wurzel (Root) und Kind-Knoten. Jeder Knoten hat maximal einen Parent.

Binary Tree: Max. 2 Kinder pro Knoten
BST: Binary Search Tree – sortiert
AVL/Red-Black: Selbst-balancierend
Suche: O(log n) bei balancierten Bäumen
Traversal: Inorder, Preorder, Postorder

Typische Anwendung: Dateisysteme, DOM (HTML), Entscheidungsbäume, Datenbanken (B-Tree)

06

Graph

Netzwerk · Knoten & Kanten

Eine Sammlung von Knoten (Vertices) und Kanten (Edges), die Beziehungen zwischen Objekten darstellen.

Gerichtet/Ungerichtet: Einbahnstraße oder beide Richtungen
Gewichtet: Kanten haben Kosten/Distanz
Algorithmen: Dijkstra, BFS, DFS, A*
Repräsentation: Adjazenzmatrix oder Adjazenzliste
Zyklen: Zyklisch oder azyklisch (DAG)

Typische Anwendung: Soziale Netzwerke, Navigation (Google Maps), Routenplanung, Empfehlungssysteme

07

Hash Table

Schlüssel-Wert-Paare · O(1) Lookup

Speichert Schlüssel-Wert-Paare und nutzt eine Hash-Funktion, um den Speicherort zu berechnen. Extrem schneller Zugriff.

Zugriff: O(1) durchschnittlich
Einfügen: O(1) durchschnittlich
Kollisionen: Chaining oder Open Addressing
Load Factor: Verhältnis Einträge/Größe
Implementierungen: dict (Python), HashMap (Java), Object (JS)

Typische Anwendung: Caching, Datenbank-Indizes, Symbol-Tabellen, Wörterbücher, Session-Speicher

08

Heap

Prioritäts-Warteschlange · Min/Max

Ein spezieller Binary Tree, bei dem der Parent immer größer (Max-Heap) oder kleiner (Min-Heap) als seine Kinder ist.

Max-Heap: Größtes Element an der Wurzel
Min-Heap: Kleinstes Element an der Wurzel
Insert: O(log n)
Extract-Min/Max: O(log n)
Peek: O(1) – Wurzel ansehen

Typische Anwendung: Priority Queues, Heapsort, Dijkstra-Algorithmus, Task-Scheduling

5. Big O Komplexität im Vergleich

Die Big O Notation beschreibt, wie die Laufzeit oder der Speicherbedarf eines Algorithmus mit der Eingabegröße wächst.

Datenstruktur	Zugriff	Suche	Einfügen	Löschen	Speicher
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1)	O(1)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)	O(n)
Queue	O(n)	O(n)	O(1)	O(1)	O(n)
BST (balanciert)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Hash Table	O(1)	O(1)	O(1)	O(1)	O(n)
Heap	O(1) (Peek)	O(n)	O(log n)	O(log n)	O(n)
Graph	O(V+E)	O(V+E)	O(1)	O(V+E)	O(V+E)

Big O Legende

O(1) – Konstant: Immer gleich schnell, unabhängig von der Datenmenge
O(log n) – Logarithmisch: Sehr effizient, z.B. binäre Suche
O(n) – Linear: Wächst proportional zur Datenmenge
O(n²) – Quadratisch: Langsam bei großen Datenmengen (z.B. Bubble Sort)

Hinweis: Die Angaben in der Tabelle beziehen sich auf den Durchschnittsfall. Im schlechtesten Fall (Worst Case) können die Werte abweichen – z.B. Hash Table O(n) bei vielen Kollisionen.

6. Einsatzgebiete in der Praxis

Welche Datenstruktur wird wo in der realen Software-Entwicklung eingesetzt?

Web-Entwicklung

DOM-Baum (Tree) für HTML-Struktur, Hash Tables für Session-Speicher und Caching, Arrays für Listen.

Tree · Hash Table · Array

Datenbanken

B-Trees und B+Trees für Indizes, Hash Tables für Joins, Heaps für Sortierung.

B-Tree · Hash Table · Heap

Spiele-Entwicklung

Graphen für Pfadfindung (A*), Quadtrees für Kollisionserkennung, Arrays für Spielfelder.

Graph · Quadtree · Array

Betriebssysteme

Queues für Prozess-Scheduling, Stacks für Funktionsaufrufe, Heaps für Speicherverwaltung.

Queue · Stack · Heap

Netzwerke

Graphen für Routing-Tabellen, Queues für Paket-Puffer, Hash Tables für ARP-Cache.

Graph · Queue · Hash Table

KI & Machine Learning

Arrays/Matrizen für Tensor-Operationen, Graphen für neuronale Netze, Heaps für Top-K-Abfragen.

Array · Graph · Heap

             Faustregel für die Wahl der Datenstruktur
            Häufiger Zugriff über Index? → Array
Häufiges Einfügen/Löschen? → Linked List
LIFO-Prinzip? → Stack
FIFO-Prinzip? → Queue
Hierarchische Daten? → Tree
Beziehungen/Netzwerke? → Graph
Schneller Key-Value-Lookup? → Hash Table
Min/Max schnell finden? → Heap

        

7. FAQ – Häufige Fragen & Antworten

Häufige Fragen zu Datenstrukturen

Was ist der Unterschied zwischen Array und Linked List?

Die wichtigsten Unterschiede:

Speicher: Array = zusammenhängend, Linked List = verteilt
Zugriff: Array = O(1) über Index, Linked List = O(n) sequentiell
Einfügen/Löschen: Array = O(n) (Verschieben), Linked List = O(1) (wenn Position bekannt)
Größe: Array = fest (oder Resizing), Linked List = dynamisch
Cache: Array = cache-freundlich, Linked List = cache-ineffizient

Faustregel: Array für häufigen Lesezugriff, Linked List für häufiges Einfügen/Löschen.

Wann sollte ich einen Stack statt einer Queue verwenden?

Das hängt vom gewünschten Verarbeitungsprinzip ab:

Stack (LIFO): Wenn das zuletzt hinzugefügte Element zuerst verarbeitet werden soll. Beispiele: Undo-Funktion, Browser-Zurück-Button, Klammer-Prüfung, rekursive Algorithmen.
Queue (FIFO): Wenn das zuerst hinzugefügte Element zuerst verarbeitet werden soll. Beispiele: Druckwarteschlange, Task-Scheduling, BFS-Algorithmus, Message Queues.

Was ist der Unterschied zwischen einem Binary Tree und einem Binary Search Tree (BST)?

Binary Tree: Jeder Knoten hat maximal 2 Kinder. Es gibt keine Sortierung – die Kinder können beliebige Werte haben.

Binary Search Tree (BST): Ein Binary Tree mit einer zusätzlichen Regel: Alle Werte im linken Teilbaum sind kleiner, alle im rechten Teilbaum sind größer als der Parent. Dies ermöglicht effiziente Suche in O(log n).

Problem: Ein BST kann degenerieren (z.B. bei sortierter Eingabe) und zu O(n) werden. Lösung: Selbst-balancierende Bäume wie AVL oder Red-Black Tree.

Warum ist eine Hash Table so schnell?

Eine Hash Table nutzt eine Hash-Funktion, die einen Schlüssel (z.B. einen String) in einen numerischen Index umwandelt. Dieser Index zeigt direkt auf den Speicherort des Werts – daher O(1) Zugriff.

Beispiel: hash("name") → 42 → Speicher[42] = "Max Mustermann"

Herausforderung: Kollisionen (zwei Schlüssel → gleicher Index). Lösungen: Chaining (Linked List an jedem Index) oder Open Addressing (nächster freier Platz).

Welche Datenstruktur ist am besten für Anfänger?

Empfohlene Reihenfolge für Anfänger:

Array: Einfachstes Konzept, in jeder Sprache vorhanden
Stack & Queue: Einfache Prinzipien (LIFO/FIFO)
Hash Table: Dict/Map in Python/Java – sehr praktisch
Linked List: Zeiger-Konzept verstehen
Tree: Rekursion und Hierarchien
Graph: Komplexeste Struktur, zuletzt lernen

Was ist der Unterschied zwischen einem Graph und einem Tree?

Tree: Ein spezieller Graph mit folgenden Einschränkungen:

Genau eine Wurzel (Root)
Jeder Knoten hat genau einen Parent (außer Root)
Keine Zyklen
Zusammenhängend

Graph: Allgemeiner – kann Zyklen haben, mehrere Verbindungen, keine Hierarchie erforderlich. Jeder Tree ist ein Graph, aber nicht jeder Graph ist ein Tree.

Was bedeutet O(log n) und warum ist es so effizient?

O(log n) bedeutet, dass sich die Laufzeit nur minimal erhöht, wenn die Datenmenge wächst. Bei jeder Operation wird die Suchmenge halbiert.

Beispiel: Binäre Suche in 1.000.000 Elementen braucht maximal ~20 Schritte (log₂ 1.000.000 ≈ 20). Zum Vergleich: Lineare Suche (O(n)) bräuchte bis zu 1.000.000 Schritte.

Typische O(log n) Algorithmen: Binäre Suche, BST-Operationen, Heap-Operationen, Merge Sort.

Wie wähle ich die richtige Datenstruktur für mein Projekt?

Stellen Sie sich folgende Fragen:

Welche Operationen brauche ich am häufigsten? (Lesen, Schreiben, Suchen, Sortieren)
Wie viele Daten habe ich? (100 Elemente vs. 100 Millionen)
Ändern sich die Daten oft? (statisch vs. dynamisch)
Brauche ich eine bestimmte Reihenfolge? (sortiert, FIFO, LIFO)
Wie sieht die Datenstruktur aus? (linear, hierarchisch, vernetzt)

Tipp: Im Zweifel mit der einfachsten Struktur beginnen (Array/Hash Table) und bei Bedarf optimieren.

Zusammenfassung

             Die wichtigsten Punkte
            Lineare Strukturen: Array (schneller Zugriff), Linked List (flexibles Einfügen), Stack (LIFO), Queue (FIFO)
Nicht-lineare Strukturen: Tree (Hierarchie), Graph (Netzwerk), Hash Table (Key-Value), Heap (Priorität)
Big O: Beschreibt die Effizienz – O(1) am besten, O(n²) am schlechtesten
Hash Table: Schnellste Struktur für Key-Value-Lookup (O(1) durchschnittlich)
Tree: Ideal für hierarchische Daten und sortierte Suche (O(log n))
Graph: Für Beziehungen und Netzwerke (Navigation, Social Media)
Wahl: Hängt von den häufigsten Operationen und der Datenmenge ab
Praxis: Im Zweifel einfach beginnen und bei Bedarf optimieren

        

Weiterführende Themen

Algorithmen

Sortier- und Suchalgorithmen, Graph-Algorithmen, dynamische Programmierung.

Zu Algorithmen

Programmiersprachen

Wie Datenstrukturen in verschiedenen Sprachen implementiert werden.

Zu Programmiersprachen

Design Patterns

Entwurfsmuster für wiederverwendbare Software-Architekturen.

Zu Design Patterns

Datenbank-Grundlagen

B-Trees, Indizes und Datenstrukturen in Datenbanksystemen.

Zu Datenbanken