O structură de date este o modalitate de a organiza și stoca datele în memorie pentru a putea fi accesate și modificate eficient. Un tip de date abstract (ADT) este modelul logic — operațiile și comportamentul lor — independent de modul în care este implementat.
ADT descrie operații există; structura de date decide sunt stocate și cât de repede rulează.
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)
| Preocupare | Întrebare de pus |
|---|---|
| Model de acces | Acces aleator sau secvențial? |
| Mutații | Inserare/ștergere frecventă în mijloc? |
| Ordonare | Sortat, FIFO, LIFO, sau nimic? |
| Căutări | După index sau după cheie? |
Alegerea corectă este cea ale cărei operații comune sunt ieftine pentru sarcina ta.
Alegerea structurii greșite transformă o operație O(1) în O(n), ceea ce poate face codul de mii de ori mai lent la scară.
Gândirea în termeni de ADT te lasă să raționezi mai întâi despre comportament, apoi să schimbi implementările mai târziu fără a rescrie apelantii.