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äte 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ť.