LERNLEITFADEN · ETWA 12 MIN LESEZEIT

Datenstrukturen

Wie man Daten speichert, entscheidet, was schnell und was langsam ist. Wählen Sie eine Alltagsaufgabe und sehen Sie, zu welcher Struktur ein Programmierer greifen würde.

StapelJede Änderung wird oben aufgelegt; Rückgängig nimmt die neueste zuerst. Last in, first out.

Was eine Datenstruktur ist, kurz gesagt

Eine Datenstruktur ist eine Art, Daten im Speicher so zu organisieren, dass bestimmte Operationen effizient sind, etwa etwas nachschlagen, hinzufügen oder entfernen. Die Wahl ist ein Kompromiss: Eine Struktur, die Nachschlagen sofort möglich macht, kann das Einfügen verlangsamen oder mehr Speicher brauchen.

Niklaus Wirth fasste ihre Bedeutung im Titel seines Buchs von 1976 zusammen: Algorithms + Data Structures = Programs.

LinearElemente in einer Folge: Arrays, verkettete Listen, Stapel, Warteschlangen.
HierarchischEltern und Kinder: Bäume und Heaps.
VernetztAlles kann mit allem verbunden sein: Graphen.
Mit SchlüsselPer Name statt Position finden: Hashtabellen und Maps.
LINEARE STRUKTUREN

Dieselben Elemente hinein, ein anderes heraus

Fügen Sie beiden Elemente hinzu und entfernen Sie dann eines. Ein Stapel gibt das neueste zurück (last in, first out); eine Warteschlange das älteste (first in, first out).

STAPEL · LIFOpush / pop
ABCOBEN · kommt als Nächstes raus
Rückgängig-Verlauf, die Zurück-Taste des Browsers und der Aufrufstapel, der festhält, welche Funktion welche aufgerufen hat.
WARTESCHLANGE · FIFOenqueue / dequeue
RAUS ←
Akommt als Nächstes rausBC
← REIN
BISHER ENTFERNT
Stapel:-Warteschlange:-
Druckaufträge, Nachrichten, die auf einen Server warten, und die Breitensuche in einem Graphen.
HASHTABELLEN

Direkt zur richtigen Schublade

Eine Hashfunktion macht aus einem Schlüssel eine Fachnummer, sodass man ihn ohne Suchen findet. Unsere addiert die Buchstabencodes und nimmt den Rest nach Division durch 8. Fügen Sie Namen hinzu und achten Sie auf Kollisionen.

N(78) + o(111) + a(97) = 286 → 286 mod 8 = Fach 6
Fach 0
Ana
Fach 1
Fach 2
Fach 3
Fach 4
Fach 5
Ben
Fach 6
Noa
Fach 7
Noch keine Kollisionen. Fügen Sie weitere Namen hinzu: Bei nur 8 Fächern teilen sich bald zwei eines.
BÄUME

Links kleiner, rechts größer

In einem binären Suchbaum enthält der linke Zweig jedes Knotens kleinere Werte und der rechte größere. Jeder Vergleich verwirft die Hälfte des Rests. Wählen Sie einen Wert zum Finden.

503070204060801025354555657590
SUCHPFAD
1. 45 < 50 → nach links2. 45 > 30 → nach rechts3. 45 > 40 → nach rechts4. 45 = 45 ✓ gefunden
4Schritte im Baum
7Schritte in der Liste (der Reihe nach)
KOMPROMISSE

Der Spickzettel

schnellokaylangsam
STRUKTURZUGRIFF PER POSITIONSUCHEEINFÜGENLÖSCHEN
Array
O(1)O(n)O(n)O(n)
Verkettete Liste
O(n)O(n)O(1)O(1)
Stapel
n/aO(n)O(1), nur oberstesO(1), nur oberstes
Warteschlange
n/aO(n)O(1), nur oberstesO(1), nur oberstes
Hashtabelle
n/aO(1)O(1)O(1)
Balancierter BST
O(log n)O(log n)O(log n)O(log n)
Heap
n/aO(n)O(log n)O(log n)
Typische bzw. durchschnittliche Fälle. Hashtabellen können bei vielen Kollisionen zu O(n) entarten; die Baumzeile setzt voraus, dass er balanciert bleibt. „Einfügen“ in ein Array heißt in der Mitte; am Ende anhängen ist meist O(1).

Meilensteine

1945Gespeicherte Programme.Von Neumanns Entwurf legte Daten und Befehle in denselben Speicher und machte Strukturen möglich.
1953Hashing.Hans Peter Luhn bei IBM beschrieb Hashing für schnelles Nachschlagen.
1955Verkettete Listen.Newell, Shaw und Simon nutzten sie im Logic Theorist, einem frühen KI-Programm.
1962Balancierte Bäume.Adelson-Velsky und Landis erfanden den AVL-Baum, der sich selbst ausbalanciert, um schnell zu bleiben.
1964Der Heap.J. W. J. Williams führte den binären Heap ein, zusammen mit Heapsort.

Weiterlesen

Algorithms + Data Structures = ProgramsNiklaus Wirth · 1976
Introduction to AlgorithmsCormen, Leiserson, Rivest & Stein · 1990
Grokking AlgorithmsAditya Bhargava · 2016

Geordnete Daten, geordneter Geist. Testen Sie Ihr Denken.

Unser vollständiger IQ-Test deckt logisches, numerisches, sprachliches und räumliches Denken ab: 60 Fragen, etwa 30 Minuten.

Vollständigen IQ-Test machen