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]