• Ta verižni seznam je nekoliko drugačen!
• Dvojno povezan verižni seznam
• Poznamo kazalca na predhodnika in naslednika

• Dejansko bomo mi uporabljali LinkedListNode (no, različico, ki pozna le naslednika, ne pa tudi prednika)

  • Torej omejili se bomo na posamezne vozle in ročno skrbeli za njihovo povezovanje

• Elementi - vozli
• Vozel - objekt

• Komponente

  • Prostor za podatke
  • Referenca na naslednjega

public class Vozel<T> {
  private T podatek; // hranimo podatke tipa T
  private Vozel<T> naslednji; // referenca na naslednjega
  // konstruktorji
  // Lastnosti: Vsebina, Nasl

public T Vsebina {
    get { return this.podatek; }
    set { this.podatek = value; }
}
public Vozel<T> Nasl{
    get { return this.naslednji; }
    set { this.naslednji = value; }
}

public Vozel(){
    this.Vsebina = default(T);
        // kot je privzeta vrednost za tip T
    this.Nasl = null;
}

• 1. primer

  • Ustvarimo tri vozle in jih povežimo med sabo
  • Izpišimo vsebino vseh treh, če poznamo referenco le na prvega
  • Spremeni vsebino prvega
  • Spremeni vsebino tretjega

• 2.primer

  • V obstoječo verigo treh vozlov dodaj nov vozel na začetek
  • Sedaj pa še na konec
• Sestavi metodo, ki izpiše vsebino vseh vozlov v verigi

Vozel<int> prvi = new Vozel<int>();
Vozel<int> drugi = new Vozel<int>();
Vozel<int> tretji = new Vozel<int>();
prvi.Vsebina = 12;
drugi.Vsebina = 42;
drugi.Nasl = prvi;
tretji.Vsebina = 13;
tretji.Nasl = drugi;

Vozel<int> zac = tretji;
prvi = null; drugi = null; tretji = null; // znebimo se naslovov
Console.WriteLine(zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine(zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine(zac.Nasl.Nasl.Vsebina); // vsebina tretjega v verigi

zac.Vsebina = 111;
zac.Nasl.Nasl.Vsebina = 1;
Console.WriteLine(zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine(zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine(zac.Nasl.Nasl.Vsebina); // vsebina tretjega v verigi

// dodaj na začetek
 Vozel<int> nov = new Vozel<int>();
 nov.Vsebina = 1000;
 // povežemo
 nov.Nasl = zac;
 // dobili smo nov začetek
 zac = nov;

Vozel<int> prvi = new Vozel<int>(); Vozel<int> drugi = new Vozel<int>(); Vozel<int> tretji = new Vozel<int>(); prvi.Vsebina = 12; drugi.Vsebina = 42;  drugi.Nasl = prvi; tretji.Vsebina = 13; tretji.Nasl = drugi;

Vozel<int> zac = tretji;
prvi = null; drugi = null; tretji = null; // znebimo se naslovov
Console.WriteLine("vsebina prvega v verigi: " + zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine("vsebina drugega v verigi: " + zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine("vsebina tretjega v verigi: " + zac.Nasl.Nasl.Vsebina); // vsebina tretjega
// dodaj na začetek
Vozel<int> nov = new Vozel<int>(); nov.Vsebina = 1000;
// povežemo
nov.Nasl = zac;
// dobili smo nov začetek
zac = nov;
Console.WriteLine("vsebina prvega v verigi: " + zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine("vsebina drugega v verigi: " + zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine("vsebina tretjega v verigi: " + zac.Nasl.Nasl.Vsebina); // vsebina tretjega
// sedaj imamo še četrtega
Console.WriteLine("vsebina četrtega v verigi: " + zac.Nasl.Nasl.Nasl.Vsebina); // vsebina četrtega

• Izpišemo vsebino verižnega seznama na začetek katerega kaže zacSez

• Ideja:

  • Vzamemo kazalec s katerim se premikamo po verigi

  • Naslednji v verigi:

    • kjeSmo = kjeSmo.Nasl;

  • Konec:

    • kjeSmo == null

public static void IzpisVerige<T>(Vozel<T> zacSez)
{
    // izpišemo vsebino verige, na katere začetek kaže zacSez
    Vozel<T> kjeSmo; // kazalec za premikanje
    kjeSmo = zacSez;
    Console.Write("Začetek: ");
    while (zacSez != null) // do konca seznama
    {
        Console.Write(zacSez.Vsebina + " -> ");
        zacSez = zacSez.Nasl; // na naslednji vozel
    }
    Console.WriteLine("KONEC");
}

public static Vozel<T> VstaviTab<T> (T[] pod)
{
    // Sestavi novo verigo, kamor vstavi podatke iz tabele pod
    Vozel<T> prvi = null; // začetek verige
    for (int i = 0; i < pod.Length; i++)
    {
        Vozel<T> nov = new Vozel<T>(); // vozel za nove podatke
        nov.Vsebina = pod[i]; nov.Nasl = prvi; // dodamo na začetek
        prvi = nov; // nov začetek
    }
    return prvi;
}

int[] podatki = { 11, 23, 34, 45, 555, 67 };
Vozel<int> verigaŠtevil = VstaviTab(podatki);
// izpis
Console.WriteLine("Prvi izpis: ");
IzpisVerige(verigaŠtevil);
// in še enkrat
Console.WriteLine("še drugi izpis: ");
IzpisVerige(verigaŠtevil);

public Vozel(T x) : this(){
  this.Vsebina = x;
}

public Vozel(V v) : this(){
    this.Nasl = v;
}

public Vozel(Vozel v, T x):this(x) {
    this.Nasl = v;
}