Povezana lista — разлика између измена
Садржај обрисан Садржај додат
Спашавам 0 извора и означавам 1 мртвим. #IABot (v2.0beta14) |
м Разне исправке |
||
Ред 11:
| title=Algoritmi
|pages=33
| url=http://poincare.matf.bg.ac.rs/~ezivkovm/nastava/algoritmi.pdf|year=2000|isbn=978-86-7589-020-1|pages=}}</ref>
Zbog toga povezane liste se najčešće koriste za implementiranje drugih struktura podataka, kao što su [[Стек (апстрактни тип података)|stek]] i [[Асоцијативни низ|mape]].
Линија 49 ⟶ 47:
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)''.
Линија 61 ⟶ 58:
| first2=Filip
| title=Osnove programiranja kroz programski jezik C – Deo II
|
| url=http://www.matf.bg.ac.rs/~janicic/courses/p2.pdf
|
}}{{Мртва веза|date=04. 2019. |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
== Reference ==
Линија 76 ⟶ 72:
| title=Algoritmi
|pages=33
| url=http://poincare.matf.bg.ac.rs/~ezivkovm/nastava/algoritmi.pdf|year=2000|isbn=978-86-7589-020-1|pages=}}
{{DEFAULTSORT:Повезана листа}}
| |||