3. Jednosmerný lineárny zoznam
3.1 Čo je to?
Dynamická štruktúra z predchádzajúceho príkladu sa nazýva jednosmerný lineárny zoznam. Všeobecne môžeme takúto údajovú štruktúru graficky reprezentovať napr. takto:
Ukazovateľ z
nie je časťou zoznamu, ale je nevyhnutný pre manipuláciu so zoznamom
(sprístupňuje ho). Často sa nazýva čelo, hlava alebo jednoducho
ukazovateľ na začiatok zoznamu t.j. na prvý prvok zoznamu.
Jednosmerný lineárny zoznam obsahuje prvky (uzly), z ktorých každý má jednu
položku ukazovateľ. Tieto ukazovatele sú nastavené tak, aby ukazovali
na prvok nasledujúci v zozname. Ak od prvku, na ktorý ukazuje
ukazovateľ z, začíname prezerať zoznam, môžeme prejsť každý prvok zoznamu práve raz.
h1,h2, h3, ..., hn sú hodnotové časti uzlov.
Jednosmerné
lineárne zoznamy sa používajú v mnohých aplikáciách, kde nahradzujú
statické polia, zvlášť pri zapamätaní dočasne využívaných zoznamov
rôznych údajov - čísel, slov, a pod. Je relatívne jednoduché efektívne
spracovávať prvky zoznamu - vkladať a vyberať z neho uzly.
Z týchto príčin a z hľadiska úspory pamäti sú zoznamy
preferované pred poliami.
Zoznamy zvykneme graficky znázorňovať zväčša ako
vodorovnú resp. zvislú postupnosť prvkov, ktoré sú navzájom prepojené.
Tento orientovaný graf si však môžeme pokojne nakresliť aj takto:
Je jasné, že aj v pamäti počítača nemusia byť jednotlivé uzly
bezprostredne vedľa seba, ale môžu byť na rôznych miestach. Pamäť pre
uzly totiž alokujeme dynamicky. Navzájom su však jednotlivé uzly
prepojené a tvoria tak lineárny zoznam (v našom prípade jednosmerný).
Základné operácie nad jednosmerným lineárnym zoznamom:
- Vyvorenie nového (prázdneho) zoznamu
- Pridanie nového prvku na koniec zoznamu
- Prehľadávanie zoznamu, výpis prvkov
- Vloženie nového prvku za označený prvok v zozname
- Vloženie nového prvku pred označený prvok v zozname
- Odstránenie prvku zo zoznamu
- Usporiadanie prvkov zoznamu
So všetkými vyššie spomenutými operáciami nad lineárnym zoznamom sa postupne zoznámime v nasledujúcich podkapitolách. Naučíme sa pracovať s lineárnym zoznamom - objasníme princípy i programátorskú realizáciu jednotlivých operácií, ktoré je možné s touto dynamickou štruktúrou vykonávať.
