Ep. 46 – Dátové štruktúry

Dátové štruktúry sú základným stavebným prvkom programovania. Predstavujú rôzne spôsoby reprezentácie dát. Opíšeme si najzákladnejšie dátové štruktúry a rozdiely medzi nimi. Keďže sme sa o dátových štruktúrach celkom rozkecali, tak algoritmy spomínať nebudeme, to až v ďalšej epizóde.

Stiahnuť

(00:00 – 02:34) – Úvod
(02:35 – 05:58) – Čo su dátové štruktúry?
(05:59 – 12:38) – Pole (Arrayy)
(12:39 – 19:45) – Zreťazený zoznam (Linked list)
(19:46 – 27:43) – Hash set
(27:44 – 32:33) – Hash map / Dictionary
(32:34 – 35:16) – Zásobník (Stack)
(35:17 – 37:25) – Rada (Queue)
(37:26 – 43:06) – Graf
(43:07 – 44:58) – Strom
(44:59 – 46:46) – Nečakaná zmena plánov
(46:47 – 47:24) – Záver

Pole (Array)

• Skupina prvkov (väčšinou toho istého typu)
• Ku prvkom pristupujeme podľa indexov (indexy väčšinou začínajú od 0)
• Statická / Nemeniteľná veľkosť

LIST

• To isté ako pole, ale veľkosť je dynamická

Zreťazený zoznam (Linked List)

• Reprezentuje sekvenciu uzlov (nodes)
• Každý node obsahuje svoju hodnotu (môže byť čokoľvek) a referenciu na ďalší node
• Referenciu môže obsahovať aj na predošlí node, vtedy je zoznam obojsmerný (inak jednosmerný)
• Konštantná O(1) zložitosť vkladania/odstraňovania prvkov.

Hash Mapa / Dictionary

• Mapuje kľúče na hodnoty
• Používa hashovaciu funkciu na kľúče
• Konštantná O(1) zložitosť prístupu k prvkom podľa key

Zásobník (stack)

• LIFO (last-in first-out)
• Vieme si to predstaviť ako taniere – posledný vložený na kopu bude použitý ako prvý
• Obsahuje funkcie:
  • pop() – odstráni prvok na vrchole
  • push(item) – pridá prvok na vrchol
  • peek() – vráti prvok na vrchole (neodstraňuje)
  • isEmpty()

Rad (Queue)

• FIFO (first-in first-out)
• Vieme si to predstaviť ako rad v obchode- prvý čo sa postaví do radu bude aj prvý obslúžený
• Obsahuje funkcie:
  • remove() – odstráni prvok na vrchole
  • add(item) – pridá prvok na koniec
  • peek() – vráti prvok na vrchole (neodstraňuje)
  • isEmpty()

Graf

• Má vrcholy a hrany. Hranami sa spájajú jednotlivé vrcholy
• Pomocou tejto dátovej štruktúry sa rieši mnoho problémov z reálneho života (napr. Google maps, Sociálne siete)
• Susedia vrcholu (alebo nazývame aj node) A, sú všetky vrcholy, ktoré majú s vrcholom A spojenie
• Spojenia/Hrany môzu byť orientované alebo neorientované
• Môže obsahovať cykly, vtedy je graf cyklický (inak acyklický)

Strom

• Stromy sú typy grafov
• Každý strom ma root node (prvý node na vrchole stromu)
• Každý node ma 0 alebo N detí (child nodes)
• Binárny strom je typ stromu, v ktorom každý node ma 0 až 2 detí
• Binárny vyhľadávací strom je taký, v ktorom platí usporiadané také, že pre každý node platí, že naľavo od tohto node sú prvky menšie a napravo väčšie