3. diel - Spájať zoznam v C #

V minulej lekcii, Zoznam (List) pomocou poľa v C # , sme si predstavili zoznamy (listy) a detailne opísali zoznam pomocou poľa a triedu List. Dnes sa v C# .NET tutoriálu zameriame na druhý typ zoznamu, ktorým je spájať zoznam.

Spojové zoznamy

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 iba prvok 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ý.

LinkedList

Spájať zoznam je v .NET reprezentovaný generickú kolekcií LinkedList. Jedná sa o spájať zoznam obojsmerný, jednosmerný spájať zoznam v .NET nenájdeme. Mohli by sme si ho naprogramovať, ale nemá to príliš význam, pretože sa s ním horšie pracuje a úspora pamäte je mizivá.

LinkedList neobsahuje rovno naše prvky ako tomu bolo u List u, ale sú v ňom uložené položky typu LinkedListNode. Sú to uzly, ktoré na seba navzájom ukazujú (odkazujú sa, ak chcete) a disponujú vlastností Value. Práve v tej je ešte len uložený náš prvok, ktorý uzol obaľuje. Dodáva tak nášmu prvku ony väzby na prvky okolité. Ukážme si metódy, ktoré má LinkedList oproti klasickému List u navyše:

• AddAfter() - Pridá nový prvok za daný prvok.
• AddBefore() - Pridá nový prvok pred daný prvok.
• AddFirst() - Pridá nový prvok na začiatok zoznamu.
• AddLast() - Pridá nový prvok na koniec zoznamu.
• First - Vlastnosť vracajúci prvý prvok.
• Last - Vlastnosť vracajúci posledný prvok.
• RemoveFirst() - Odstráni prvý prvok.
• RemoveLast() - Odstráni posledný prvok.

Príklad

Vyskúšajme si podobný príklad ako u listu:

LinkedList<int> seznam = new LinkedList<int>();
LinkedListNode<int> hlava = seznam.AddFirst(5);
seznam.AddAfter(hlava, 10);
Console.WriteLine(seznam.First.Value);
Console.WriteLine(seznam.First.Next.Value);

Výstup programu:

5
10

Vytvoríme nový spájať zoznam typu int, pridáme 1. prvok a uložíme si ho ako hlavu. Za hlavu pridáme ďalší prvok. Nakoniec vypíšeme prvý prvok a prvok po prvom prvku (teda 2.).

Skúsme si ešte ono rýchle vkladanie a mazanie prvkov:

// inicializace a naplnění spojového seznamu
LinkedList<int> seznam = new LinkedList<int>();
seznam.AddLast(1);
seznam.AddLast(2);
LinkedListNode<int> prostredni = seznam.AddLast(3);
seznam.AddLast(4);
seznam.AddLast(5);

// přidávání a mazání v prostředku seznamu
seznam.AddAfter(prostredni, 32);
seznam.AddAfter(prostredni, 31);
seznam.Remove(prostredni);

// výpis seznamu
foreach (int i in seznam)
    Console.Write("{0}, ", i);

Console.ReadKey();

výstup:

Práca so spojovým zoznamom je vďaka uzlom o niečo komplikovanejšie ako s List em a väčšinou používame skôr List. Po "spojáku" siahneme hlavne v prípade, keď chceme často vkladať a mazať prvky doprostred zoznamu, čo by u List u bolo veľmi pomalé.

Ešte poznámku, než listy úplne opustíme. V starých zdrojových kódoch môžete naraziť na kolekciu StringCollection. Tá suplovala za List<string> v časoch, keď kolekcia v .NET neboli generickej. Dnes už nie je dôvod túto triedu používať a spôsobuje skôr zmätení.

Dnes to bolo trochu kratšie, ale nechcel som začínať na konci novú tému. V budúcej lekcii, Viacrozmerné polia v C # .NET , sa pozrieme na viacrozmerné pole.

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.