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

Vysvetlenie uvedeného pseudokódu:

• 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.
• Cyklus ukončíme vtedy ak bude prvok pom zhodný z posledným prvkom zoznamu (smerní na posledný prvok zoznamu obsahuje premenná LinZ.

Vkladanie záznamov zo lineárneho zoznamu

Prvok môžeme do zoznamu vkladať dvoma spôsobmi:

1. Vloženie prvku na koniec (na začiatok). Vytváraný zoznam bude neusporiadaný.
2. Vloženie prvku na správne miesto. V tomto prípade sa snažíme aby bol zoznam stále usporiadaný od najmenšieho (najväčšieho) prvku po najväčší (najmenší).

Vkladanie nového prvku na koniec zoznamu

Pri vkladaní prvku do lineárneho zoznamu musíme rozlíšiť 2 rôzne situácie

1. Zoznam je prázdny
   • Vložený prvok bude jediným prvkom zoznamu. Bude prvým a zároveň posledným prvkom zoznamu
2. Zoznam nie je prázdny.
   • Vložený prvok umiestnime na koniec zoznamu. Tento nový prvok bude zároveň posledným prvkom zoznamu.

Na nasledujúcich obrázkoch bude znázornená situácia vloženia nového prvku do prázdneho a neprázdneho zoznamu na koniec.

• 

  Prázdny zoznam. Do zoznamu budeme vkladať nový prvok s hodnotou "-5"

• 

  Do prázdneho zoznamu sme vložili nový prvok s hodnotou "-5". Tento prvok sa stal zároveň prvým aj posledným prvkom zoznamu.

• 

  Do zoznamu sme vložili nový prvok s hodnotou "20". Tento nový prvok bude posledným prvkom v zozname. Pred pridaním mal prvok "-5" smerník dalsi nastavený na hodnou NULL (pretože bol posledný). Teraz smetník dalsi prvku "-5" ukazuje na prvok "20", ktorého smerník dalsi ma hodnotu NULL.

Pri vkladaní prvku do usporiadaného lineárneho zoznamu musíme rozlíšiť nasledujúce situácie

1. Zoznam je prázdny
   • Vložený prvok bude jediným prvkom zoznamu. Bude prvým a zároveň posledným prvkom zoznamu. Toto riešenie je rovnaké ako v predchádzajúcom príklade.
2. Zoznam nie je prázdny.
   1. Nový prvok je menší ako prvý prvok.
   2. Nový prvok je väčší ako posledný prvok.
   3. Nový prvok treba umiestniť na správne miesto v zozname.

Na nasledujúcich obrázkoch bude znázornené jednotlivé prípady. Budeme vychádzať z neprázdneho zoznamu z nasledujúceho obrázka.

Nerázdny usporiadaný lineárny zoznam

Do zoznamu vkladáme nová prvok s hodnotou "-5". Zistili sme že tento prvok je menší ako prvý prvok, preto ho umiestnime na začiatok zoznamu. Po vložení to bude nový prvý prvok zoznamu.

Vloženie nového prvku na začiatok zoznamu

Do zoznamu vkladáme nová prvok s hodnotou "20". Zistili sme že tento prvok je väčší ako posledný prvok, preto ho umiestnime na koniec zoznamu. Po vložení to bude nový posledný prvok zoznamu.

Vloženie nového prvku na koniec zoznamu

Do zoznamu vkladáme nová prvok s hodnotou "5". Zistili sme že tento prvok treba umiestniť na správne miesto v zozname. Po nájdení správneho miesta (medzi prvky 0 a 10) ho medzi tieto prvky vložíme. Prvky medzi ktoré budeme nový prvok vkladať si označme ako lavy a pravy. Postupnosť operácií, ktoré musíme urobiť je na nasledujúcom obrázku:

1. Smerník dalsi nového prvku nastavíme na prvok pravy
2. Zmažeme smerník dalsi, ktorý ukazuje z prvku lavy na pravy.
3. Smerník dalsi prvku lavy nastavíme tak, aby ukazoval na nový prvok.

Implementácia lineárneho zoznamu v jazyku C

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

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