Povezana lista — разлика између измена
Нова страница: {{МАТФ032014}} мини|Primer povezane liste '''Povezana lista''' je Структура података|struktura p… |
(нема разлике)
|
Верзија на датум 5. април 2014. у 20:11
Овај чланак је део пројекта семинарских радова на Математичком факултету у Београду. Датум уноса: март—мај 2014. Ова група студената уређиваће у простору чланака. Немојте пребацивати чланак у друге именске просторе. Позивамо вас да допринесете његовом квалитету и помогнете студентима при уређивању. |
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.
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.
Ciklične liste
Kod cikličnih listi poslednji čvor ne pokazuje na nil, već na glavu liste.
Ako je lista dvostruko povezana osim što poslednji čvor pokazuje na glavu, i glava svojim pokazivačem na predhodi element pokazuje na poslednji čvor.
TU BI KONTINJUD
Reference
- ^ Živković, Miodrag (2000). Algoritmi (PDF). стр. 33. ISBN 86-7589-020-6.