En datastruktur er en måde at organisere og gemme data i hukommelsen på, så det kan tilgås og ændres effektivt. En abstrakt datatype (ADT) er den logiske model — operationerne og deres adfærd — uafhængig af hvordan det implementeres.
ADT beskriver operationer der findes; datastrukturen bestemmer de gemmes og hvor hurtigt de kører.
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)
| Hensyn | Spørgsmål at stille |
|---|---|
| Adgangsmønster | Tilfældig adgang eller sekventiel? |
| Mutationer | Hyppige indsættelser/sletninger i midten? |
| Rækkefølge | Sorteret, FIFO, LIFO, eller ingen? |
| Opslag | Efter indeks eller efter nøgle? |
Det rigtige valg er det, hvis almindelige operationer er billige for din arbejdsbyrde.
At vælge den forkerte struktur omdanner en O(1)-operation til O(n), hvilket kan gøre koden tusinder af gange langsommere i stor skala.
At tænke i termer af ADT'er lader dig ræsonnere om adfærd først, derefter udskifte implementeringer senere uden at omskrive opkald.