Povezana lista — разлика између измена
м Робот: додато {{Commonscat|Linked lists}} |
м ciscenje mrtvih referenci |
||
| Ред 52: | Ред 52: | ||
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. |
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. |
||
<ref> |
<ref> |
||
{{Cite book |
* {{Cite book |
||
| last=Janičić |
| last=Janičić |
||
| first=Predrag |
| first=Predrag |
||
Верзија на датум 26. април 2019. у 07:02
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
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.
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.
