2. diel - Zoznam (List) pomocou poľa v C#

V minulej lekcii, Úvod do kolekcií a genericita, sme si urobili úvod do kolekcií a ukázali sme si, čo je to genericita.

Dnes sa budeme v C# .NET tutoriálu venovať zoznamom (listom), čo je typ kolekcií, s ktorými sme sa počas seriálu už stretli.

Pole

Urobme si na začiatku malú odbočku späť k poľu, ktoré bolo prvou kolekciou, ktorú sme v seriáli spoznali v lekcii Pole v C# .NET. Pole sa vyznačuje tým, že má pevne daný počet prvkov. Z tohto dôvodu niekedy dokonca nebýva považované za kolekciu. Prvky v poli sú číselne indexované a to od nuly.

Hlavnou nevýhodou poľa teda je, že do neho nemôžeme za behu aplikácie prvky pridávať alebo ich mazať. To bohužiaľ často potrebujeme, aj keď sú situácie, keď je pole ideálna voľba. Touto daňou je vyvážená obrovská rýchlosť, s ktorou môžeme s prvkami poľa pracovať. Keďže dáta sú rovnakého typu (či už úplne rovnakého, alebo spoločného predka), zaberajú v pamäti rovnako miesta. Jednotlivé prvky poľa sú v pamäti uložené za sebou, ako v rade, ktorý je neprerušený. Pole celých čísel si môžeme predstaviť napr. takto:

Pokiaľ teda chceme napr. pristúpiť na 5. prvok, len vstúpime tam, kde pole začína a potom odskočíme 4 násobky veľkosti typu (tu int u) ďalej. Sme na 5. prvku. Čítanie a zápis na indexy v poli má teda konštantnú časovú zložitosť. Pokiaľ vás tento termín zmiatol, môžete to chápať tak, že do poľa zapisujeme okamžite a rovnako tak z neho aj čítame.

Pokiaľ v C# .NET založíme prázdne číselné pole, je automaticky naplnené nulami.

Zoznamy (Listy)

Zoznamy (anglicky a často aj slovensky list) sú kolekcie, ktoré umožňujú prvky za behu programu pridávať a mazať. Môžu byť číselne indexované ako pole, ale tiež nemusia. Sú v zásade 2 typy zoznamov.

Zoznamy s poľom

Zoznam najčastejšie využíva to, že hoci veľkosť poľa nemôžeme za behu programu meniť, môžeme za behu vytvoriť pole nové.

Zoznam je potom trieda, ktorá obsahuje metódy na pridanie a odstránenie prvkov (a mnoho ďalších, pre nás teraz nepodstatných metód). Trieda v podstate obaľuje pole a obsahuje navyše premennú, kde si uchováva počet prvkov. Pri vytvorení inštancie sa vytvorí pole napr. o 12tich prvkoch a premenná s počtom prvkov sa nastaví na 0. Pri pridaní prvého prvku sa prvok vloží na 1. index v poli a počet prvkov sa inkrementuje. Takto môžeme pridať až 12 prvkov, kým pole naplníme. Vo chvíli, keď vyčerpáme kapacitu poľa, jednoducho vytvoríme nové, napríklad 2x väčšie. Prvky zo starého poľa do neho skopírujeme a staré pole zahodíme. Keď sa toto nové pole opäť naplní, budeme situáciu opakovať. Takýmto spôsobom naozaj interne funguje kolekcia List, s ktorou sme doteraz pracovali. List s poľom si môžeme predstaviť asi takto:

List na obrázku má 8 prvkov. Prvky sú uložené v internom poli, ktoré má prvkov 12. Posledné 4 prvky sa nevyužívajú a List sa zvonku tvári ako že tam nie sú.

Výhodou je rýchlosť prístupu k prvkom pomocou indexov vďaka využitiu poľa. Nevýhodou je samozrejme časové oneskorenie potrebné na vytvorenie nového poľa a prekopírovanie prvkov, aj keď nastáva len občas. Ďalšou, aj keď menej bolestivou nevýhodou je, že kolekcia zaberá v pamäti viac priestoru, než je nutné. Tento typ zoznamu je napriek tomu najpoužívanejšou kolekciou v .NETe a je pomerne dobre optimalizovaný.

List s poľom je teda v .NETe zastúpený triedou List a jeho negenerický náprotivok je ArrayList. Popíšme si dôležité metódy na triede List:

Metódy a ďalšie prvky na triede List

List implementuje interface IList. Ten tvorí základ kolekcie a obsahuje nasledujúce metódy:

• Add() - Pridá nový prvok do listu.
• Clear() - Vymaže všetky prvky.
• Contains() - Vráti true, pokiaľ list obsahuje daný prvok.
• CopyTo() - Metódu už poznáme z poľa, umožňuje skopírovať prvky z listu do poľa.
• IndexOf() - Vráti index prvého výskytu daného prvku v liste.
• Insert() - Vloží na daný index nový prvok (a ďalšie prvky posunie).
• Remove() - Vymaže daný prvok. Táto funkcia je veľmi užitočná v prípade, že máme v List pri inštancii nejakej triedy (napr. užívateľa), nemusíme si držať ich číselné indexy, len zavoláme napr. list.Remove(charles), kedy odovzdáme konkrétnu inštanciu, ktorá sa má zo zoznamu odobrať..
• RemoveAt() - Vymaže prvok na danom indexe.

Hoci sme si List vyskúšali už 1000-krát, pre úplnosť si predsa len ukážme niekoľko riadkov kódu:

{CSHARP_CONSOLE}
List<int> list = new List<int>();
list.Add(5);
list.Add(10);
Console.WriteLine(list[0]);
{/CSHARP_CONSOLE}

Výstup programu:

Konzolová aplikácia
5

Kód vyššie vytvorí List typu int, pridá do neho 2 čísla a potom vypíše prvý prvok do konzoly. Pracujeme s indexmi ako by sme pracovali s poľom, ale môžeme do neho za behu programu pridávať prvky a tiež ich mazať.

Samotný List ešte dodáva ďalšie metódy, popíšme si aj tie:

• AddRange() - Pridá do listu prvky z odovzdaného poľa. Podobne môžeme volať aj metódy InsertRange() a RemoveRange(). Je dobrý nápad metódu využívať, pretože nám ušetrí cyklus. Jedinou zákernosťou je, že vie pridávať iba z poľa. Za chvíľu si ukážeme čo s tým.
• AsReadOnly() - Vráti inštanciu listu, z ktorej je možné prvky iba čítať. Vhodné na zapuzdrenie prvkov kolekcie.
• Count - Vlastnosť nesúca počet prvkov v liste. Všimnite si, že sa vlastnosť nemenuje Length (ako pri poli), pretože dĺžka listu je o niečo väčšia. Pravú dĺžku listu získame vlastností Capacity, aj keď nám tento údaj asi k ničomu nie je.
• Find() - Vyhľadá daný prvok pomocou predikátu (ktorý je, ako už vieme, delegátom). Je to veľmi jednoduché a efektívne, pretože môžeme použiť zápis cez lambda funkcie. Ukážme si, ako by sa na List pri type int vyhľadalo číslo väčšie ako 25:

{CSHARP_CONSOLE}

List<int> list = new List<int>();
list.Add(5);
list.Add(10);
list.Add(30);

int numbers = list.Find(a => a > 25);
Console.WriteLine(numbers);
{/CSHARP_CONSOLE}

Výstup programu:

Konzolová aplikácia
30

Find() vráti prvý nájdený prvok alebo predvolenú hodnotu typu pri neúspechu (pri objektoch null).

• FindAll() - Podobne ako Find() môžeme používať metódu FindAll(), ktorá nájde všetky zodpovedajúce prvky a vráti nový List, ktorý tieto nájdené prvky obsahuje:

{CSHARP_CONSOLE}

List<int> list = new List<int>();
list.Add(5);
list.Add(10);
list.Add(30);
list.Add(35);

List<int> numbersGreaterThan25 = list.FindAll(a => a > 25);
foreach (int c in numbersGreaterThan25)
    Console.WriteLine(c);
{/CSHARP_CONSOLE}

Výstup programu:

Konzolová aplikácia
30
35

Vďaka delegátom a lambda výrazom je všetko tak jednoduché. Ďalej list ponúka metódy FindIndex(), FindLast() a FindLastIndex(). Zaujímavá je ešte metóda BinarySearch(), ktorá vyhľadáva prvok rovnako ako Find(), ale je oveľa rýchlejšia. Predpokladom je však fakt, že je list zotriedený. Viac pri algoritme binárne vyhľadávanie

• Exists() - Exists() funguje podobne ako Find(), iba nevracia nájdený prvok ale true pokiaľ bol nejaký nájdený, inak false.
• LastIndexOf() - Obdoba metódy IndexOf(), vracia index posledného výskytu daného prvku v liste.
• RemoveAll() - Odstráni všetky prvky, ktoré zodpovedajú danému predikátu.
• Reverse() - Prevráti list tak, aby bol 1. prvok ako posledný a naopak posledný ako prvý.
• Sort() - Zotriedi list. Je dôležité, aby jeho prvky obsahovali rozhranie IComparable, inak metóda vyvolá výnimku. Základné triedy a štruktúry z .NETu IComparable implementujú, pri svojich triedach ho vieme dodať.
• ToArray() - Veľmi používaná metóda, ktorá vytvorí pole prvkov z listu a to vráti. Keďže pole je štandardná výmenná štruktúra v .NETe, budeme metódu používať veľmi často. Všimnite si, že napr. metóda AddRange() berie v parametri poľa, nie list. To aby bola univerzálna. Ak teda chceme skopírovať prvky jedného listu do druhého, urobíme to takto:

list1.AddRange(list2.ToArray());

Až na niekoľko metód sme si popísali celý list.

Vyskúšajte si ďalšie metódy ako Sort(), vyhľadávanie a podobne. Detailnejšiu prácu s kolekciami sa budeme ešte venovať, keď sa dostaneme k technológii LINQ.

V budúcej lekcii, Spojový zoznam v C#, si uvedieme 2. typ listu, ktorým je spojový zoznam.

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