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

2.747 бајтова додато ,  пре 6 година
нема резимеа измене
[[Датотека: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.
 
===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ć
| first=Predrag
| last2=Marić
| first2=Filip
| title=Osnove programiranja kroz programski jezik C – Deo II
| pages=109-110
| url=http://www.matf.bg.ac.rs/~janicic/courses/p2.pdf
| year=2014}}</ref>
 
== Reference ==
7

измена