Skip to main content.

Spájaný zoznam

Najjednoduchší spôsob vzájomného združenia alebo pospájania prvkov nejakej množiny je ich zoradenie do zoznamu. V týchto prípadoch je potrebný iba jeden spojovací článok pre každý prvok množiny, ktorý stačí na určenie nasledujúceho prvku v množine.

Spájaný zoznam je dátovou štruktúrou, ktorá aplikuje tento princíp. Skladá sa z postupnosti uzlov rovnakého typu, kde každý uzol pozostáva z dvoch zložiek. Prvou zložkou sú referencie (smerníky) ukazujúce na nasledovníka a predchodcu uzla a druhá zložka je samotná hodnota kľúča spolu s ďalšími dátami. Na rozdiel od poľa, v ktorom je poradie stanovené indexmi, je teda poradie v spájanom zozname určované ukazovateľmi vo všetkých objektoch.

Ak je x prvok zoznamu, next[x] ukazuje na jeho nasledovníka v zozname a prev[x] na jeho predchodcu. Ak prev[x]=nil, prvok nemá predchodcu a preto je prvým prvkom (head) zoznamu. Ak next[x]=nil, prvok nemá nasledovníka a je posledným prvkom (tail) zoznamu. Atribút head[L] ukazuje na prvý prvok zoznamu L. Ak head[L]=nil, zoznam je prázdny.

Hlavnou výhodou spájaného zoznamu je fakt, že usporiadanie dát v spájanom zozname sa môže líšiť od usporiadania dát v pamäti. Nové usporiadanie jednotlivých uzlov môže teda spĺňať rôzne špeciálne potreby. Spájané zoznamy tiež poskytujú jednoduchú a flexibilnú reprezentáciu pre dynamické množiny podporujúce operácie ako sú napríklad Search, Insert a Delete.

^ TOP

Typy spájaného zoznamu

Zoznam s jednoduchou väzbou
Tento typ zoznamu má smerník iba na svojho nasledovníka. Ak je uzol posledný, smerník má hodnotu nil.
jednoduchy zoznam
Zoznam s dvojitou väzbou
Je to typ spájaného zoznamu, ktorý má smerník na svojho nasledovníka a aj smerník na svojho predchodcu. Ak je uzol prvý, hodnota smerníka na predchodcu má hodnotu nil a obdobne, ak je uzol posledný, tak hodnota smerníka na nasledovníka má tiež hodnotu nil.
dvojity zoznam
Kruhový zoznam
V kruhovom zozname smerník prev hlavy (head) ukazuje na posledný prvok a smerník next posledného prvku ukazuje na hlavu zoznamu.
kruhovy zoznam

^ TOP

Zarážky

Spájané zoznamy majú niekedy špeciálny uzol, ktorý sa volá zarážka (sentinel node). Zarážka označuje začiatok (koniec) zoznamu a nemá žiadnu hodnotu kľúča. Používa sa hlavne na zjednodušenie a zrýchlenie niektorých operácií. Použitím zarážky sa docieli, že každý uzol má predchodcu (nasledovníka) a že každý zoznam má prvý (posledný) uzol.
V princípe to znamená, že miesto toho, aby smerníky mali hodnotu nil, budú ukazovať na zarážku.
zarazka

^ TOP

Operácie

Nasledovné operácie uvedené v pseudokóde sú základnými operáciami na spájaných zoznamoch.

Vyhľadávanie v spájanom zozname
Procedúra List-Search(L,k) nájde v zozname L prvý prvok s kľúčom k jednoduchým lineárnym prehľadávaním, pričom vráti ukazovateľ na tento prvok. Ak sa v danom zozname taký prvok nenachádza, procedúra vráti hodnotu nil. Na vyhľadanie prvku v zozname pozostávajúcom z n prvkov, potrebuje procedúra v najhoršom prípade čas Theta(n). 
      LIST-SEARCH
        x:=head[L]
        while (x<>nil) and (key[x]<>k) do
          x:=next[x]
        return x
Vkladanie do spájaného zoznamu
Procedúra List-Insert umiestni daný prvok x na začiatok zoznamu. Čas behu procedúry je O(1). 
      LIST-INSERT
        next[x]:=head[L]
        if head[L]<>nil then
          prev[head[L]]:=x
        head[L]:=x
        prev[x]:=nil
Vymazávanie zo spájaného zoznamu
Procedúra List-Delete odstráni prvok x zo spájaného zoznamu L. Aby mohol byť prvok odstránený, musí naň procedúra dostať ukazovateľ. Prvok bude potom zo zoznamu vyňatý jednoduchou zmenou ukazovateľov. Ak teda chceme vymazať prvok s daným kľúčom, musíme najprv vyvolať procedúru List-Search
      LIST-DELETE
        next[prev[x]]:=next[x]
        prev[next[x]]:=prev[x]

^ TOP

Vlastnosti

Spájaný zoznam je dátový typ odkazujúci sám na seba, lebo jednotlivé uzly sú toho istého typu.
Umožňuje vkladanie a mazanie uzlov v konštantnom čase, ale neumožňuje náhodný prístup.
Aby bol zoznam lineárny, nesmú existovať cykly vo vzájomných odkazoch.

^ TOP