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

V minulé lekci, Úvod do kolekcí a genericita, jsme si probrali ú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í, s nimiž jsme se během seriálu již setkali.

Pole

Udělejme si na začátku malou odbočku zpět k poli, jež bylo první kolekcí, kterou jsme v seriálu poznali v lekci Pole v C# .NET. 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 z něj mazat. To však bohužel často potřebujeme, i když jsou situace, kdy je pole ideální volbou. Touto daní je vyvážena obrovská rychlost, s níž 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 pátý prvek, jen vstoupíme tam, kde pole začíná, a poté odskočíme čtyři násobky velikosti typu (zde typu int) dále. Jsme na pátém prvku. Čtení i zápis na indexy v poli mají tedy konstantní časovou složitost. Pokud by vás tento termín zmátl, můžete ho 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 i mazat. Mohou být číselně indexované jako pole, ale také nemusí. Existují v zásadě dva typy seznamů.

Seznamy s polem

Seznam nejčastěji využívá toho, že ačkoli za běhu programu nemůžeme měnit velikost pole, můžeme tehdy 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í vedlejší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 dvanácti 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 první index v poli a počet prvků se inkrementuje. Takto můžeme přidat až dvanáct prvků, než pole naplníme. Ve chvíli, kdy vyčerpáme kapacitu pole, jednoduše vytvoříme pole nové, třeba dvakrát 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í, situaci zopakujeme. Takovýmto způsobem opravdu interně funguje kolekce List, s níž jsme doteď pracovali. List s polem si můžeme představit asi takto:

List na obrázku má osm prvků. Prvky jsou uloženy v interním poli, které má prvků dvanáct. Poslední čtyři 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 .NET a je poměrně dobře optimalizován.

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

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 totiž 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ž tisíckrát, pro úplnost si přece 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 dvě čísla a poté vypíše první prvek do konzole. S indexy pracujeme, 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(). Tuto metodu je dobrý nápad využívat, jelikož nám ušetří cyklus. Jedinou záludností je, že metoda umí přidávat pouze z pole. Za chvíli si ukážeme, jak s tím naložit.
• 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ěme 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 prostřednictvím lambda funkcí. Ukažme si, jak by se na seznamu List 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 i 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é. List dále 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 jejího využití 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(), avšak nevrací nalezený prvek, nýbrž true, pokud byl nějaký prvek nalezený. V opačném případě vrací 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 první 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 .NET IComparable implementují, u vlastních tříd ho umíme dodat.
• ToArray() – Frekventovaně používaná metoda, která vytvoří pole prvků z listu a dané pole vrátí. Jelikož pole je standardní výměnná struktura v .NET, budeme metodu používat velmi často. Povšimněme si, že např. metoda AddRange() bere v parametru pole, nikoli list. To proto, aby byla univerzální. Chceme-li tedy 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 druhý 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š.