3. diel - Spojkový zoznam v C#

V minulej lekcii, Zoznam (List) pomocou poľa v C#, sme si predstavili zoznamy (listy) a detailne popísali zoznam pomocou poľa a triedu List.

Dnes sa v kurze C# .NET zameriame na druhý typ zoznamu, ktorým je spojkový zoznam.

Spojkové zoznamy

Druhou možnosťou vytvorenia zoznamu s premenným počtom prvkov sú tzv. spojkové 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, keď prvý prvok ukazuje na druhý, druhý na tretí a tak ďalej. Prvky z minulého príkladu by sme si v spojkovom zozname mohli predstaviť napr. takto:

Takému spojkovému zoznamu sa hovorí jednosmerný (Singly Linked List). Pokiaľ 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 spojkovom zozname (Doubly Linked List). Ten by v našom prípade vyzeral nejako takto:

Pri spojkových zoznamoch 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ží od počtu prvkov v liste.

Niekedy však nepotrebujeme prvky indexovať a v tej chvíli sa táto kolekcia stáva veľmi výhodnou. 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, pokiaľ nám bude stačiť pamäť. Pomerne dobre môžeme mazať aj prvky uprostred zoznamu alebo vkladať nové prvky medzi existujúce. Pri poli bolo vloženie prvku možné iba tak, že sme všetky prvky napravo posunuli a vytvorili tak miesto pre nový prvok. To nás stálo nemalý výpočtový čas, ktorý bol závislý od počtu prvkov. V spojkovom zozname iba prvok naodkazujeme medzi dva existujúce, 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 pri dátových štruktúrach a algoritmoch býva, niečo za niečo

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

Tieda LinkedList

Spojkový zoznam je v .NET reprezentovaný generickou kolekciou LinkedList. Jedná sa o spojkový zoznam obojsmerný, jednosmerný spojkový 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 kolekcii List, 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ú vlastnosťou Value. Práve v tej je ešte len uložený náš prvok, ktorý uzol obaľuje. Dodáva tak nášmu prvku väzby na prvky okolité. Ukážme si metódy, ktoré má LinkedList oproti klasickému 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.
• 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 pri liste:

{CSHARP_CONSOLE}
LinkedList<int> list = new LinkedList<int>();
LinkedListNode<int> head = list.AddFirst(5);
list.AddAfter(head, 10);
Console.WriteLine(list.First.Value);
Console.WriteLine(list.First.Next.Value);
{/CSHARP_CONSOLE}

Výstup programu:

Konzolová aplikácia
5
10

Vytvoríme nový spojkový zoznam typu int, 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ý).

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

{CSHARP_CONSOLE}
// initialization and filling of the linked list
LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
LinkedListNode<int> middle = list.AddLast(3);
list.AddLast(4);
list.AddLast(5);

// adding and deleting in the middle of the list
list.AddAfter(middle, 32);
list.AddAfter(middle, 31);
list.Remove(middle);

// printing the list
foreach (int i in list)
    Console.Write("{0}, ", i);

Console.ReadKey();
{/CSHARP_CONSOLE}

Výstup:

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

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

Ešte jednu poznámku predtým, ako listy úplne opustíme. V starých zdrojových kódoch môžete naraziť na kolekciu StringCollection. Tá suplovala za List<string> v dobách, kedy kolekcie v .NET neboli generické. Dnes už nie je dôvod túto triedu používať a spôsobuje skôr zmätok.

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

V nasledujúcej lekcii, Viacrozmerné polia v C# .NET, si predstavíme viacrozmerné polia.

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