3. diel - Spájať zoznam vo VB.NET

V minulej lekcii, Zoznam (List) pomocou poľa vo VB.NET , sme si predstavili zoznamy (listy) a detailne opísali zoznam pomocou poľa a triedu List.

Dnes sa vo VB.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 (niekedy tiež hovoríme uzly) 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, keď prvý 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 dva po sebe idúce prvky ukazujú navzájom (teda aj druhý 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 stý prvok a prečítať jeho hodnotu. Keď chceme k stému 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 odkazy prvku nasmerujeme medzi dva existujúce prvky, 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, bude 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 to bolo pri zoznamu cez pole List, ale sú v ňom uložené položky typu LinkedListNode. Sú to prvky (uzly), ktoré na seba navzájom ukazujú (prepájajú 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é.

Na zozname LinkedList nájdeme tieto vlastnosti:

• Count - Vlastnosť vracajúci počet prvkov.
• First - Vlastnosť vracajúci prvý prvok.
• Last - Vlastnosť vracajúci posledný prvok.

Ukážme si metódy, ktoré má LinkedList oproti klasickému zoznamu List 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.
• Clear() - Odoberie všetky prvky zoznamu.
• Contains() - Určí či je hodnota v zozname.
• CopyTo() - skopíruje všetky prvky zoznamu na kompatibilnej jednorozmerné pole (Array).
• Find() - vyhľadá prvý prvok, ktorý obsahuje zadanú hodnotu.
• FindLast() - vyhľadá posledný prvok, ktorý obsahuje zadanú hodnotu.
• Remove() - Odstráni prvý výskyt prvku (hodnoty).
• RemoveFirst() - Odstráni prvý prvok.
• RemoveLast() - Odstráni posledný prvok.

Príklad

Vytvoríme nový spájať zoznam typu Integer, pridáme prvý 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 druhý).

{VBNET_CONSOLE}
Dim seznam As New LinkedList(Of Integer)()
Dim hlava As LinkedListNode(Of Integer) = seznam.AddFirst(5)
seznam.AddAfter(hlava, 10)
Console.WriteLine(seznam.First.Value)
Console.WriteLine(seznam.First.[Next].Value)
{/VBNET_CONSOLE}

Výstup programu:

Konzolová aplikácia
5
10

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

{VBNET_CONSOLE}
' inicializácia a naplnenie spojovaceho zoznamu
    Dim seznam As New LinkedList(Of Integer)()
    seznam.AddLast(1)
    seznam.AddLast(2)
    Dim prostredni As LinkedListNode(Of Integer) = seznam.AddLast(3)
    seznam.AddLast(4)
    seznam.AddLast(5)

' pridávanie a mazanie v prostriedku zozname
    seznam.AddAfter(prostredni, 32)
    seznam.AddAfter(prostredni, 31)
    seznam.Remove(prostredni)

' výpis zoznamu
    For Each i As Integer In seznam
        Console.Write("{0}, ", i)
    Next
    Console.WriteLine()

    Console.ReadKey()
{/VBNET_CONSOLE}

výstup:

Konzolová aplikácia
1, 2, 31, 32, 4, 5,

Práca so spojovým zoznamom je vďaka uzlom o niečo komplikovanejšie ako sa zoznamom cez pole List a väčšinou používame skôr List. Po LinkedList siahneme hlavne v prípade, keď chceme často vkladať a mazať prvky uprostred 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ť.

Dnes to bolo trochu kratšie, ale nechcel som začínať na konci novú tému.

V budúcej lekcii, Viacrozmerné polia vo VB .NET , si uvedieme diel o viacrozmerných poliach.

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š.