Co je datová struktura a co je abstraktní datový typ (ADT)?

Question

Accepted Answer

**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 vs. implementace

ADT popisuje *jaké* operace existují; datová struktura určuje *jak* jsou uloženy a jak rychle běží.

```text
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
```

## Proč záleží na rozlišení v kódu

```python
# 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)
```

## Výběr struktury

| 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.

## Proč to záleží

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.

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?