Eine Datenstruktur ist eine Möglichkeit, Daten im Speicher zu organisieren und zu speichern, damit sie effizient zugegriffen und modifiziert werden können. Ein abstrakter Datentyp (ADT) ist das logische Modell — die Operationen und ihr Verhalten — unabhängig davon, wie es implementiert ist.
Der ADT beschreibt Operationen es gibt; die Datenstruktur entscheidet sie gespeichert werden und wie schnell sie laufen.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Aspekt | Frage |
|---|---|
| Zugriffsmuster | Zufällige oder sequenzielle Zugriffe? |
| Mutationen | Häufiges Einfügen/Löschen in der Mitte? |
| Reihenfolge | Sortiert, FIFO, LIFO oder keine? |
| Lookups | Nach Index oder nach Schlüssel? |
Die richtige Wahl ist diejenige, bei der häufige Operationen billig für Ihre Workload sind.
Die Wahl der falschen Struktur verwandelt eine O(1)-Operation in O(n), was Code in großem Maßstab tausendfach verlangsamen kann.
Denken in Begriffen von ADT's ermöglicht es dir, zuerst über Verhalten zu argumentieren, dann später Implementierungen auszutauschen, ohne Aufrufer umzuschreiben.