Luka
03-07-2008, 23:22
U programiranju se često susrečemo s potrebom da pohranimo podatke u polje nedefinirane duljine. U C++u duljina polja mora biti poznata prije prevođenja programa što znači da kasnije, ukoliko želimo dodati neki novi element, moramo prvo izbaciti stari. Djelomično rješenje problema ju u dinamičkoj alokaciji memorije - u tom slučaju se umjesto na stog (eng. stack) podaci pohranjuju na hrpu (eng. heap), poseban dio memorije. Na taj je način moguće alcirati prostor za polje tijekom izvođenja programa, što omogućava veću fleksibilnost programa. No, čak i tada javlja se problem - što ako popunimo polje podacima i želimo dodati još jedan element čije postojanje nismo unaprijed predvidjeli? Najjednostavnije rješenje je ponovno koristiti dinamičku alokaciju memorije i alocirati polje za jedan element veće od prethodnog, te nakon toga kopirati sve elemente starog polja u novo polje. Ovakav pristup će biti vrlo spor ako imamo mnogo elemenata, a što je više elemenata u polju dodavanje novog elementa će postajati sporije. To je ujedno i najveći nedostatak ovakvog pristupa - sporost pri dodavanju. Ukoliko poželimo sve zakomplicirati brisanjem elemenata, sporost će se javljati i prilikom brisanja. Uz sve to, ukoliko je polje stvarno veliko a trenutna memorija fragmentirana postoji mogućnost da se polje neće moći alocirati i samim time nestaje mogućnost proširenja. Jedno od rješenja su dvostruko vezane liste (ili doubly linked list). Cilj ovog teksta je upoznati Vas s načinom rada ove strukture podataka i kako se služiti ovakvim listama u praksi. Bilo bi dobro znati da postoje i jednostavnije "jednostruko vezane liste", i njihova varijacija "kružno vezane liste".
Osnova svake vezane liste je član (eng. node). Član je ustvari struktura koja se sastoji od 3 elementa. Pokazivač na prethodni član, pokazivač na sljedeći član i sam element (vrijednost bilo kojeg tipa). Članovi se povezuju maloprije spomenutim pokazivačima. Vezana lista se može ovako predstaviti:
http://img117.imageshack.us/img117/7704/610pxdoublylinkedlistsvqr6.png
[slika preuzeta sa Wikimedia Commons - originalna scalable vector graphics slika (http://en.wikipedia.org/wiki/Image:Doubly-linked-list.svg)]
Primjetite kako se na krajevima nalaze nul-pokazivači (premda oni nisu nužni za funkcioniranje liste). Po listi se moguće "kretati" upravo pokazivačima na objekte koji su neposredno ispred i iza trenutnog objekta.
Ovakav pristup ima mnogo prednosti:
- memorija smije biti fragmentirana jer to neće utjecati na listu - članovi se mogu nalaziti bilo gdje u memoriji.
- izbacivanje elemenata je puno lakše - jednostavno treba preusmjeriti objekte neposredno iza i ispred onog kojeg želimo obrisati, a kako njega više ništa ne veže, on ispada iz liste.
- dodavanje elementa je brže - nema potrebe za povećavanjem max broja elemenata jer vezana lista radi na potpuno drugačijem principu od standardnog arraya.
Kao i sve ostalo, i vezana lista ima nedostataka - a on je posljedica načina rada liste. Naime, kod standardnog arraya, do objekta se dolazi tako što se adresi početnog objekta pridoda umnožak indeksa željenog elementa i količina memorije koju zauzima struktura (npr. 1 byte). To je tako jer array sprema elemente jedan iza drugoga u memoriju, bez prostora između. No, kod vezanih lista je nemoguće doći do nekog objekta na taj način jer se određeni član sprema na slučajnu adresu koja nemora nužno biti veća od prethodne. Zbog toga, jedini način putovanja je da se ide od jednog do drugog elementa sve dok ne dođemo do željenog. A takav pristup je vrlo spor kad se u polju nađe mnogo elemenata. Ovaj problem je moguće umanjiti raznim metodama, npr. mogli bismo se, umjesto od prvog elementa prema zadanom indeksu, kretati od posljednjeg prema zadanom ukoliko je taj elemnt bliže kraju liste nego početku.
Za kraj, ovdje se nalazi primjer linked liste koju sam napisao u C++u: http://docs.google.com/Doc?id=dgxfs98_216pt727f5.
Osnova svake vezane liste je član (eng. node). Član je ustvari struktura koja se sastoji od 3 elementa. Pokazivač na prethodni član, pokazivač na sljedeći član i sam element (vrijednost bilo kojeg tipa). Članovi se povezuju maloprije spomenutim pokazivačima. Vezana lista se može ovako predstaviti:
http://img117.imageshack.us/img117/7704/610pxdoublylinkedlistsvqr6.png
[slika preuzeta sa Wikimedia Commons - originalna scalable vector graphics slika (http://en.wikipedia.org/wiki/Image:Doubly-linked-list.svg)]
Primjetite kako se na krajevima nalaze nul-pokazivači (premda oni nisu nužni za funkcioniranje liste). Po listi se moguće "kretati" upravo pokazivačima na objekte koji su neposredno ispred i iza trenutnog objekta.
Ovakav pristup ima mnogo prednosti:
- memorija smije biti fragmentirana jer to neće utjecati na listu - članovi se mogu nalaziti bilo gdje u memoriji.
- izbacivanje elemenata je puno lakše - jednostavno treba preusmjeriti objekte neposredno iza i ispred onog kojeg želimo obrisati, a kako njega više ništa ne veže, on ispada iz liste.
- dodavanje elementa je brže - nema potrebe za povećavanjem max broja elemenata jer vezana lista radi na potpuno drugačijem principu od standardnog arraya.
Kao i sve ostalo, i vezana lista ima nedostataka - a on je posljedica načina rada liste. Naime, kod standardnog arraya, do objekta se dolazi tako što se adresi početnog objekta pridoda umnožak indeksa željenog elementa i količina memorije koju zauzima struktura (npr. 1 byte). To je tako jer array sprema elemente jedan iza drugoga u memoriju, bez prostora između. No, kod vezanih lista je nemoguće doći do nekog objekta na taj način jer se određeni član sprema na slučajnu adresu koja nemora nužno biti veća od prethodne. Zbog toga, jedini način putovanja je da se ide od jednog do drugog elementa sve dok ne dođemo do željenog. A takav pristup je vrlo spor kad se u polju nađe mnogo elemenata. Ovaj problem je moguće umanjiti raznim metodama, npr. mogli bismo se, umjesto od prvog elementa prema zadanom indeksu, kretati od posljednjeg prema zadanom ukoliko je taj elemnt bliže kraju liste nego početku.
Za kraj, ovdje se nalazi primjer linked liste koju sam napisao u C++u: http://docs.google.com/Doc?id=dgxfs98_216pt727f5.