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

Povezana lista (уреди)

Верзија на дан 9. април 2014. у 05:57 ч.

4 бајта додата ,  пре 6 година
м
референце; козметичке измене
м (референце; козметичке измене)
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 ===
{{Main|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.
<ref>{{Cite book
| last=Janičić
| last2=Marić
| first2=Filip
| title=Osnove programiranja kroz programski jezik C – Deo II|pages=109-110
| pages=109-110
| url=http://www.matf.bg.ac.rs/~janicic/courses/p2.pdf
| year=2014}}</ref>
Autobot
Ботови
1.572.075

измена

Преузето из „https://sr.wikipedia.org/wiki/Посебно:МобилнеРазлике/9722622”