Što je struktura podataka i što je apstraktni tip podataka (ADT)?

Question

Accepted Answer

**Struktura podataka** je način organizacije i pohrane podataka u memoriji tako da se mogu učinkovito pristupiti i izmijeniti. **Apstraktni tip podataka (ADT)** je *logički model* — operacije i njihovo ponašanje — neovisno o tome kako je implementiran.

## ADT vs implementation

ADT opisuje *koje* operacije postoje; struktura podataka odlučuje *kako* se pohranjuju i koliko brzo se izvršavaju.

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

## Why the distinction matters in code

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

## Choosing a structure

| Concern | Question to ask |
|---|---|
| Access pattern | Random access or sequential? |
| Mutations | Frequent insert/delete in the middle? |
| Ordering | Sorted, FIFO, LIFO, or none? |
| Lookups | By index or by key? |

Ispravan izbor je onaj čije su **česte operacije jeftine** za vašu radnu opterećenja.

## Zašto je to važno

Odabir pogrešne strukture pretvara O(1) operaciju u O(n), što može učiniti kod hiljadu puta sporijim u skali.

Razmišljanje u smislu ADT-a omogućava vam da prvo razmislite o *ponašanju*, a zatim kasnije zamijenite implementacije bez ponovnog pisanja pozivajućih funkcija.

Concern	Question to ask
Access pattern	Random access or sequential?
Mutations	Frequent insert/delete in the middle?
Ordering	Sorted, FIFO, LIFO, or none?
Lookups	By index or by key?