BF Summer sales
Pouze tento týden sleva až 80 % na HTML & CSS a JavaScript
80 % bodů zdarma na online výuku díky naší Letní akci!

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:

Jednosměrný spojový seznam v C# .NET

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:

Obousměrný spojový seznam v C# .NET

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.

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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:

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);

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ů:

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

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, se podíváme na vícerozměrná pole.


 

Stáhnout

Staženo 432x (22.95 kB)
Aplikace je včetně zdrojových kódů v jazyce C#

 

Předchozí článek
Seznam (List) pomocí pole v C#
Všechny články v sekci
Kolekce a LINQ v C# .NET
Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
12 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity (10)

 

 

Komentáře

Avatar
stacox
Člen
Avatar
stacox:18.2.2013 16:32

Sice se jedná o triviálnost, ale mám za to, že máš popisky metod LinkedList prohozený :)
-
AddAfter - Přidá prvek před daný prvek.
AddBefore - Přidá prvek za daný prvek.

 
Odpovědět
18.2.2013 16:32
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na stacox
David Čápka:18.2.2013 17:27

Díky, opraveno :)

Odpovědět
18.2.2013 17:27
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
pracansky
Člen
Avatar
pracansky:11.4.2015 23:00

Z popisu toho listu jsem pochopil že při každém překročení hranice 12 prvků se všechna data kopírují. A při mazání dokonce pokaždé. To je asi při větších velikostech problém.

Naproti tomu vázaný seznam je sice možné snadno rozšiřovat i zkracovat, ale není možné jej rychle indexovat.

Existuje nějaké alternativa která která má výhody obou (rychlé změny i indexový přístup) i za cenu většího plýtvání pamětí?

 
Odpovědět
11.4.2015 23:00
Avatar
Patrik Bak
Člen
Avatar
Patrik Bak:7.10.2015 0:27

Kde v praxi má toto význam použiť ?

 
Odpovědět
7.10.2015 0:27
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Ondra Toman
Člen
Avatar
Ondra Toman:6. ledna 0:09

Chápu teda správně, že LinkedListNode je jakýsi přístupový bod do určitého místa v seznamu?
pokud budu mít takovýto seznam:

2 - první
7
5 - node
3 - posledí

můžu k 7 přistoupit jako "prvek před node"?

 
Odpovědět
6. ledna 0:09
Avatar
Nositelka Změny:27. ledna 13:24

Chápu správně, že List<> (popř. ArrayList) ve skutečnosti není žádný seznam, ale úplně obyčejné dynamické pole (něco jako vector v C++)?

Odpovědět
27. ledna 13:24
j.k.j
Avatar
Odpovídá na Nositelka Změny
Ing. Petr Štechmüller:27. ledna 14:08

Ahoj, ano, reálná implementace List, nebo ArrayList je ve skutečnosti dynamické pole.
Doporučuji se podívat přímo na zdrojáky jak Listu, tak ArrayListu ;-)

Z nich poznáš, co se tam přesně děje :)

Odpovědět
27. ledna 14:08
Pokud spolu kód a komentář nekorespondují, budou patrně oba chybné
Avatar
David Holohlavský:10. května 21:30

Díky za článek. ;-)

 
Odpovědět
10. května 21:30
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 8 zpráv z 8.