Struktura danych to sposób organizowania i przechowywania danych w pamięci, aby można było do nich efektywnie uzyskać dostęp i je modyfikować. Abstrakcyjny typ danych (ADT) to model logiczny — operacje i ich zachowanie — niezależnie od sposobu ich implementacji.
ADT opisuje operacje istnieją; struktura danych decyduje są przechowywane i jak szybko działają.
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 | Pytanie do zadania |
|---|---|
| Wzór dostępu | Dostęp losowy czy sekwencyjny? |
| Mutacje | Częste wstawianie/usuwanie w środku? |
| Porządkowanie | Posortowane, FIFO, LIFO, czy brak? |
| Wyszukiwania | Po indeksie czy po kluczu? |
Właściwy wybór to ten, którego operacje powszechne są tanie dla Twojego obciążenia.
Wybór złej struktury zmienia operację O(1) w O(n), co może sprawić, że kod będzie działał tysiące razy wolniej na dużą skalę.
Myślenie w kategoriach ADT pozwala najpierw rozumować o zachowaniu, a następnie wymieniać implementacje bez przepisywania komentatorów.