A tömb adatszerkezet kiváló, ha előre tudjuk, hogy mennyi elemre van szükségünk. Abban az esetben viszont, ha nem tudjuk előre, hogy mennyi elemünk lesz, akkor nehezen tudjuk bővíteni a későbbiekben.
Lényegében a bővítés csak úgy lehetséges, hogy létrehozunk egy újabb tömböt, aminek a mérete a hozzáadandó elemek számával meg van növelve. Az új tömbbe átmásoljuk a meglévő tömb elemeit, majd az új tömbhöz hozzáadjuk az új elemeket. Végezetül pedig töröljük az eredeti tömböt.
Az algoritmus leírásból kiolvasható, hogy ez nem éppen ideális, mivel a sebességre igen negatív hatással van a másolás. Továbbá a másolás folyamán egy rövid időre duplázódik a programunk memóriahasználata.
Egy sokkal jobb megoldás lehet nagy mennyiségű, előre nem ismert számú adat tárolására a láncolt lista szerkezet. Ennek lényege, hogy van egy láncszem típusunk, amely tartalmazza a tárolni kívánt elemi típust és egy referenciát a következő elemre. Ha a referencia a következő elemre nem létezik, akkor a lánc végén vagyunk.
Ezt a megoldást hívjuk egyszeresen láncolt listának. Ennek hátránya, hogy az elemeken csak sorban tudunk végighaladni az elejétől a végéig. Viszont, ha kiegészítjük a láncszem típusunkat egy referenciával, ami az előző láncelemre mutat, akkor kétszeresen láncolt listát kapunk, amiben szabadon mozoghatunk előre és hátra is. Valamint a lánc ebben az esetben bővíthető az elején és a végén is, míg az egyszeresen láncolt listánk csak a végén bővíthető.
Ezen adatszerkezet előnye, hogy ugyanazzal a sebességgel a végtelenségig bővíthető a lánc. Hátránya viszont az, hogy csak szekvenciális olvasást tud gyorsan. Egy adott elem indexhez csak úgy tudunk eljutni a láncban, hogy az elejétől elkezdjük olvasni az elemeket és megállunk a kívánt elemnél.
A .NET láncolt lista implementációja nem meglepő módon a LinkedList osztálynevet kapta. Az alábbi fontosabb metódusokkal és tulajdonságokkal rendelkezik:
LinkedListNode<T> First { get; }
Referencia a lánc első elemére.
LinkedListNode<T> Last { get; }
Referencia a lánc utolsó elemére.
LinkedListNode<T> AddAfter(LinkedListNode node, T value)
A lánc bővítése az első paraméter által meghatározott elem után. A második paraméter az értéket határozza meg. A metódus visszatérési értéke az újonnan létrejött láncelem.
LinkedListNode<T> AddBefore(LinkedListNode node, T value)
A lánc bővítése az első paraméter által meghatározott elem előtt. A második paraméter az értéket határozza meg. A metódus visszatérési értéke az újonnan létrejött láncelem.
LinkedListNode<T> Find(T value)
Kikeresi a paraméter által meghatározott értékhez tartozó első láncelemet.
LinkedListNode<T> FindLast(T value)
Kikeresi a paraméter által meghatározott értékhez tartozó utolsó láncelemet.
LinkedListNode<T> AddFirst(T value)
Lánc bővítése az elején. A meghatározott érték által létrejövő láncelem lesz a lánc első eleme. A metódus visszatérési értéke az újonnan létrejött láncelem.
LinkedListNode<T> AddLast(T value)
Lánc bővítése a végén. A meghatározott érték által létrejövő láncelem lesz a lánc utolsó eleme. A metódus visszatérési értéke az újonnan létrejött láncelem.
void RemoveFirst()
Lánc első elemének eltávolítása. A metódus hívása után a második láncelem lesz az új első.
void RemoveLast()
Lánc utolsó elemének eltávolítása. A metódus hívása után az utolsó előtti láncelem lesz az új utolsó.
A láncolt lista szerkezethez tartozó belső láncelem, LinkedListNode osztály tulajdonságai:
LinkedListNode<T> Next { get; }
A következő láncelemre mutató referencia
LinkedListNode<T> Previous { get; }
Az előző láncelemre mutató referencia
T Value { get; set; }
A láncelem által tárolt érték lekérdezése vagy beállítása.
A következő mintaprogram a láncolt lista használatát mutatja be:
using System;
using System.Collections.Generic;
namespace PeldaLancolt
{
class Program
{
static void Main(string[] args)
{
var lista = new LinkedList<string>();
//jobbról bővítés
lista.AddLast("egy");
lista.AddLast("példa");
lista.AddLast("program");
lista.AddLast("lenne");
//balról bővítés
lista.AddFirst("Ez");
Console.WriteLine("Lánc elemek száma: {0}", lista.Count);
Console.WriteLine("Lánc tartalma előre: ");
//a foreach automatikusan a value elemet szedi ki
foreach (var elem in lista)
{
Console.Write("{0} ", elem);
}
Console.WriteLine("\nLánc tartalma vissza: ");
var vissza = lista.Last;
while (vissza != null)
{
Console.Write("{0} ", vissza.Value);
vissza = vissza.Previous;
}
Console.ReadKey();
}
}
}
A program kimenete:
Lánc elemek száma: 5
Lánc tartalma elore:
Ez egy példa program lenne
Lánc tartalma vissza:
lenne program példa egy EzImplementált interfészek
