Lekce 3 - Spojový seznam v C#

V minulé lekci, Seznam (list) pomocí pole v C#, jsme si představili seznamy (listy) a detailně jsme 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é (nejsou tedy již uložené za sebou) a po sobě jdoucí prvky na sebe odkazují. Můžeme si to představit jako takový řetězec, kdy první 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 dva po sobě jdoucí prvky ukazují navzájem (tedy i druhý na první a tak dále). Pak 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 stý prvek a přečíst jeho hodnotu. Když chceme ke stému prvku přistoupit, musíme jít z prvního prvku na druhý, z druhého na třetí a tak dále až do stovky. Časová složitost čtení i zápisu na index tedy závisí 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 či mazat tak dlouho, dokud nám bude stačit paměť. Poměrně dobře můžeme mazat i 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ý závisel na počtu prvků. Ve spojovém seznamu prvek pouze naodkazujeme mezi dva existující, ostatních prvků se změna nedotkne.

Máme tedy efektivní vkládání a mazání prvků za cenu neefektivního přístupu k indexům. 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ší. Budeme-li často přistupovat k prvkům pomocí indexu, bude spojový seznam katastrofou. Budeme-li naopak prvky často vkládat nebo mazat uprostřed kolekce, spojový seznam si s tím hravě poradí, avšak list s polem by byl extrémně pomalý.

LinkedList

Spojový seznam je v .NET reprezentovaný generickou kolekcí LinkedList. Jedná se o spojový seznam obousměrný, jednosměrný spojový seznam v .NET 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 seznamu List, ale jsou v něm uloženy položky typu LinkedListNode. Jsou to uzly, které na sebe navzájem ukazují (odkazují na sebe, chcete-li) a disponují vlastností Value. Právě v té je teprve uložen náš prvek, který je uzlem obalen. Uzel tak dodává našemu prvku ony vazby na prvky okolní. Ukažme si metody, které má LinkedList oproti klasickému List 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 první 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 ten druhý).

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í veprostřed 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 kvůli 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 uprostřed seznamu, což by u listu bylo velmi pomalé.

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

Dnes to bylo trochu kratší, abychom na konci nezačínali nové téma.

V příští lekci, Vícerozměrná pole v C# .NET, si představíme vícerozměrná pole.

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