Láncolt Lista

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 Ez

Implementált interfészek