En datastruktur er en måte å organisere og lagre data i minnet på slik at det kan nås og endres effektivt. En abstrakt datatype (ADT) er den logiske modellen — operasjonene og deres oppførsel — uavhengig av hvordan den implementeres.
ADT beskriver operasjoner som finnes; datastrukturen bestemmer de lagres og hvor raskt de kjø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)
| Forhold | Spørsmål å stille |
|---|---|
| Tilgangsmønster | Tilfeldig tilgang eller sekvensielt? |
| Mutasjoner | Hyppig innsetting/sletting i midten? |
| Rekkefølge | Sortert, FIFO, LIFO eller ingen? |
| Oppslag | Etter indeks eller nøkkel? |
Det riktige valget er det hvis vanlige operasjoner er billige for arbeidsmengden din.
Å velge feil struktur gjør at en O(1)-operasjon blir O(n), som kan gjøre koden tusenvis av ganger saktere i stor skala.
Å tenke i termer av ADT-er lar deg resonnere om oppførsel først, deretter bytte implementasjoner senere uten å skrive om kallerene.