Tietorakenne on tapa järjestää ja varastoida tietoja muistissa niin, että niitä voidaan käyttää ja muokata tehokkaasti. Abstrakti tietotyyppi (ADT) on looginen malli — operaatiot ja niiden käyttäytyminen — riippumatta siitä, miten se toteutetaan.
ADT kuvaa operaatioita on olemassa; tietorakenne päättää ne tallennetaan ja kuinka nopeasti ne suoritetaan.
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)
| Huomio | Kysymys joita kysyä |
|---|---|
| Pääsymalli | Satunnaisesti vai peräkkäin? |
| Muutokset | Usein lisääminen/poistaminen keskeltä? |
| Järjestys | Järjestetty, FIFO, LIFO vai ei mitään? |
| Haut | Indeksin tai avaimen perusteella? |
Oikea valinta on sellainen, jonka yleiset operaatiot ovat halvat työmäärällesi.
Väärän rakenteen valinta muuttaa O(1)-operaation O(n)-operaatioksi, mikä voi tehdä koodista tuhansia kertoja hitaamman suuremmassa mittakaavassa.
ADT:n kannalta ajattelu antaa sinun perustella käyttäytymistä ensin ja sitten vaihtaa toteutuksia myöhemmin ilman, että joudut kirjoittamaan kutsujia uudelleen.