Lekce 2 - Seznam (List) pomocí pole v C#

V minulé lekci, Úvod do kolekcí a genericita, jsme si udělali úvod do kolekcí a ukázali jsme si, co je to genericita.

Dnes se budeme v C# .NET tutoriálu věnovat seznamům (listům), což je typ kolekcí, se kterým jsme se během seriálu již setkali.

Pole

Udělejme si na začátku malou odbočku zpět k poli, které bylo první kolekcí, kterou jsme v seriálu poznali. Pole se vyznačuje tím, že má pevně daný počet prvků. Z tohoto důvodu někdy dokonce nebývá považováno za kolekci. Prvky v poli jsou číselně indexovány a to od nuly.

Hlavní nevýhodou pole tedy je, že do něj nemůžeme za běhu aplikace prvky přidávat nebo je mazat. To bohužel často potřebujeme, i když jsou situace, kdy je pole ideální volba. Touto daní je vyvážena obrovská rychlost, se kterou můžeme s prvky pole pracovat. Jelikož data jsou stejného typu (ať již úplně stejného, nebo společného předka), zabírají v paměti stejně místa. Jednotlivé prvky pole jsou v paměti uložené za sebou, jako v řadě, která je nepřerušená. Pole celých čísel si můžeme představit např. takto:

Pokud tedy chceme např. přistoupit na 5. prvek, jen vstoupíme tam, kde pole začíná a poté odskočíme 4 násobky velikosti typu (zde intu) dále. Jsme na 5. prvku. Čtení a zápis na indexy v poli má tedy konstantní časovou složitost. Pokud vás tento termín zmátl, můžete to chápat tak, že do pole zapisujeme okamžitě a stejně tak z něj i čteme.

Pozn. Pokud v C# .NET založíme prázdné číselné pole, je automaticky naplněno nulami.

Seznamy (Listy)

Seznamy (anglicky a často i česky list) jsou kolekce, které umožňují prvky za běhu programu přidávat a mazat. Mohou být číselně indexované jako pole, ale také nemusí. Jsou v zásadě 2 typy seznamů.

Seznamy s polem

Seznam nejčastěji využívá toho, že ačkoli velikost pole nemůžeme za běhu programu měnit, můžeme za běhu vytvořit pole nové.

Seznam je poté třída, která obsahuje metody pro přidání a odstranění prvků (a mnoho dalších, pro nás nyní nepodstatných metod). Třída v podstatě obaluje pole a obsahuje navíc proměnnou, kde si uchovává počet prvků. Při vytvoření instance se vytvoří pole např. o 12ti prvcích a proměnná s počtem prvků se nastaví na 0. Při přidání prvního prvku se prvek vloží na 1. index v poli a počet prvků se inkrementuje. Takto můžeme přidat až 12 prvků, než pole naplníme. Ve chvíli, kdy vyčerpáme kapacitu pole, jednoduše vytvoříme nové, třeba 2x větší. Prvky ze starého pole do něj zkopírujeme a staré pole zahodíme. Až se toto nové pole opět naplní, budeme situaci opakovat. Takovýmto způsobem opravdu interně funguje kolekce List, se kterou jsme doteď pracovali. List s polem si můžeme představit asi takto:

List na obrázku má 8 prvků. Prvky jsou uloženy v interním poli, které má prvků 12. Poslední 4 prvky se nevyužívají a List se zvenku tváří jako že tam nejsou.

Výhodou je rychlost přístupu k prvkům pomocí indexů díky využití pole. Nevýhodou je samozřejmě časová prodleva nutná k vytvoření nového pole a překopírování prvků, i když nastává jen občas. Další, i když méně bolestivou nevýhodou je, že kolekce zabírá v paměti více prostoru, než je nutné. Tento typ seznamu je přesto nejpoužívanější kolekcí v .NETu a je poměrně dobře optimalizován.

List s polem je tedy v .NETu zastoupen třídou List a jeho negenerický protějšek je ArrayList. Popišme si důležité metody na třídě List:

Metody a další prvky na třídě List

List implementuje interface IList. Ten tvoří základ kolekce a obsahuje následující metody:

• Add() - Přidá nový prvek do listu.
• Clear() - Vymaže všechny prvky.
• Contains() - Vrátí true, pokud list obsahuje daný prvek.
• CopyTo() - Metodu již známe z pole, umožňuje zkopírovat prvky z listu do pole.
• IndexOf() - Vrátí index prvního výskytu daného prvku v listu.
• Insert() - Vloží na daný index nový prvek (a další prvky posune).
• Remove() - Vymaže daný prvek. Tato funkce je velmi užitečná v případě, že máme v Listu instance nějaké třídy (např. uživatele), nemusíme si držet jejich číselné indexy, jen zavoláme např. list.Remove(karel), kdy předáme konkrétní instanci, která se má ze seznamu odebrat..
• RemoveAt() - Vymaže prvek na daném indexu.

Ačkoli jsme si List vyzkoušeli již 1000krát, pro úplnost si přeci jen ukažme několik řádků 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á aplikace
5

Kód výše vytvoří List typu int, přidá do něj 2 čísla a poté vypíše první prvek do konzole. Pracujeme s indexy jako bychom pracovali s polem, ale můžeme do něj za běhu programu přidávat prvky a také je mazat.

Samotný List ještě dodává další metody, popišme si i ty:

• AddRange() - Přidá do listu prvky z předaného pole. Podobně můžeme volat i metody InsertRange() a RemoveRange(). Je dobrý nápad metodu využívat, jelikož nám ušetří cyklus. Jedinou záludností je, že umí přidávat pouze z pole. Za chvíli si ukážeme co s tím.
• AsReadOnly() - Vrátí instanci listu, ze které lze prvky pouze číst. Vhodné pro zapouzdření prvků kolekce.
• Count - Vlastnost nesoucí počet prvků v listu. Všimněte si, že se vlastnost nejmenuje Length (jako u pole), jelikož délka listu je o něco větší. Pravou délku listu získáme vlastností Capacity, i když nám tento údaj asi k ničemu není.
• Find() - Vyhledá daný prvek pomocí predikátu (který je, jak již víme, delegátem). Je to velmi jednoduché a efektivní, jelikož můžeme použít zápis přes lambda funkce. Ukažme si, jak by se na Listu typu int vyhledalo číslo větší než 25:

{CSHARP_CONSOLE}

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

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

Výstup programu:

Konzolová aplikace
30

Find() vrátí první nalezený prvek nebo výchozí hodnotu typu při neúspěchu (u objektů null).

• FindAll() - Podobně jako Find() můžeme používat metodu FindAll(), která najde všechny odpovídající prvky a vrátí nový List, který tyto nalezené prvky obsahuje:

{CSHARP_CONSOLE}

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

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

Výstup programu:

Konzolová aplikace
30
35

Díky delegátům a lambda výrazům je vše tak snadné. Dále list nabízí metody FindIndex(), FindLast() a FindLastIndex(). Zajímavá je ještě metoda BinarySearch(), která vyhledává prvek stejně jako Find(), ale je mnohem rychlejší. Předpokladem je však fakt, že je list setříděný. Více u algoritmu binární vyhledávání

• Exists() - Exists() funguje podobně jako Find(), pouze nevrací nalezený prvek ale true pokud byl nějaký nalezený, jinak false.
• LastIndexOf() - Obdoba metody IndexOf(), vrací index posledního výskytu daného prvku v listu.
• RemoveAll() - Odstraní všechny prvky, které odpovídají danému predikátu.
• Reverse() - Převrátí list tak, aby byl 1. prvek jako poslední a naopak poslední jako první.
• Sort() - Setřídí list. Je důležité, aby jeho prvky obsahovaly rozhraní IComparable, jinak metoda vyvolá výjimku. Základní třídy a struktury z .NETu IComparable implementují, u svých tříd ho umíme dodat.
• ToArray() - Velmi používaná metoda, která vytvoří pole prvků z listu a to vrátí. Jelikož pole je standardní výměnná struktura v .NETu, budeme metodu používat velmi často. Všimněte si, že např. metoda AddRange() bere v parametru pole, nikoli list. To aby byla univerzální. Pokud tedy chceme zkopírovat prvky jednoho listu do druhého, uděláme to takto:

list1.AddRange(list2.ToArray());

Až na několik metod jsme si popsali celý list.

Vyzkoušejte si další metody jako Sort(), vyhledávání a podobně. Detailnější práci s kolekcemi se budeme ještě věnovat, až se dostaneme k technologii LINQ.

V příští lekci, Spojový seznam v C#, si uvedeme 2. typ listu, kterým je spojový seznam.

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.