Zhrnutie na Základy informatiky: Hardvér, Architektúra a Dátové Štruktúry

## Úvod Dátové štruktúry sú spôsoby organizácie a ukladania dát tak, aby sme s nimi vedeli efektívne pracovať. V tomto materiáli sa zameriame na **zreťazené zoznamy (Linked List)** a princíp **FIFO** (First In, First Out), ktorý sa často používa vo frontách. > **Definícia:** Zreťazený zoznam je lineárna dátová štruktúra, v ktorej sú údaje uložené v sérii uzlov; každý uzol obsahuje dátovú časť a ukazovateľ na nasledujúci uzol. ## Základné časti zreťazeného zoznamu - **Uzol (node):** obsahuje hodnotu a referenciu/ukazovateľ na ďalší uzol. - **Hlava (head):** ukazovateľ na prvý uzol zoznamu. - **Chvost (tail):** často ukazovateľ na posledný uzol (nie vždy povinný). ### Typy zreťazených zoznamov | Typ | Popis | Kedy sa používa | |---|---|---| | Jednoducho zreťazený (Singly linked list) | Každý uzol ukazuje len na nasledujúci uzol. | Keď potrebujeme jednoduchú sekvenčnú štruktúru s nízkymi nárokmi na pamäť. | | Dvojito zreťazený (Doubly linked list) | Uzol ukazuje na predchádzajúci aj nasledujúci uzol. | Keď potrebujeme rýchlu navigáciu oboma smermi. | | Cyklický zoznam (Circular linked list) | Posledný uzol ukazuje späť na prvý, vytvára kruh. | Pri implementácii opakovaných cyklov alebo kruhových buffrov. | > **Definícia:** FIFO (First In, First Out) je princíp, podľa ktorého je prvý vložený prvok prvý spracovaný; bežná implementácia je fronta. ## Operácie so zreťazeným zoznamom (zrozumiteľne rozdelené) 1. Vkladanie (insert) - Na začiatok: zmena hlavy na nový uzol, ktorý ukazuje na starú hlavu. - Na koniec: ak máme chvost, nový uzol sa pripojí za chvost a aktualizuje sa chvost. 2. Mazanie (delete) - Z hlavy: posunieme hlavu na nasledujúci uzol. - Z prostredia: nájdeme predchádzajúci uzol a upravíme jeho ukazovateľ. 3. Prehľadávanie (traversal) - Prechádzame od hlavy cez ukazovatele až na koniec. ### Výhody a nevýhody | Vlastnosť | Výhoda | Nevýhoda | |---|---|---| | Dynamická veľkosť | Pamäť sa alokuje podľa potreby. | Viac administratívy s ukazovateľmi. | | Vkladanie/mazanie | Efektívne, ak poznáme pozíciu | Pomalý priamy prístup k prvkom podľa indexu. | | Prístup | Nie je potrebné presúvať veľké bloky pamäte | Náhodný prístup je pomalý (nutné prechádzať zoznam). | Fun fact: V jednoduchom zreťazenom zozname je prístup k n-tému prvku v čase úmernom $n$. ## FIFO a Fronty - **Fronta (queue)** je dátová štruktúra založená na princípe FIFO. - Hlavné operácie: - **enqueue** – pridanie prvku na koniec fronty. - **dequeue** – odstránenie prvku z čela fronty. - Príklad zo života: ak sa ľudia postavia do radu, prvý človek v rade je prvý, kto bude obslúžený. ### Použitie FIFO v praxi - Plánovanie procesov v operačných systémoch (ready queue) - Tlačové fronty (dokumenty sú tlačené v poradí prijatia) - Komunikácia medzi procesmi (zásobníky správ/queue) - Spracovanie úloh v poradí pri dávkovom spracovaní > **Definícia:** Fronta je abstraktná dátová štruktúra, ktorá uplatňuje pravidlo FIFO; typické operácie sú enqueue a dequeue. ## Praktické príklady (ilustračné kódy v pseudokóde) 1) Vkladanie na začiatok jednoduchého zreťazeného zoznamu: - Vytvor nový uzol s hodnotou $v$. - Nastav nový uzol.next = head. - head = nový uzol. 2) Dequeue vo fronte implementovanej zreťazeným zoznamom: - Ak je head null, fronta je prázdna. - Uložiť hodnotu head. - head = head.next. - Vrátiť uloženú hodnotu. Did you know that circular linked lists are často používané v implementácii round-robin plánovania, pretože prirodzene cyklujú medzi prvkami? ## Porovnanie: Pole vs Zreťazený zoznam vs Fronta | Štruktúra | Prístup podľa indexu | Vkladanie/mazanie na strede | Pamäťová efektívnosť | |---|---|---|---| | Pole (array) | Rýchly priamy prístup | Niekedy nákladné (potreba posunutia) | Pevná veľkosť alebo nákladné resize | | Zreťazený zoznam | Pomaly (prejsť $n$ prvkov) | Efektívne (len zmena ukazovateľov) | Dynamické, ale overhead na ukazovatele | | Fronta | Záleží na implementácii | Optimalizované pre FIFO operácie |