Lekce 3 - Spojový seznam v C#

V minulé lekci, Seznam (List) pomocí pole v C#, jsme si představili seznamy (listy) a detailně popsali seznam pomocí pole a třídu List.

Dnes se v C# .NET tutoriálu zaměříme na druhý typ seznamu, kterým je spojový seznam.

Spojové seznamy

Druhou možností vytvoření seznamu s proměnným počtem prvků jsou tzv. spojové seznamy. Ty již s polem vůbec nepracují a jsou založené na odlišném principu. Jednotlivé prvky v listu jsou v paměti různě rozházené (již tedy nejsou uložené za sebou) a po sobě jdoucí prvky na sebe odkazují. Můžeme si to představit jako takový řetězec, kdy 1. prvek ukazuje na druhý, druhý na třetí a tak dále. Prvky z minulého příkladu bychom si ve spojovém seznamu mohli představit např. takto:

Takovému spojovému seznamu se říká jednosměrný (Singly Linked List). Pokud nemáme nějaký vážný důvod šetřit pamětí, obvykle na sebe 2 po sobě jdoucí prvky ukazují navzájem (tedy i 2. na první a tak dále). Hovoříme o obousměrném spojovém seznamu (Doubly Linked List). Ten by v našem případě vypadal nějak takto:

U spojových seznamů jsme přišli o možnost rychle přistoupit k prvku podle jeho indexu a to kvůli tomu, že prvky již nejsou v paměti za sebou. Neexistuje způsob, jak efektivně přeskočit rovnou např. na 100. prvek a přečíst jeho hodnotu. Když chceme k 100. prvku přistoupit, musíme z prvního prvku na druhý, z druhého na třetí a tak dále až do stovky. Časová složitost čtení a zápisu na index tedy záleží na počtu prvků v listu.

Někdy však nepotřebujeme prvky indexovat a v tu chvíli se tato kolekce stává velmi výhodnou. Již na začátku jsme si řekli, že s polem vůbec nepracujeme. Již nejsme nijak omezeni délkou seznamu a položky můžeme za běhu programu přidávat a mazat tak dlouho, dokud nám bude stačit paměť. Poměrně dobře můžeme i mazat prvky uprostřed seznamu nebo vkládat nové prvky mezi existující. U pole bylo vložení prvku možné pouze tak, že jsme všechny prvky napravo posunuli a vytvořili tak místo pro nový prvek. To nás stálo nemalý výpočetní čas, který byl závislý na počtu prvků. Ve spojovém seznamu pouze prvek naodkazujeme mezi 2 existující, ostatních prvků se změna nedotkne.

Máme tedy efektivní vkládání a mazání prvků na úkor neefektivního přístupu na indexy. Tak už to u datových struktur a algoritmů vůbec bývá, něco za něco

Vidíme, že spojový seznam a seznam přes pole se velmi liší. Pokud budeme často přistupovat k prvkům pomocí indexu, byl by spojový seznam katastrofou. Pokud budeme naopak prvky často vkládat nebo mazat uprostřed kolekce, spojový seznam si s tím hravě poradí a list s polem by byl extrémně pomalý.

LinkedList

Spojový seznam je v .NETu reprezentovaný generickou kolekcí LinkedList. Jedná se o spojový seznam obousměrný, jednosměrný spojový seznam v .NETu nenajdeme. Mohli bychom si ho naprogramovat, ale nemá to příliš význam, jelikož se s ním hůře pracuje a úspora paměti je mizivá.

LinkedList neobsahuje rovnou naše prvky jako tomu bylo u Listu, ale jsou v něm uloženy položky typu LinkedListNode. Jsou to uzly, které na sebe navzájem ukazují (odkazují se, chcete-li) a disponují vlastností Value. Právě v té je teprve uložen náš prvek, který uzel obaluje. Dodává tak našemu prvku ony vazby na prvky okolní. Ukažme si metody, které má LinkedList oproti klasickému Listu navíc:

• AddAfter() - Přidá nový prvek za daný prvek.
• AddBefore() - Přidá nový prvek před daný prvek.
• AddFirst() - Přidá nový prvek na začátek seznamu.
• AddLast() - Přidá nový prvek na konec seznamu.
• First - Vlastnost vracející první prvek.
• Last - Vlastnost vracející poslední prvek.
• RemoveFirst() - Odstraní první prvek.
• RemoveLast() - Odstraní poslední prvek.

Příklad

Vyzkoušejme si podobný příklad jako u listu:

{CSHARP_CONSOLE}
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);
{/CSHARP_CONSOLE}

Výstup programu:

Konzolová aplikace
5
10

Vytvoříme nový spojový seznam typu int, přidáme 1. prvek a uložíme si ho jako hlavu. Za hlavu přidáme další prvek. Nakonec vypíšeme první prvek a prvek po prvním prvku (tedy 2.).

Zkusme si ještě ono rychlé vkládání a mazání prvků:

{CSHARP_CONSOLE}
// 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();
{/CSHARP_CONSOLE}

Výstup:

Konzolová aplikace
1, 2, 31, 32, 4, 5,

Práce se spojovým seznamem je díky uzlům o něco komplikovanější než s Listem a většinou používáme spíše List. Po "spojáku" sáhneme hlavně v případě, kdy chceme často vkládat a mazat prvky doprostřed seznamu, což by u Listu bylo velmi pomalé.

Ještě poznámku, než listy úplně opustíme. Ve starých zdrojových kódech můžete narazit na kolekci StringCollection. Ta suplovala za List<string> v dobách, kdy kolekce v .NETu nebyly generické. Dnes již není důvod tuto třídu používat a způsobuje spíše zmatení.

Dnes to bylo trochu kratší, ale nechtěl jsem začínat na konci nové téma.

V příští lekci, Vícerozměrná pole v C# .NET, si uvedeme díl o vícerozměrných polích.

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