Een gegevensstructuur is een manier om gegevens in het geheugen in te delen en op te slaan zodat deze efficiënt kunnen worden benaderd en gewijzigd. Een abstract gegevenstype (ADT) is het logische model — de bewerkingen en hun gedrag — onafhankelijk van de implementatie.
Het ADT beschrijft bewerkingen bestaan; de gegevensstructuur bepaalt deze worden opgeslagen en hoe snel ze werken.
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)
| Aspect | Vraag om te stellen |
|---|---|
| Toegangspatroon | Willekeurige toegang of sequentieel? |
| Mutaties | Veelvuldig invoegen/verwijderen in het midden? |
| Volgorde | Gesorteerd, FIFO, LIFO of geen? |
| Zoeken | Op index of op sleutel? |
De juiste keuze is degene waarvan de veelvoorkomende bewerkingen goedkoop zijn voor uw werkbelasting.
De verkeerde structuur kiezen verandert een O(1)-bewerking in O(n), wat code op schaal duizenden keren langzamer kan maken.
Denken in termen van ADT's stelt je in staat om eerst over gedrag na te denken, en later implementaties uit te wisselen zonder callers opnieuw te schrijven.