Zhrnutie na Základy počítačového hardvéru a dátových štruktúr

## Úvod Dátové štruktúry sú spôsoby organizácie a ukladania dát tak, aby sme ich vedeli efektívne spracovať. Tento materiál sa zameriava na **zreťazené zoznamy (linked lists)** a princíp **FIFO (First In, First Out)**, vysvetlí základné typy, operácie, príklady a použitia v reálnych systémoch. ## Zreťazený zoznam (Linked List) > **Definícia:** Zreťazený zoznam je lineárna dátová štruktúra, v ktorej sú prvky uložené v uzloch; každý uzol obsahuje dátovú časť a ukazovateľ na ďalší uzol. ### Základné časti uzla - **Dátová časť** – hodnota uložená v uzle. - **Ukazovateľ (reference)** – odkaz na nasledujúci uzol (alebo na predchádzajúci pri dvojito zreťazenom zozname). ### Typy zreťazených zoznamov | Typ | Popis | Výhody | Nevýhody | |---|---:|---|---| | Jednoducho zreťazený (Singly) | Každý uzol ukazuje na nasledujúci uzol | Jednoduchá implementácia, menšia pamäť | Len jednosmerný pohyb, pomalý priamy prístup | | Dvojito zreťazený (Doubly) | Uzly majú ukazovateľ na predchádzajúci a nasledujúci | Rýchlejšie obojsmerné prechádzanie, rýchlejšie mazanie | Vyššia pamäťová náročnosť (dodatočný ukazovateľ) | | Cyklický (Circular) | Posledný uzol ukazuje späť na prvý | Umožňuje rotujúce prechádzanie bez null ukazovateľov | Potreba ošetriť nekonečné slučky | ### Operácie a ich zložitosť (všeobecne) - Vloženie na začiatok: O(1) - Vloženie na koniec: O(n) ak nemáme tail pointer, O(1) s tail pointer - Odstránenie: O(1) ak máme priamy prístup k uzlu a jeho predchodcovi (inak O(n)) - Hľadanie prvku: O(n) ### Praktický príklad (pseudokód) 1. Vloženie na začiatok (Singly): - Vytvor nový uzol s hodnotou v - new.next = head - head = new 2. Odstránenie z čela: - if head == null then return - head = head.next Fun fact: Zreťazené zoznamy boli jednou z prvých univerzálne popísaných dynamických dátových štruktúr a používajú sa už od počiatkov programovania na efektívne vkladanie a mazanie. ## FIFO (First In, First Out) a fronty > **Definícia:** FIFO je princíp, kde prvý vložený prvok je aj prvý, ktorý sa spracuje; dátová štruktúra implementujúca tento princíp sa nazýva fronta (queue). ### Základné operácie vo fronte - **enqueue** – pridanie prvku na koniec fronty - **dequeue** – odstránenie prvku z čela fronty - **peek/front** – zobraziť prvý prvok bez odstránenia - **isEmpty** – skontrolovať, či je fronta prázdna ### Implementácie fronty - Pole (cirkulárny buffer) – efektívne miesto, vyžaduje správu indexov - Zreťazený zoznam – jednoduché enqueue/dequeue s O(1) pri použití ukazovateľov na head a tail ### Príklad použitia FIFO v reálnom svete - Plánovanie procesov v operačných systémoch - Tlačové fronty: objednávky sú spracované v poradí, v akom prišli - Spracovanie požiadaviek v serveroch a sieťach Did you know that fronty sú základom mnohých systémov správy úloh, kde je dôležité zachovať poradie prichádzajúcich požiadaviek pre korektné spracovanie? ## Porovnanie: zreťazený zoznam vs pole pre implementáciu fronty | Kritérium | Pole (cirkulárne) | Zreťazený zoznam | |---|---:|---:| | Vkladanie na koniec (enqueue) | O(1) | O(1) s tail pointer | | Odstránenie z čela (dequeue) | O(1) | O(1) | | Pamäťová efektívnosť | Fixná veľkosť alebo potreba reallocation | Dynamická veľkosť, menej plytvania pri premenlivom počte prvkov | | Náročnosť implementácie | Vyžaduje spracovanie indexov, wrap-around | Jednoduché s ukazovateľmi | ### Kedy použiť ktorý prístup - Použite pole/cirkulárny buffer, ak je maximálna veľkosť známa a potrebuje sa rýchly priamy prístup - Použite zreťazený zoznam, ak potrebujete dynamickú veľkosť a časté vkladanie/mazanie bez prealokácií ## Rozšírenia a súvisiace koncepty - Pri implementácii doubly linked list často udržiavame ukazovatele na head a tail pre rýchle operácie na oboch koncoch - Cyklické zoznamy sa často používajú v situáciách, kde sa potrebuje opakované prechádzanie bez resetu ukazovateľa - Fronty môžu byť rozšírené na priority queues, kde poradie závisí od priority, nie len od času vloženia ## Prakt