20/21: Programiranje IT 4 - ogled

Jednostruko spregnuta lista je lista elemenata koji mogu da se nalaze bilo gde u memoriji i koji su povezani linkom ili pokazivačem. U svakom elementu liste se nalaze neki podaci plus pokazivač na sledeći element u listi. Samo poslednji element u listi, pošto je zadnji, na tom mestu ima null.

Ilustracija: Jednostruko spregnuta lista

Ovo je dinamička struktura podataka. Može da se koristi, na primer, za predstavljanje nizova podataka. U tom slučaju se svaki element nalazi na nekom proizvoljnom mestu u memoriji i međusobno se povezuju pokazivačima. Elementi u listi se dinamički stvaraju i uništavaju. Drugim rečima, broj elemenata u listi može da se menja u toku izvršavanja programa (umetanje novil elemenata ili brisanje postojećih). Koliko se elemenata može smestiti u listu zavisi samo od veličine memorije koju imate u računaru.

Logička i fizička struktura:

Kod jednostruko spregnutih lista, pod logičkom strukturom se misli na to da znamo redosled elemenata, koji je prvi, drugi, treći, ... Pod fizičkom strukturom se misli na to kako je to smešteno u memoriji. Elementi koji su logički susedni (jedan iza drugog), u memoriji ne moraju da su susedni. NJihov fizički poredak nema nikakve logičke veze sa fizičkim poretkom.

   Slon s;
   ...
   if (s==null) 
      Console.WriteLine("Promenljiva nema vrednost");
   else      
      Console.WriteLine("Tezina = " + s.Tezina);

Promenljivu koja se nalazi na početku liste još nazivamo glava liste, poslednji element u listi često nazivamo i rep liste. Za svaki pojedinačni element liste još kažemo i da je čvor liste.

Dodavanje elemenata može da se vrši na početku liste, na kraju liste ili negde u sredini. Isto tako, može da se uklanja element na bilo kojoj poziciji u listi. Međutim, prolazak kroz listu mora da se vrši redom: naziv liste pokazuje gde se nalazi prvi element, prvi element pokazuje gde se nalazi drugi element, i tako redom, sve dok se ne dođe do poslednjeg elementa koji ne pokazuje na neki sledeći element već na tom mestu ima null.

Kako se radi sa listama u programskom jeziku C#

Programski jezik C# ima gotovu klasu koja se koristi za rad sa listama: klasa ArrayList koja je definisana u prostoru imena System.Collections (učitava se pomoću: using System.Collections). Elementi liste mogu biti objekti bilo kojeg tipa (klase).

U nastavku su navedene neke metode koje možemo koristiti za kreiranje lista i rad sa njima:

• Add - dodavanje objekta u listu
• Clear - uklanja sve objekte iz liste
• Contains - proverava da li je zadati objekat prisutan u listi
  
• IndexOf - Vraća indeks zadatog objekta
  
• Insert - Umeće zadati objekat na zadato mesto
• Remove - uklanja zadati objekat
• RemoveAt - uklanja objekat sa zadatim rednim brojem
• Reverse - redosled objekata okreće naopačke

Kao i svi drugi objekti, lista se kreira naredbom new. Nije potrebno da se veličina liste zadaje unapred, jer, kao što smo već rekli, lista se sama po sebi proširuje po potrebi. To znači da se tako zauzima optimalna količina memorije.

Primer:

   ArrayList mojaLista = new ArrayList();

   mojaLista.Add(new Slon(50));
   mojaLista.Add("ovo je neki string");

   Console.WriteLine(mojaLista.Count);

Ovde smo na kraj liste dodali dva različita objekta. U poslednjoj liniji se pomoću atributa Count može saznati koliki je ukupan broj elemenata u listi.

Kada želimo da pristupimo nekom elementu liste, to radimo kao kod nizova, pisanjem uglastih zagrada i indeksa elementa koji nam je potreban. Pošto se u listu može staviti bilo kakav objekat, potrebno je izvršiti konverziju tipa, kao na primer:

   Slon s = (Slon) mojaLista[0];
   string st = (string) mojaLista[1];

(Dobra praksa je da se u listi koristi samo jedan tip podataka, da se ne bi slučajno desila konverzija u pogrešan tip.)

Kada su u listi objekti istog tipa, za prolazak kroz celu listu se može koristiti naredba foreach.

Primer:

Ako pretpostavimo da lista ucenici u sebi sadrži 24 stringa, ako bismo da ispišemo sve elemente liste, to možemo da uradimo ovako:

   foreach(string s in ucenici)
    {
      Console.WriteLine(s);
    }

U ovom primeru, petlja će se izvršiti 24 puta. U svakom prolasku kroz petlju će se menjati vrednost promenljive s, od prvog do poslednjeg elementa.

U nastavku ćemo dati primer kako se koriste 2 metode klase ArrayList.

Metoda IndexOf vraća poziciju zadatog elementa, a u slučaju da taj element ne pripada listi vraća -1.

   ArrayList drugaLista = new ArrayList();
   Slon s1 = new Slon(90);
   Slon s2 = new Slon(80);
   drugaLista.Add(s2);
   Console.WriteLine( drugaLista.IndexOf(s1)); // ispisuje -1
   Console.WriteLine( drugaLista.IndexOf(s2)); // ispisuje 0 - pozicija prvi u listi

Metoda Contains vraća true ili false u zavisnosti od toga da li se zadati objekat nalazi u listi ili ne:

   Console.WriteLine( drugaLista.Contains(s1)); // ispisuje false   
   Console.WriteLine( drugaLista.Contains(s2)); // ispisuje true

Ako uklonimo neki objekat iz liste, to ne znači da smo ga uklonili i iz memorije, već samo da smo iz liste izbacili pokazivač na njega. Za uklanjanje elementa koji se nalazi na određenom mestu u listi koristi se metoda RemoveAt, a primer za to je drugaLista.RemoveAt(0);. Ako želimo da uklonimo sve elemente iz liste, koristićemo metodu Clear, kao npr: drugaLista.Clear();

Generičke liste

U ovom slučaju, u listu je moguće dodavati samo vrednosti odabranog tipa.

Primer:

   List<int> lista2 = new List<int>();
   lista2.Add(3);

Razlika između ArrayList i List je u sledećem: