Një struktura e të dhënave është një mënyrë organizimi dhe ruajtjeje të të dhënave në memorie në mënyrë që ato të jenë të arritshme dhe të modifikohen në mënyrë efikase. Një lloj i të dhënave abstrakt (ADT) është modeli logjik — operacionet dhe sjellja e tyre — i pavarur nga mënyra se si zbatohet.
ADT përshkruan operacione ekzistojnë; struktura e të dhënave vendos ato ruhen dhe sa shpejt ekzekutohen.
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)
| Shqetësim | Pyetja për tu bërë |
|---|---|
| Modeli i qasjes | Qasje rastësore apo radhë? |
| Ndryshimet | Shpesh futje/fshirje në mes? |
| Renditja | E renditur, FIFO, LIFO, apo asnjë? |
| Kërkimet | Sipas indeksit apo sipas çelësi? |
Zgjedhja e duhur është ajo operacionet e zakonshme të së cilës janë të lira për ngarkesën tuaj.
Zgjedhja e gabuar e strukturës e shndërron një operacion O(1) në O(n), i cili mund ta bëjë kodin mijëra herë më të ngadaltë në shkallë.
Mendimi në termat e ADT-ve ju lejon të arsyetoni për sjelljen fillimisht, pastaj të zëvendësoni zbatime më vonë pa rishkruar thirrjeset.