Mi az adatstruktúra és mi az absztrakt adattípus (ADT)?

Question

IT Interview Practice · Accepted Answer

Az **adatstruktúra** a memóriában lévő adatok szervezésének és tárolásának módja, hogy hatékonyan elérhessék és módosíthassák azokat. Az **absztrakt adattípus (ADT)** a *logikai modell* — a műveletek és azok viselkedése — függetlenül attól, hogy hogyan van megvalósítva.

## ADT vs implementation

Az ADT leírja, *mely* műveletek léteznek; az adatstruktúra azt határozza meg, *hogyan* tárolódnak, és milyen gyorsan futnak.

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

A helyes választás az, amelynek **gyakori műveletei olcsóak** az Ön munkaterheléséhez.

## Miért számít ez

A helytelen struktúra kiválasztása egy O(1) műveletet O(n)-re alakít, amely nagy léptékben ezerszer lassabbá teheti a kódot.

Az ADT-k szempontjából való gondolkodás lehetővé teszi, hogy először a *viselkedésről* gondolkodjunk, majd később az implementációkat lecserélhessük anélkül, hogy újra kellene írni a hívókat.

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?

ADT vs implementation

Why the distinction matters in code

Choosing a structure

Miért számít ez

Kapcsolódó kérdések