📦 Datenstrukturen – der Werkzeugkasten

1. Was ist eine Datenstruktur?

Eine Datenstruktur organisiert Werte und legt fest, welche Operationen sinnvoll möglich sind. Sie beeinflusst, wie leicht Daten gespeichert, gefunden, verändert, durchlaufen und gelöscht werden können.

Datenstruktur und Algorithmus

Ein Algorithmus beschreibt, wie ein Problem gelöst wird. Eine Datenstruktur bestimmt, wie die benötigten Informationen organisiert sind. Beide gehören zusammen: Eine passende Struktur kann einen Algorithmus vereinfachen und beschleunigen.

2. Abstrakter Datentyp und konkrete Umsetzung

Ein abstrakter Datentyp beschreibt erlaubte Werte und Operationen, ohne die interne Speicherung festzulegen. Eine konkrete Datenstruktur setzt dieses Verhalten technisch um.

3. Lineare und nichtlineare Strukturen

Weitere wichtige Eigenschaften

• Geordnet oder ungeordnet
• Eindeutige Werte oder Duplikate
• Feste oder dynamische Größe
• Direkter Indexzugriff oder schrittweises Durchlaufen
• Veränderlich oder unveränderlich

4. Array und dynamische Liste

Ein klassisches Array speichert Elemente in einer geordneten, zusammenhängenden Struktur und ermöglicht direkten Zugriff über einen Index. Viele Hochsprachen bieten zusätzlich dynamische Arrays, deren Kapazität bei Bedarf wächst.

5. Verkettete Liste

Eine verkettete Liste besteht aus Knoten. Jeder Knoten speichert einen Wert und einen Verweis auf den nächsten Knoten; bei einer doppelt verketteten Liste zusätzlich auf den vorherigen.

6. Stack – Last In, First Out

Ein Stack arbeitet nach dem LIFO-Prinzip: Das zuletzt abgelegte Element wird zuerst entfernt. Der Zugriff erfolgt normalerweise nur an der Oberseite.

Typische Anwendungen

• Rückgängig-Funktion in Editoren
• Funktionsaufrufe und Rekursion
• Prüfung verschachtelter Klammern
• Tiefensuche in Bäumen und Graphen
• Zurück-Navigation in einem Ablauf

FÜR jedes zeichen IN text
    WENN zeichen eine öffnende Klammer ist DANN
        stack.push(zeichen)
    SONST WENN zeichen eine schließende Klammer ist DANN
        WENN stack leer ODER oberste Klammer passt nicht DANN
            RÜCKGABE falsch
        ENDE WENN
        stack.pop()
    ENDE WENN
ENDE FÜR

RÜCKGABE stack ist leer

7. Queue und Deque

Eine Queue arbeitet typischerweise nach FIFO: Das zuerst eingereihte Element wird zuerst entfernt. Eine Deque erlaubt Einfügen und Entfernen an beiden Enden.

8. Hash Map und Set

Eine Map ordnet eindeutigen Schlüsseln Werte zu. Ein Set speichert eindeutige Werte ohne Duplikate. Hash-basierte Implementierungen berechnen aus einem Schlüssel eine Position in einer internen Tabelle.

Kollisionen

Unterschiedliche Schlüssel können auf dieselbe Tabellenposition abgebildet werden. Implementierungen lösen solche Kollisionen beispielsweise durch Verkettung oder offene Adressierung.

9. Bäume, Suchbäume und Heap

Ein Baum organisiert Knoten hierarchisch. Der oberste Knoten heißt Wurzel; Knoten können Kinder besitzen. Ein Knoten ohne Kinder wird häufig Blatt genannt.

10. Trie – Präfixbaum für Text

Ein Trie (auch Präfixbaum) speichert Zeichenketten in einer Baumstruktur. Jeder Knoten repräsentiert ein Zeichen, und der Pfad von der Wurzel zu einem Knoten bildet ein Präfix. Er eignet sich besonders für Auto-Vervollständigung, Rechtschreibprüfung und Wörterbuch-Suchen.

11. Graphen

Ein Graph besteht aus Knoten und Kanten. Kanten können gerichtet oder ungerichtet sowie mit einem Gewicht versehen sein.

Adjazenzliste

graph = {
    "Köln":   ["Bonn", "Essen"],
    "Bonn":   ["Köln", "Aachen"],
    "Essen":  ["Köln", "Aachen"],
    "Aachen": ["Bonn", "Essen"]
}

Eine Adjazenzliste speichert zu jedem Knoten seine Nachbarn. Bei dünn besetzten Graphen benötigt sie häufig weniger Speicher als eine vollständige Adjazenzmatrix.

12. Bloom-Filter – probabilistische Struktur

Ein Bloom-Filter ist eine speicher-effiziente, probabilistische Datenstruktur. Er prüft, ob ein Element möglicherweise in einer Menge enthalten ist. Falsch-Positiv ist möglich, aber Falsch-Negativ nicht.

13. LRU-Cache

Ein LRU-Cache (Least Recently Used) speichert eine begrenzte Anzahl von Elementen. Wenn die Kapazität erreicht ist, wird das am längsten nicht verwendete Element entfernt. Er kombiniert eine Hash-Map für schnellen Zugriff mit einer doppelt verketteten Liste für die Reihenfolge.

14. Disjoint Set (Union-Find)

Ein Disjoint Set (auch Union-Find) verwaltet eine Sammlung von disjunkten Mengen. Er unterstützt zwei Operationen: Union (zwei Mengen zusammenführen) und Find (die Menge eines Elements finden).

15. Operationen und typische Laufzeiten

Eine pauschale Bewertung als „schnell“ oder „langsam“ reicht nicht. Entscheidend sind konkrete Operation, Implementierung und Voraussetzungen.

16. Datenstrukturen in Python

Liste, Dictionary und Set

# Dynamische Liste
technologien = ["HTML", "CSS", "Python"]
technologien.append("SQL")

# Dictionary: Schlüssel → Wert
profil = {"name": "Murat", "erfahrung": 15}
profil["stadt"] = "Köln"

# Set: eindeutige Werte
tags = {"Web", "Python", "Web"}
print(tags)  # enthält "Web" nur einmal

Effiziente Queue mit deque

from collections import deque

auftraege = deque(["A-101", "A-102"])
auftraege.append("A-103")     # hinten einreihen

naechster = auftraege.popleft()  # vorne entnehmen
print(naechster)                  # A-101

Häufigkeiten mit einem Dictionary zählen

woerter = ["python", "web", "python", "sql", "web", "python"]
haeufigkeit = {}

for wort in woerter:
    haeufigkeit[wort] = haeufigkeit.get(wort, 0) + 1

print(haeufigkeit)
# {'python': 3, 'web': 2, 'sql': 1}

17. Datenstrukturen in JavaScript

Array, Map und Set

// Dynamisches Array
const technologien = ["HTML", "CSS", "JavaScript"];
technologien.push("SQL");

// Map: Schlüssel dürfen verschiedene Typen besitzen
const profil = new Map();
profil.set("name", "Murat");
profil.set("erfahrung", 15);

// Set: eindeutige Werte
const tags = new Set(["Web", "Python", "Web"]);
console.log(tags.size); // 2

Queue mit Kopfindex

class Queue {
    constructor() {
        this.values = [];
        this.head = 0;
    }

    enqueue(value) {
        this.values.push(value);
    }

    dequeue() {
        if (this.isEmpty()) return undefined;
        const value = this.values[this.head];
        this.head += 1;
        return value;
    }

    isEmpty() {
        return this.head >= this.values.length;
    }
}

18. Interaktives Datenstruktur-Labor

Wähle eine Struktur und führe typische Operationen aus. Das Labor zeigt, wie sich Reihenfolge, Duplikate und Zugriffspunkte unterscheiden.

19. Die passende Datenstruktur auswählen

Beginne nicht mit dem Namen einer Struktur, sondern mit den benötigten Operationen und fachlichen Regeln.

1. 1
   Zugriff bestimmenWird per Position, Schlüssel, Priorität, Reihenfolge oder Beziehung zugegriffen?
2. 2
   Ordnung klärenMuss Einfügereihenfolge, Sortierung oder Hierarchie erhalten bleiben?
3. 3
   Duplikate prüfenSind gleiche Werte erlaubt oder muss jedes Element eindeutig sein?
4. 4
   Änderungsmuster betrachtenWird häufig gelesen, gesucht, am Ende ergänzt oder in der Mitte verändert?
5. 5
   Datenmenge und Speicher bewertenWelche Größen und Wachstumsszenarien sind realistisch?
6. 6
   Einfach starten und messenDie verständlichste passende Struktur wählen und nur bei messbarem Bedarf optimieren.

20. Checkliste für die Wahl einer Datenstruktur

Hake die erledigten Punkte ab. Die Auswahl bleibt nur während dieses Seitenaufrufs erhalten.

0 von 10 Punkten erledigt

21. Häufige Fehler und Lösungen

22. Übungen zum Mitmachen

Löse jede Aufgabe zuerst mit einer Begründung für die gewählte Struktur.

Lösungshinweise

23. Passende nächste Themen

24. Häufige Fragen zu Datenstrukturen