Podatkovna struktura je način organiziranja in shranjevanja podatkov v pomnilnik, tako da so dostopni in spreminjali se učinkovito. Abstraktni podatkovni tip (ADT) je logični model — operacije in njihovo obnašanje — neodvisno od načina implementacije.
ADT opisuje operacije obstajajo; podatkovna struktura odloči so shranjeni in kako hitro se izvajajo.
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)
| Skrb | Vprašanje |
|---|---|
| Vzorec dostopa | Naključni dostop ali zaporedni? |
| Spremembe | Pogosto vstavljanje/brisanje sredi? |
| Urejanje | Razvrščeno, FIFO, LIFO ali nič? |
| Iskanja | Po indeksu ali po ključu? |
Prava izbira je tista, katere pogoste operacije so poceni za vaše delo.
Napačna izbira strukture spremeni O(1) operacijo v O(n), kar lahko naredi kodo tisoče krat počasnejšo v velikem obsegu.
Razmišljanje v smislu ADT-jev omogoča razmišljanje o obnašanju najprej, nato pa zamenjavo implementacij kasneje brez prepisovanja klicateljev.