Zhrnutie na Základy informatiky a manažmentu
Základy Informatiky a Manažmentu: Komplexný Sprievodca
Úvod
Dátové štruktúry sú spôsob usporiadania a správy dát tak, aby ich program mohol efektívne používať. Tento materiál sa zameriava na zreťazené zoznamy (Linked List) a princíp FIFO (First In, First Out), ktoré sú základom mnohých algoritmov a systémov spracovania dát.
Definícia: Zreťazený zoznam je lineárna dátová štruktúra, v ktorej sú údaje uložené v sérii uzlov, pričom každý uzol obsahuje dátovú časť a ukazovateľ (referenciu) na nasledujúci uzol.
Zreťazené zoznamy - rozdelenie a základné vlastnosti
Typy zreťazených zoznamov
- Jednoducho zreťazený zoznam (Singly linked list): každý uzol ukazuje len na nasledujúci uzol.
- Dvojito zreťazený zoznam (Doubly linked list): každý uzol ukazuje na predchádzajúci aj nasledujúci uzol.
- Cyklický zoznam (Circular linked list): posledný uzol ukazuje späť na prvý, čím vytvára cyklus.
Definícia: Jednoducho zreťazený zoznam: každý uzol má pole "value" a ukazovateľ "next"; posledný uzol má "next" = null (ak nie je cyklický).
Vlastnosti zreťazených zoznamov
- Dynamická veľkosť — pamäť sa môže pridávať alebo uvoľňovať za behu programu.
- Efektívne vkladanie a mazanie prvkov, ak poznáme pozíciu (bežné operácie v čase $O(1)$ pre vloženie/mazanie pri známej pozícii).
- Menej vhodné pre priamy prístup — nájdenie prvku podľa indexu je v priemere $O(n)$.
Základné operácie (Singly linked list)
- Vytvorenie uzla (node) s hodnotou a ukazovateľom na next.
- Vloženie na začiatok (push/insertHead): zmena head ukazateľa.
- Vloženie na koniec (append): prechádzanie až na posledný uzol, potom nastavenie jeho next.
- Odstránenie z hlavy (pop/dequeueHead): head = head.next.
- Vyhľadávanie prvku: prechádzanie zo začiatku až po nájdenie.
Príklad (pseudokód):
- Vytvor Node(value, next=null)
- Ak head == null, head = node
- Inak, prejdite do posledného uzla a nastavte last.next = node
Tabuľkové porovnanie typov
| Typ | Ukazovatele | Vkladanie/mazanie pri známej pozícii | Priamy prístup podľa indexu | Využitie pamäti |
|---|---|---|---|---|
| Jednoducho zreťazený | next | + (O(1)) | - (O(n)) | nízke |
| Dvojito zreťazený | prev, next | ++ (O(1)) | - (O(n)) | vyššie (dvojité ukazovatele) |
| Cyklický | next (posledný -> prvý) | + (O(1)) pri rotáciách | - (O(n)) | podobné ako singly |
💡 Vedeli ste?Fun fact: Zreťazené zoznamy sú jednou z prvých dátových štruktúr, ktoré sa učia v kurzoch algoritmov, pretože intuitívne ukazujú rozdiel medzi statickou (pole) a dynamickou pamäťou.
FIFO (First In, First Out) a fronty
Definícia: FIFO (First In, First Out) je princíp organizácie dát, pri ktorom je prvý vložený prvok aj prvý spracovaný.
Implementácia fronty (Queue)
Najbežnejšie operácie:
- enqueue – pridanie prvku na koniec fronty
- dequeue – odstránenie prvku z čela fronty
- peek/front – zobrazenie prvého prvku bez odstránenia
Frontu je možné implementovať pomocou:
- Poľa (circular buffer) — efektívne, ale s pevnou maximálnou veľkosťou alebo s posunom indexov.
- Zreťazeného zoznamu — jednoduché vkladanie na koniec a odstránenie z hlavy v čase $O(1)$.
Prečo použiť FIFO?
- Zachováva poradie príchodu úloh.
- Jednoduché modelovanie reálnych situácií, napr. fronty v obchode, tlačové fronty.
Príklad reálneho použitia:
- Operačný systém plánuje úlohy alebo spravuje frontu tlače.
- Sieťové buffery prijímajú pakety a spracujú ich v poradí príchodu.
💡 Vedeli ste?Did you know that implementácia fronty pomocou zreťazeného zoznamu umožňuje vždy dosiahnuť operácie enqueue a dequeue v čase $O(1)$ bez potreby posunu všetkých prvkov?
Praktické príklady a cvičenia (Not attending študent)
- Implementujte jednoduchý singly linked list v preferovanom programovacom jazyku: metódy insertHead, append, removeHead, find.
- Implementujte frontu pomocou zreťazeného zoznamu s metódami enqueue, dequeue, peek a testujte poradie spracovania.
- Vyskúšajte prevod medzi implementáciami: napíšte frontu pomocou poľa (circular buffer) a porovnajte správanie pri plnom buffri.
T
Zaregistruj sa pre celé zhrnutieKartičkyTest znalostíZhrnutiePodcastMyšlienková mapa
Začni zadarmo Už máš účet? Prihlásiť sa
Zreťazené zoznamy a FIFO
Klíčová slova: Počítačový hardvér, Softvérové simulácie, Dátové štruktúry, Vedenie
Klíčové pojmy: Zreťazený zoznam má uzly s hodnotou a ukazovateľom na next, Singly, Doubly, a Circular sú hlavné typy zreťazených zoznamov, Zreťazené zoznamy umožňujú dynamickú veľkosť, Vkladanie/mazanie pri známej pozícii je v O(1), Priamy prístup podľa indexu v zreťazenom zozname je O(n), FIFO znamená First In, First Out; fronta zachováva poradie, Frontu možno implementovať pomocou poľa alebo zreťazeného zoznamu, Enqueue a Dequeue v zreťazenom zozname sú O(1), Testujte hranice: prázdny zoznam a jedna položka, Doubly linked list umožňuje obojsmerné prechádzanie, Cyklický zoznam prepája koniec so začiatkom, Pri výbere štruktúry zvoľte podľa potrebných operácií
## Úvod
Dátové štruktúry sú spôsob usporiadania a správy dát tak, aby ich program mohol efektívne používať. Tento materiál sa zameriava na **zreťazené zoznamy (Linked List)** a princíp **FIFO (First In, First Out)**, ktoré sú základom mnohých algoritmov a systémov spracovania dát.
> **Definícia:** Zreťazený zoznam je lineárna dátová štruktúra, v ktorej sú údaje uložené v sérii uzlov, pričom každý uzol obsahuje dátovú časť a ukazovateľ (referenciu) na nasledujúci uzol.
## Zreťazené zoznamy - rozdelenie a základné vlastnosti
### Typy zreťazených zoznamov
- **Jednoducho zreťazený zoznam (Singly linked list)**: každý uzol ukazuje len na nasledujúci uzol.
- **Dvojito zreťazený zoznam (Doubly linked list)**: každý uzol ukazuje na predchádzajúci aj nasledujúci uzol.
- **Cyklický zoznam (Circular linked list)**: posledný uzol ukazuje späť na prvý, čím vytvára cyklus.
> **Definícia:** Jednoducho zreťazený zoznam: každý uzol má pole "value" a ukazovateľ "next"; posledný uzol má "next" = null (ak nie je cyklický).
### Vlastnosti zreťazených zoznamov
- Dynamická veľkosť — pamäť sa môže pridávať alebo uvoľňovať za behu programu.
- Efektívne vkladanie a mazanie prvkov, ak poznáme pozíciu (bežné operácie v čase $O(1)$ pre vloženie/mazanie pri známej pozícii).
- Menej vhodné pre priamy prístup — nájdenie prvku podľa indexu je v priemere $O(n)$.
### Základné operácie (Singly linked list)
1. Vytvorenie uzla (node) s hodnotou a ukazovateľom na next.
2. Vloženie na začiatok (push/insertHead): zmena head ukazateľa.
3. Vloženie na koniec (append): prechádzanie až na posledný uzol, potom nastavenie jeho next.
4. Odstránenie z hlavy (pop/dequeueHead): head = head.next.
5. Vyhľadávanie prvku: prechádzanie zo začiatku až po nájdenie.
Príklad (pseudokód):
1. Vytvor Node(value, next=null)
2. Ak head == null, head = node
3. Inak, prejdite do posledného uzla a nastavte last.next = node
### Tabuľkové porovnanie typov
| Typ | Ukazovatele | Vkladanie/mazanie pri známej pozícii | Priamy prístup podľa indexu | Využitie pamäti |
|---|---:|---:|---:|---:|
| Jednoducho zreťazený | next | + (O(1)) | - (O(n)) | nízke
| Dvojito zreťazený | prev, next | ++ (O(1)) | - (O(n)) | vyššie (dvojité ukazovatele)
| Cyklický | next (posledný -> prvý) | + (O(1)) pri rotáciách | - (O(n)) | podobné ako singly
Fun fact: Zreťazené zoznamy sú jednou z prvých dátových štruktúr, ktoré sa učia v kurzoch algoritmov, pretože intuitívne ukazujú rozdiel medzi statickou (pole) a dynamickou pamäťou.
## FIFO (First In, First Out) a fronty
> **Definícia:** FIFO (First In, First Out) je princíp organizácie dát, pri ktorom je prvý vložený prvok aj prvý spracovaný.
### Implementácia fronty (Queue)
Najbežnejšie operácie:
- **enqueue** – pridanie prvku na koniec fronty
- **dequeue** – odstránenie prvku z čela fronty
- **peek/front** – zobrazenie prvého prvku bez odstránenia
Frontu je možné implementovať pomocou:
- Poľa (circular buffer) — efektívne, ale s pevnou maximálnou veľkosťou alebo s posunom indexov.
- Zreťazeného zoznamu — jednoduché vkladanie na koniec a odstránenie z hlavy v čase $O(1)$.
### Prečo použiť FIFO?
- Zachováva poradie príchodu úloh.
- Jednoduché modelovanie reálnych situácií, napr. fronty v obchode, tlačové fronty.
Príklad reálneho použitia:
- Operačný systém plánuje úlohy alebo spravuje frontu tlače.
- Sieťové buffery prijímajú pakety a spracujú ich v poradí príchodu.
Did you know that implementácia fronty pomocou zreťazeného zoznamu umožňuje vždy dosiahnuť operácie enqueue a dequeue v čase $O(1)$ bez potreby posunu všetkých prvkov?
## Praktické príklady a cvičenia (Not attending študent)
1. Implementujte jednoduchý singly linked list v preferovanom programovacom jazyku: metódy insertHead, append, removeHead, find.
2. Implementujte frontu pomocou zreťazeného zoznamu s metódami enqueue, dequeue, peek a testujte poradie spracovania.
3. Vyskúšajte prevod medzi implementáciami: napíšte frontu pomocou poľa (circular buffer) a porovnajte správanie pri plnom buffri.
T