Datová struktura je způsob, jak organizovat a ukládat data v paměti, aby byla efektivně přístupná a modifikovatelná. Abstraktní datový typ (ADT) je logický model — operace a jejich chování — nezávisle na tom, jak je implementován.
ADT popisuje operace existují; datová struktura určuje jsou uloženy a jak rychle běží.
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 | Otázka, kterou si položit |
|---|---|
| Vzor přístupu | Náhodný přístup nebo sekvenční? |
| Mutace | Časté vkládání/mazání uprostřed? |
| Řazení | Seřazeno, FIFO, LIFO, nebo nic? |
| Vyhledávání | Podle indexu nebo podle klíče? |
Správná volba je ta, jejíž běžné operace jsou levné pro vaši úlohu.
Volba špatné struktury změní operaci O(1) na O(n), což může na velkém měřítku zpomalit kód tisíckrát.
Myšlení z hlediska ADT vám umožňuje nejdřív uvažovat o chování, poté později vyměňovat implementace bez přepsání volajících.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět