3. díl - Spojový seznam v C#

C# .NET Kolekce a LINQ Spojový seznam v C#

V minulém díle seriálu tutoriálů o C# .NET jsme si představili seznamy (listy) a detailně popsali seznam pomocí pole a třídu List. Dnes se 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 zasebou) 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

Takovému spojovému seznamu se říká jednosměrný (Single 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 (Double Linked List). Ten by v našem případě vypadal nějak takto:

Obousměrný spojový seznam

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 zasebou. 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á.

LinekdList 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 prvky ony vazby na prvky okolní. Ukažme si metody, které má LinkedList oproti klasickému Listu navíc:

  • AddAfter - Přidá prvek za daný prvek.
  • AddBefore - Přidá prvek před daný prvek.
  • AddFirst - Přidá prvek na začátek seznamu.
  • AddLast - Přidá 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:

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:

Spojový seznam v C# .NET

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


 

Stáhnout

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
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 se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (2 hlasů) :
4.54.54.54.54.5


 


Miniatura
Předchozí článek
Seznam (List) pomocí pole v C#
Miniatura
Všechny články v sekci
Kolekce v C# .NET a LINQ
Miniatura
Následující článek
Vícerozměrná pole v C# .NET

 

 

Komentáře

Avatar
stacox
Člen
Avatar
stacox:

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ět 18.2.2013 17:27
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
pracansky
Člen
Avatar
pracansky:

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:

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

 
Odpovědět 7.10.2015 0:27
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 4 zpráv z 4.