Strukture podataka i algoritmi
3.2 Liste

Implementacija naseg skupa pomocu nizova ima jedan ozbiljan nedostatak: morate znati maksimalan broj elemenata skupa kada ga kreirate. Ovo pravi probleme u programima kod kojih se ovaj broj ne moze sa sigurnoscu predvideti kada se program pokrene. Na srecu, mozemo koristiti strukturu poznatu kao povezana lista da bismo prevazisli ovo ogranicenje.

3.2.1 Povezane liste

Povezana lista je veoma fleksibilna dinamicka struktura podataka: objekti se mogu dodavati ili brisati iz nje po zelji. Programer ne mora da brine o tome koliko objekata program treba da smesti: ovo nam dozvoljava da pravimo robustne programe kojima je potrebno mnogo manje odrzavanja. Veoma cest uzrok problema u odrzavanju programa je potreba za povecanjem kapaciteta programa kako bi mogao da obradi vece skupove: cak i najvelikodusnija predvidjanja prosirenja postaju neodgovarajuca tokom vremena!

U povezanoj listi, svakom objektu se alocira mesto u memoriji dok se dodaje u listu i pritom se odrzava veza od svakog objekta do sledeceg objekta u listi.

Svaki cvor liste ima dva elementa
  1. objekat koji se stavlja u listu i
  2. pointer na sledeci objekat u listi
Poslednji cvor liste sadrzi NULL pointer kako bi ukazao da smo stigli do kraja, odnosno repa liste.

Dok se objekti dodaju u listu, memorija za cvor se dinamicki alocira. Stoga je broj objekata koji se mogu dodati u listi ogranicen samo kolicinom raspolozive memorije.

Promenljiva za listu

Promenljiva koja predstavlja listu je jednostavno pointer na prvi cvor, odnosno na glavu liste.

Dodavanje u listu

Najjednostavnija strategija za dodavanje objekta u listu je:
  1. alociraj memoriju za novi cvor,
  2. prekopiraj objekat u novi cvor,
  3. postavi da next pointer novog cvora pokazuje na trenutnu glavu liste i
  4. postavi da glava liste pokazuje na novi cvor.
Ova strategija je brza i efikasna, ali se svaki objekat dodaje na glavu liste.

Alternativno resenje je kreiranje strukture za listu koje sadrzi pointere i na glavu i na rep: 

	struct fifo_list {
		struct node *head;
		struct node *tail;
		};

Sada bi se kod za AddToCollection metod lako promenio tako da objekat koji se dodaje u listu ide na njen rep, umesto na glavu.

Specifikacija ostaje identicna onoj za implementaciju pomocu niza: parametar max_item u konstruktoru ConsCollection se jednostavno ignorise [7]

Prema tome, jedino treba da promenimo implementaciju. Kao posledica, programe koji koriste ovaj objekat ne moramo menjati. Posledice po cenu odrzavanja softvera su znacajne.

Struktura podataka je promenjena, ali posto su detalji (atributi objekta ili elementi strukture) skriveni od korisnika, nema uticaja po program korisnika.

Ucitaj collection_ll.c

Primetimo:

  1. Ovakva implementacija naseg skupa moze da se postavi umesto prethodne bez ikakvih promena u programu korisnika. Sa izuzetkom dodate fleksibilnosti da se u nas skup moze dodati proizvoljno mnogo objekata, ova implementacija pruza daje isto ponasanje strukture kao i prethodna.
  2. Implementacija pomocu povezane liste menja fleksibilnost za efikasnost - na vecini sistema, sistemski poziv za alociranje memorije je relativno skup. Pre-alokacija memorije u implementaciji pomocu niza je, u opstem slucaju, efikasnija. Dalje primere ovakvih nezeljenih kompromisa cemo videti kasnije.

Proucavanje struktura podataka i algoritmi ce vam omoguciti da napravite odluku o implementaciji koja najbolje odgovara specifikacijama vaseg korisnika.

3.2.2 Varijante listi

Kruzno povezane liste

Postavljajuci da rep liste uvek pokazuje na glavu, mozemo da napravimo kruzno povezanu listu. Ako spoljni pointer (onaj iz struct t_node u nasoj implementaciji), pokazuje na trenutni "rep" liste, tada se "glava" liste trivijalno nalazi pomocu tail->next, dozvoljavajuci nam da imamo bilo LIFO (Last-In-First-Out = Ko poslednji udje, prvi izadje) ili FIFO (First-In-First-Out = Ko prvi udje, prvi i izadje) liste sa samo jednim spoljnim pointerom. Kod modernih procesora, nekoliko bajtova memorije ustedjenih na ovaj nacin se verovatno ne bi smatrali znacajnim. Kruzno povezana lista bi se najverovatnije koristila u primenama koje zahtevaju planiranje ili obradu podataka, za koje je bitno da svi imaju isti nivo prioriteta.

Dvostruko povezane liste

Dvostruko povezane liste, pored pointera na sledeci objekat, imaju pointer i na prethodni objekat u listi.
One omogucavaju obilazak liste u oba pravca. (Da bi se vratilo na prethodni objekat u obicnoj listi, obilazak se mora poceti ponovo od glave liste.) Mnoge primene zahtevaju pretrazivanje nazad i napred kroz odredjenu sekciju liste: na primer, pretraga za uobicajenim prezimenom kao "Petrovic" u nasem telefonskom imeniku bi verovatno zahtevala mnogo pokusaja nazad i napred kroz mali deo celog imenika, pa stoga pointeri na prethodni objekat postaju korisni. U ovom slucaju, struktura cvora se menja, tako da on sada ima dva pointera: 
struct t_node {
     void *item;
     struct t_node *previous;
     struct t_node *next;
     } node;

Liste pomocu nizova

Iako ovo moze delovati besmisleno (zasto primenjivati strukturu koja ima dodatni "next" pointer na niz?), upravo to radi operativni sistem kako bi upravljao slobodnom memorijom.

Memorija je samo niz reci. Posle serije alokacija i de-alokacija memorije, blokovi slobodne memorije se nalaze razbacani po raspolozivom prostoru. Kako bi bio u mogucnosti da ponovo iskoristi ovu memoriju, operativni sistem bi obicno povezao oslobodjene blokove zajedno u slobodnoj listi zapisujuci pointere na sledeci slobodan blok unutar samog bloka. Dodatni spoljasnji pointer na slobodnu listu pokazuje na prvi blok slobodne liste. Kada dodje do novog zahteva za memorijom, operativni sistem ce jednostavno proci kroz slobodnu listu tragajuci za slobodnim blokom memorije odgovarajuce velicine, a zatim ce ga obrisati iz slobodne liste (prepovezujuci slobodnu listu tako da zaobilazi upravo zauzeti blok). Predlozene su mnoge varijacije ove seme odrzavanja slobodne memorije: za vise detalja jednostavno uzmite bilo koju knjigu o operativnim sistema ili o implementaciji funkcionalnih jezika. Stavka garbage collection (skupljanje djubreta) u indeksu verovatno sadrzi duzu diskusiju o ovoj temi.

Kljucni pojmovi

Dinamicke strukture podataka
Strukture koje rastu ili se smanjuju u skladu sa menjanjem podataka koje sadrze. Liste, stekovi i stabla su primeri dinamickih struktura.

Dalje na Stekove
Nazad na Sadrzaj
© John Morris, 1998. Prevod sa engleskog, Dragan Stevanovic, 2002.