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š.
Stiahnuť
Stiahnutím nasledujúceho súboru súhlasíš s licenčnými podmienkami
Stiahnuté 568x (22.95 kB)
Aplikácia je vrátane zdrojových kódov v jazyku C#