Lista (informatika)
Lista je struktura podataka koja se odlikuje linearnim rasporedom pripadajućih elemenata. Po svojoj prirodi, lista je najsrodnija nizu, ali se uglavnom implementira koristeći dinamičko alociranje memorije i pokazivače.
Osobine[uredi | uredi kod]
Svaka lista mora da zadovoljava sljedeće osobine:
- Lista može biti prazna
- Moguće je ubaciti novi element na bilo koju poziciju u listi
- Moguće je izbaciti bilo koji element iz liste
- Lista ima svoju veličinu, tj. broj elemenata
- Svakom elementu liste se može pristupiti preko rednog broja, tj. indeksa
Lista se može sastojati od elemenata različitih tipova, a može biti tipizirana, tj. imati ograničenje da svi pripadajući elementi moraju biti istog, određenog unaprijed, tipa.
Vrste[uredi | uredi kod]
Po vrsti povezanosti, liste se najčešće dijele na jednostruko povezane i dvostruko povezane. Po svom obliku, dijele se na linearne i kružne liste.
Dvostruko povezane liste su liste po kojima je moguće pretraživanje pripadajućih elemenata u dva smjera. Ovo se u programiranju najčešće implementira postojanjem dva pokazivača u svakom elementu liste, od kojih jedan pokazuje na prethodni, a drugi na sljedeći element u listi. Ova vrsta liste je jako udobna za rad, i u većini slučajeva olakšava rješenje u odnosu na jednostruko povezanu listu.
Jednostruko povezane liste podržavaju pretraživanje elemenata samo u jednom smjeru. Kod implementacija liste pomoću pokazivača i dinamičke memorije, svaki element sadrži po tačno jedan pokazivač koji pokazuje na sljedeći element u listi. Najčešće se koriste u situacijama kada je jednosmjerno pretraživanje dovoljno za dati problem. Iako ograničene jednim smjerom, one imaju uštedu od po jednog pokazivača po elementu što, u slučajevima sa velikim brojem elemenata, može biti značajno.
Kružne liste se odlikuju odsustvom početka liste. Naime, za razliku od običnih listi koje imaju jasno izražen početni element i krajnji element, čiji pokazivač je jednak nuli, poslednje ubačeni element liste se uvijek postavlja da pokazuje na prvi, a prvi element može da šeta, tj. u svakom trenutku bilo koji element može da se proglasi za prvi bez remećenja strukture. Na ovaj način se postiže da se iteracija po listi ne mora nikada završiti, jednostavno prelazeći svaki put na sljedeći element, što čini određene algoritme jednostavnijim.
