En datastruktur är ett sätt att organisera och lagra data i minnet så att den kan nås och modifieras effektivt. En abstrakt datatyp (ADT) är den logiska modellen — operationerna och deras beteende — oberoende av hur den implementeras.
ADT beskriver operationer som finns; datastrukturen bestämmer de lagras och hur snabbt de körs.
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 | Fråga att ställa |
|---|---|
| Åtkomstmönster | Slumpmässig eller sekventiell åtkomst? |
| Ändringar | Ofta infogning/borttagning i mitten? |
| Ordning | Sorterad, FIFO, LIFO eller ingen? |
| Sökningar | Efter index eller nyckel? |
Rätt val är det vars vanliga operationer är billiga för din arbetsbelastning.
Att välja fel struktur förvandlar en O(1)-operation till O(n), vilket kan göra koden tusentals gånger långsammare i stor skala.
Att tänka i termer av ADT:er låter dig resonera om beteende först, och sedan byta implementeringar senare utan att skriva om anroparna.