Lekce 3 - Spojový seznam ve VB.NET

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

Dnes se ve VB.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 (někdy také říkáme uzly) 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 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). 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 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 odkazy prvku nasměrujeme mezi dva existující prvky, 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, bude 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 seznamu přes pole List, ale jsou v něm uloženy položky typu LinkedListNode. Jsou to prvky (uzly), které na sebe navzájem ukazují (propojují 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í.

Na seznamu LinkedList nalezneme tyto vlastnosti:

• Count - Vlastnost vracející počet prvků.
• First - Vlastnost vracející první prvek.
• Last - Vlastnost vracející poslední prvek.

Ukažme si metody, které má LinkedList oproti klasickému seznamu 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.
• Clear() - Odebere všechny prvky seznamu.
• Contains() - Určí zda je hodnota v seznamu.
• CopyTo() - zkopíruje všechny prvky seznamu na kompatibilní jednorozměrné pole (Array).
• Find() - vyhledá prvý prvek, který obsahuje zadanou hodnotu.
• FindLast() - vyhledá poslední prvek, který obsahuje zadanou hodnotu.
• Remove() - Odstraní první výskyt prvku (hodnoty).
• RemoveFirst() - Odstraní první prvek.
• RemoveLast() - Odstraní poslední prvek.

Příklad

Vytvoříme nový spojový seznam typu Integer, 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 druhý).

{VBNET_CONSOLE}
Dim seznam As New LinkedList(Of Integer)()
Dim hlava As LinkedListNode(Of Integer) = seznam.AddFirst(5)
seznam.AddAfter(hlava, 10)
Console.WriteLine(seznam.First.Value)
Console.WriteLine(seznam.First.[Next].Value)
{/VBNET_CONSOLE}

Výstup programu:

Konzolová aplikace
5
10

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

{VBNET_CONSOLE}
' inicializace a naplnění spojového seznamu
    Dim seznam As New LinkedList(Of Integer)()
    seznam.AddLast(1)
    seznam.AddLast(2)
    Dim prostredni As LinkedListNode(Of Integer) = 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
    For Each i As Integer In seznam
        Console.Write("{0}, ", i)
    Next
    Console.WriteLine()

    Console.ReadKey()
{/VBNET_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ž se seznamem přes pole List a většinou používáme spíše List. Po LinkedList sáhneme hlavně v případě, kdy chceme často vkládat a mazat prvky uprostř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.

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

V příští lekci, Vícerozměrné pole ve VB.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š.