Lineárny zoznam

Algoritmy a programovanie

---

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Lineárny zoznam (lineárny spojový zoznam) je dynamická dátová štruktúra, navonok podobná poľu (umožňuje uložiť viacero hodnôt, ale iným spôsobom), obsahujúca jednu alebo viacero dátových položiek (štruktúr) rovnakého typu, ktoré sú navzájom lineárne previazané vzájomnými odkazmi pomocou smerníkov alebo referencií. Aby bol zoznam lineárny, nesmú v ňom existovať cykly so vzájomnými odkazmi.

Lineárny zoznam poznáme jednosmerný a obojsmerný. V jednosmernom zozname odkazuje každá položka na nasledujúcu položku a v obojsmernom zozname odkazuje aktuálna položka na nasledujúcu ale aj predchádzajúcu položku. Definuje sa tu smerník alebo odkaz na určitý prvok zoznamu. Na konci (a začiatku) musí byť definovaná zarážka, ktorá označuje koniec zoznamu. Ak vytvoríme taký cyklus, že posledný prvok zoznamu odkazuje na prvý prvok zoznamu, dostaneme kruhový zoznam.

• 

  Jednosmerný lineárny zoznam.Každý prvok zoznamu okrem svojej hodnoty obsahuje i odkaz na nasledujúci prvok v seznamu. Posledný prvok odkazuje „nikam“.

• 

  Jednosmerný kruhový zoznam. Posledný prvok zoznamu odkazuje opäť na začiatok.

• 

  Obojsmerný lineárny zoznam. Každý prvok zoznamu obsahuje, okrem svojej hodnoty, odkaz na nasledujúci i predchádzajúci prvok zoznamu

V nasledujúcom texte bude opisovaný jednosmerný lineárny zoznam.

Vlastnosti lineárneho zoznamu

• Jednosmerný lineárny zoznam je pamäťovo nenáročná dátová štruktúra
• Dovoľuje zoskupiť ľubovoľný počet prvkov. Počet prvkov je obmedzený len dostupnou pamäťovou kapacitou počítača.
• Dokáže jednoducho meniť svoju veľkosť počas behu programu.
• Prvky zoznamu, na rozdiel od polí neležia vedľa seba, ale v pamäti sú alokované podľa toho, kde je dostatok miesta.

Nasledujúci obrázok znázorňuje spôsob uloženia prvkov v pamäti pri použití poľa a lineárneho zoznamu.

Rozdiel medzi vnútornou štruktúrou poľa a lineárneho zoznamu

Štruktúra lineárneho zozamu

Lineárny zoznam sa skladá z určitých prvkov (alebo uzlov), ktoré sú navzájom previazané vzájomnými odkazmi. Inak povedané stavebný prvok lineárneho zoznamuje samotnú hodnotu prvku (číslo, reťazec, štruktúra, ...) a odkaz na ďalší prvok. Ešte pripomeňme, že všetky prvky lineárneho zoznamu sú rovnakého typu.

Definujme štruktúru TPrvok (záznam pracovnej povahy), ktorý bude obsahovať:

• dátovú časť (ľubovolná položka, v našom prípade celé číslo)
• ukazovateľ na na ďalší záznam typu TPrvok

Definícia v jazyku C:

struct TPrvok 
   {	
      int data;	
      TPrvok *dalsi; 
   };

Vysvetlenie: Štruktúra TPrvok obsahuje dátovú časť označenú ako data. Odkaz na ďalší prvok je označený ako dalsi, a je to smetník na štruktúru TPrvok.

V nasledujúcom príklade budú ukážky definície prvkov lineárneho zoznamu, ktorý namiesto hodnoty celého čísla obsahuje inú dátovú časť.

 1 struct TPrvok 
 2    {	
 3       char retazec[64];	
 4       TPrvok *dalsi; 
 5    };
 6 //------------------------------------
 7 struct TPrvok 
 8    {	
 9       TZlomok data;	
10       TPrvok *dalsi; 
11    };
12 //------------------------------------
13 struct TPrvok 
14    {	
15       double data[10];	
16       TPrvok *dalsi; 
17    };

• riadok 1: prvok lineárneho zoznamu je reťazec o dĺžke 63 znakov
• riadok 7: prvok lineárneho zoznamu je zlomok
• riadok 13: prvok lineárneho zoznamu je pole reálnych čísel o veľkosti 10.

Vizualizácia dátovej štruktúry TPrvok

Pre uloženie informácie o tom, kde má zoznam začiatok a kde končí si definujme ďalšiu štruktúru, ktorú nazveme TZoznam, ktorá bude obsahovať 2 smerníky na štruktúru TPrvok. Jeden smerník ukazuje na začiatok zoznamu a druhý smerník ukazuje na koniec zoznamu.

struct TZoznam { 
   TPrvok *prvy;
   TPrvok *posledny;
} ;

Vizualizácia dátovej štruktúry TZoznam

Práca s lineárnym zoznamom

Pre lineárny zoznam platí nasledovné:

• Prvky prvy, posledny, dalsi sú ukazovatele na TPrvok.
• Časť štruktúry TPrvok označené ako data môže byť ľubovoľný dátový typ: reťazec, štruktúra, číslo...
• Ak je zoznam prázdny informačná štruktúra TZoznam má dva ukazovatele a oba majú hodnotu NULL. Teda ukazujú "nikam".
• Ak je v zozname jeden prvok tak ukazovatele prvy a posledny (TZoznam) ukazujú ne tento prvok a dalsi (TPrvok) má hodnotu NULL.
• Ak je v zozname dva a viac prvkov tak
  • smerník prvy (TZoznam) ukazuje na prvý prvok v lineárnom zozname,
  • smerník posledny (TZoznam) ukazuje na posledný prvok v lineárnom zozname,
  • Smerník dalsi (TPrvok) prvého prvku ukazuje na druhy prvok zoznamu a dalsi druhého prvku ukazuje na NULL.

• 

  Prázdny lineárny zoznam

• Lz5.png

  Lineárny zoznam s jedným prvkom

Prechod cez lineárny zoznam

Uvedieme psseudokód, ktorý ukazuje princíp prechodu cez všetky prvky lineárneho zoznamu.

 1 TZoznam LinZ;
 2 // naplnenie zoznamu datami
 3 begin
 4 TPrvok *pom;
 5 pom=LinZ.prvy;
 6 rob
 7    begin
 8       vypis pom->data
 9       pom=pom->dalsi;
10       pokial( pom != LinZ.posledny )
11    end
12 end

Na riadku 1 si vytvoríme premennú typu TZoznam (Lineárny zoznam, ktorý udržuje informáciu o prvom a posledom prvku zoznamu). Naplnenie zoznamu je symbolicky naznačené na riadku 2. Zoznam pozostáva zo štruktúr typu smerník na TPrvok. Preto si na riadku 4 vytvárame premennú pom typu smerník na TPrvok. Pre túto premennú netreba alokovať miesto v pamäti, pretože pomocou tejto premennej budeme prechádzať po existujúcich prvkoch zoznamu. Na začiatok nastavíme premennú pom na prvý prvok zoznamu. V cykle (riadok 6) vypíšeme obsah prvku (riadok 8). Na riadku 9 je posunutie sa o jeden prvok ďalej (riadok 9). Cyklus ukončíme vtedy ak bude prvok pom zhodný z posledným prvkom zoznamu (smerní na posledný prvok zoznamu obsahuje premenná LinZ.