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 List
u 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š.
Stáhnout
Stažením následujícího souboru souhlasíš s licenčními podmínkami
Staženo 3x (187.88 kB)
Aplikace je včetně zdrojových kódů v jazyce VB