Spájať zoznam

V dnešnom tutoriále si ukážeme trochu zložitejšie, avšak veľmi dôležitú dátovú štruktúru. Bude to spájať zoznam

Spájať zoznam (Linked list)

Zoznam (list), do ktorého možno na rozdiel od poľa pridávať prvky alebo z neho prvky mazať, môžeme implementovať pomocou obyčajného poľa, v ktorom jednoducho len necháme dostatok voľného miesta. Hovorí o tom článok Dátové štruktúry poľa a list

Druhou možnosťou vytvorenia zoznamu s premenným počtom prvkov sú tzv. Spojové zoznamy. Tie už s poľom vôbec nepracujú a sú založené na odlišnom princípe. Jednotlivé prvky v liste sú v pamäti rôzne rozhádzané (už teda nie sú uložené za sebou) a po sebe idúce prvky na seba odkazujú. Môžeme si to predstaviť ako taký reťazec, kedy 1. prvok ukazuje na druhý, druhý na tretí a tak ďalej. Prvky z minulého príkladu by sme si vo spájať zozname mohli predstaviť napr. Nasledovne:

Takému spojovému zoznamu sa hovorí jednosmerný (Single Linked List). Ak nemáme nejaký vážny dôvod šetriť pamäťou, zvyčajne na seba 2 po sebe idúce prvky ukazujú navzájom (teda aj 2. na prvú a tak ďalej). Hovoríme o obojsmernom spájať zoznamu (double Linked List). Ten by v našom prípade vyzeral nejako takto:

U spojových zoznamov sme prišli o možnosť rýchlo pristúpiť k prvku podľa jeho indexu a to kvôli tomu, že prvky už nie sú v pamäti za sebou. Neexistuje spôsob, ako efektívne preskočiť rovno napr. Na 100. prvok a prečítať jeho hodnotu. Keď chceme k 100. prvku pristúpiť, musíme z prvého prvku na druhý, z druhého na tretí a tak ďalej až do stovky. Časová zložitosť čítania a zápisu na index teda záleží na počte prvkov v liste.

Niekedy však nepotrebujeme prvky indexovať a v tej chvíli sa táto kolekcia stáva veľmi výhodnú. Už na začiatku sme si povedali, že s poľom vôbec nepracujeme. Už nie sme nijako obmedzení dĺžkou zoznamu a položky môžeme za behu programu pridávať a mazať tak dlho, kým nám bude stačiť pamäť. Pomerne dobre môžeme aj mazať prvky uprostred zoznamu alebo vkladať nové prvky medzi existujúce. U pole bolo vloženie prvku možné len tak, že sme všetky prvky napravo posunuli a vytvorili tak priestor pre nový prvok. To nás stálo nemalý výpočtový čas, ktorý bol závislý na počte prvkov. Vo spájať zoznamu nový prvok iba naodkazujeme medzi 2 existujúcej, ostatných prvkov sa zmena nedotkne.

Máme teda efektívne vkladanie a mazanie prvkov na úkor neefektívneho prístupu na indexy. Tak už to u dátových štruktúr a algoritmov vôbec býva, niečo za niečo

Vidíme, že spájať zoznam a zoznam cez pole sa veľmi líšia. Ak budeme často pristupovať k prvkom pomocou indexu, bol by spájať zoznam katastrofou. Ak budeme naopak prvky často vkladať alebo mazať uprostred kolekcie, spájať zoznam si s tým hravo poradí a list s poľom by bol extrémne pomalý.

Ukážme si, ako sa taký spájať zoznam deklaruje (jazyk C):

// Osoba
typedef struct osoba {
    int vek;
    char *jmeno;
    struct osoba *p_dalsi; // Ukazatel na další osobu
} OSOBA;

// Seznam osob
typedef struct {
    int pocet;
    OSOBA *p_hlava;
    OSOBA *p_ocas;
} SEZNAM;

Ako prvý definujeme štruktúru OSOBA, čo je jedna položka zoznamu. Tá obsahuje meno, vek a odkaz na ďalšie a predchádzajúce osobu. Odkazov je tu docielené cez priame Pointer, čo je špecifikum jazyka C. Okrem štruktúry položky zoznamu sa ďalej definuje aj samotný SEZNAM. Ten okrem odkazu na hlavu (prvý prvok) v tejto konkrétnu implementáciu ukladá aj chvost (posledný prvok) a ďalej počet prvkov v zozname. Asi vám došlo, že ak by sme dĺžku zoznamu neukladali, museli by sme ju zakaždým zistiť prejdením celého zoznamu od začiatku do konca.

Časová zložitosť

Aký je teda rozdiel medzi používaním poľa a spojovaceho zoznamu? V niekoľkých operáciách sa štruktúry pochopiteľne líši. Ukážme si tabuľku zložitosťou:

operácia	zložitosť
Nájdi prvok	O (n)
Pridaj prvok na začiatok	O (1)
Pridaj prvok na koniec	O (1) *
Pridaj prvok niekam	O (n)
Zmaž prvok	O (n)
Zmaž začiatok	O (1)
Nájdi následníka	O (n)
Nájdi predka	nemožné **

- * Ak si držíme informáciu o tom, kde je koniec, inak O(n).

• ** Samozrejme nič nebráni tomu, aby ste si do tejto štruktúry pridali ďalšie pointer na svojho predka. Tým pádom z jednoduchého zoznamu urobíte obojsmerný a množina operácií sa ešte zvýši, napr. "Nájdi predka".

Nebezpečenstvo

Má to ale háčik, pointera samostatné. Sú vynikajúcim nástrojom pre programátora, ale sú natoľko silné, že môžu narobiť poriadnu paseku. Asi ako by ste si chceli krájať chleba motorovou pílou. V moderných jazykoch ako napr. Java preto Pointer nie sú, sú tu iba tzv. Referencie. Referencie je niečo ako pointer, ale vy s tým pointer nemôžete priamo pracovať a tým spôsobiť napr. Poškodenie inej časti pamäte. Viac o Pointer sa dozvieme v seriáli Princípy fungovania počítačov.

Spájať zoznam sa často používa pre implementáciu dátových štruktúr frontu a zásobníka.