Povezana lista

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Primer povezane liste

Povezana lista je struktura podataka, koja je u osnovi predstavljena kao vektor parova (element, pokazivač), pri čemu pokazivač sadrži adresu narednog para. Tako postavljeni parovi nazivaju se čvorovima. Prolazak kroz listu moguć je jedino linearno - redom od početka, element po element, prateći pokazivače. Nedostaci ove strukture podataka su u tome što zahteva dodatni prostor u memoriji (uz svaki element ide i pokazivač), a k-tom (k>1) elementu se može pristupiti samo preko svih predhodnih. Prednost povezane liste je u tome što se upis i brisanje lako realizuju, potrebno je menjanje samo pokazivača (jednog u slučaju brisanja, dva u slučaju upisivanja). ^[1]

Zbog toga povezane liste se najčešće koriste za implementiranje drugih struktura podataka, kao što su stek i mape.

Koncept[уреди | уреди извор]

Svaki deo povezane liste se naziva element povezane liste ili čvor.

Polje u čvoru koje sadrži adresu sledećeg čvora se najčešće naziva sledeći pokazivač. Drugo polje je poznato kao podatak, vrednost ili informacija.

Glava je prvi čvor u povezanoj listi. Repom se može nazvati ili niz elemenata povezane liste (čvorova) koji ne sadrži glavu ili poslednji čvor u listi. Kraj liste se označava tako što poslednji čvor liste pokazuje na prazan čvor ili nil.

Vrste[уреди | уреди извор]

Jednostruko povezane liste[уреди | уреди извор]

Jednostruke povezane liste imaju čvorove koji sadrže samo vrednost i pokazivač na sledeći čvor.

Jednostruko povezana lista

Dvostruko povezane liste[уреди | уреди извор]

U dvostruko povezanim listama svaki čvor osim vrednosti i pokazivača na sledeći čvor sadrži još jedan pokazivač, na prethodni element.

Dvostruko povezana lista

Ciklične liste[уреди | уреди извор]

Kod cikličnih listi poslednji čvor ne pokazuje na nil, već na glavu liste.

Ciklična lista

Ako je lista dvostruko povezana osim što poslednji čvor pokazuje na glavu, i glava svojim pokazivačem na predhodi element pokazuje na poslednji čvor.

Prazna lista[уреди | уреди извор]

Prazna lista je lista bez podataka, za njih se kaže da su to liste bez čvorova.

Napredna povezana lista[уреди | уреди извор]

Kod naprednih povezanih listi svaki čvor ima više polja za vrednost.

Odnos niza, dinamičkog bloka i povezane liste[уреди | уреди извор]

Povezana lista se po više pitanja razlikuje od (statički alociranog) niza. Lista se može proizvoljno smanjivati i proširivati (tj. broj njenih elemenata se može smanjivati i povećavati). Dodavanje elementa u listu zahteva vreme O(1) (mada, zbog fragmentisanja memorije, konkretno vreme može da raste kako se program izvršava). Elementi niza su smešteni u uzastopnim memorijskim lokacijama i pozicija u memoriji i-tog elementa se može jednostavno izračunati na osnovu i i pozicije početnog elementa. Zbog toga se i-tom elementua niza pristupa u vremenu O(1). S druge strane, elementi liste su smešteni u memorijskim lokacijama koje nisu nužno uzastopne i mogu biti razbacane po memoriji. Da bi se pristupilo jednom elementu liste, potrebno je krenuti od početnog elementa i pratiti pokazivače sve dok se ne naiđe na traženi element, te je vreme potrebno za pristup O(n) (gde je n broj elemenata liste).

Povezana lista se po više pitanja razlikuje i od dinamički alociranih blokova memorije (koji mogu da sadrže nizove elemenata istog tipa). Alokacija dinamičkog bloka zahteva postojanje u memoriji povezanog bloka slobodne memorije (veličine dovoljne da primi zadati skup elemenata). S druge strane, korišćenje lista zahteva alociranje memorije samo za jedan po jedan element. Brisanje elemenata se takođe vrši pojedinačno (ta česta dodavanja i brisanja elemenata liste dovode do fragmentisanja memorije). Veličina dinamičkog bloka se može menjati samo od njegovog kraja (a i to može da bude zahtevna operacija). Veličina liste se menja jednostavno dodavanjem novih pojedinačnih elemenata. Elementima u dinamičkom bloku se pristupa, kao elementima niza, u vremenu O(1), a elementima liste u vremenu O(n).

Sve u svemu — nijedna od navedenih struktura podataka (povezane liste, nizovi, dinamički blokovi) nije uvek najbolji izbor i nema svojstva uvek bolja od druga dva. Najbolji izbor je vezan za specifičnosti konkretnog problema i najvažnije zahteve. ^[2]

Reference[уреди | уреди извор]

^ Živković, Miodrag (2000). Algoritmi (PDF). ISBN 978-86-7589-020-1.
^ Janičić, Predrag; Marić, Filip (2014). Osnove programiranja kroz programski jezik C – Deo II (PDF). стр. 109—110. ^{[мртва веза]}

Литература[уреди | уреди извор]

Živković, Miodrag (2000). Algoritmi (PDF). ISBN 978-86-7589-020-1.

[1] Živković, Miodrag (2000). Algoritmi (PDF). ISBN 978-86-7589-020-1.

[2] Janičić, Predrag; Marić, Filip (2014). Osnove programiranja kroz programski jezik C – Deo II (PDF). стр. 109—110. ^{[мртва веза]}

[1]

[2]