Povezana lista — разлика између измена

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 6. април 2014. у 04:15

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.

TU BI KONTINJUD

Reference

^ Živković, Miodrag (2000). Algoritmi (PDF). стр. 33. ISBN 86-7589-020-6.

[1] Živković, Miodrag (2000). Algoritmi (PDF). стр. 33. ISBN 86-7589-020-6.

[1]

@@ Ред 12: / Ред 12: @@
 | page=33
 | url=http://poincare.matf.bg.ac.rs/~ezivkovm/nastava/algoritmi.pdf
-| year=2000.
+| year=2000.|id=ISBN 86-7589-020-6}}</ref>
-| isbn=86-7589-020-6}}</ref>
 <br />
 Zbog toga povezane liste se najčešće koriste za implementiranje drugih struktura podataka, kao što su [[Стек|stek]] i [[Асоцијативни низ|mape]].
-==Koncept==
+== Koncept ==
 Svaki deo povezane liste se naziva element povezane liste ili čvor.
@@ Ред 24: / Ред 23: @@
 '''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==
+== Vrste ==
-===Jednostruko povezane liste===
+=== Jednostruko povezane liste ===
 '''Jednostruke povezane liste''' imaju čvorove koji sadrže samo vrednost i pokazivač na sledeći čvor.
 [[Датотека:Singly-linked-list.svg|центар|Jednostruko povezana lista]]
-===Dvostruko povezane liste===
+=== 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.
 [[Датотека:Doubly-linked-list.svg|центар|Dvostruko povezana lista]]
-===Ciklične liste===
+=== Ciklične liste ===
 Kod '''cikličnih listi''' poslednji čvor ne pokazuje na nil, već na glavu liste.
 [[Датотека:Circularly-linked-list.svg|центар|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.
-==TU BI KONTINJUD==
+== TU BI KONTINJUD ==
-==Reference==
+== Reference ==
 {{reflist}}