Izvorni kôd stranice Lista (struktura podataka)

{{Sporna_autorska_prava}}
'''Prepisano sa stranice www.crnarupa.singidunum.ac.rs/valjevo'''
[[Datoteka:Singly-linked-list.svg|mini|285x285px|Jednostruko povezana lista]]U računarstvu, lista ili sekvenca je apstraktni tip podataka, koji predstavlja poredani niz vrijednosti, gdje se neka vrijednost može pojaviti više puta. Instanca liste je prikaz matematičkog koncepta za konačne liste.

Lista je osnovni tip '''kontejnera''', jer sadrže druge vrijednosti. Ako se ista vrijednost pojavljuje više puta, svako

pojavljivanje se smatra kao posebna stavka.

== Definicija ==
Lista je [[struktura podataka]] koja se odlikuje rasporedom pripadajućih elemenata. Po svojoj prirodi lista je najsrodnija [[Niz (čvor)|nizu]], ali se uglavnom implementira koristeći dinamičko alociranje memorije i pokazivače.<ref>{{Cite book|title = Algoritmi i strukture podataka|last = Tomašević|first = Milo|publisher = Akademska misao|year = 2008|isbn = 978-86-7466-328-8|location = Beograd|pages = 405-406}}</ref>

Lista se obično predstavlja kao vektor parova (element pokazivač), gdje pokazivač sadrži adresu narednog elementa. Ovako postavljeni parovi se nazivaju '''čvorovi'''. Prvi čvor se obično naziva '''glavom''' liste, a posljednji čvor '''repom''' liste.

Kod liste, prostor za neki čvor se alocira kada je to stvarno potrebno, tj. prilikom umetanja tog čvora u listu. S druge strane, prilikom brisanja nekog elementa iz liste, potrebno je izvršiti dealokaciju tog prostora, odnosno oslobađanje memorije.

== Osobine listi ==
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;
* 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, unaprijed određenog tipa.

== Vrste listi ==
Po vrsti povezanosti, liste se najčešće dijele na jednostruko povezane i dvostruko povezane. Po svom obliku, liste dijelimo na linearne i kružne.

=== Jednostruko povezane liste ===
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 jednog pokazivača za element što, u slučajevima s velikim brojem elemenata, može biti značajno.

=== Dvostruko povezane liste ===
Dvostruko povezane liste su liste u kojima je moguće preraživanje pripadajućih elemenata u da 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 pogodna za rad, i u većini slučajeva olakšava rješavanje u odnosu na jednostruko povezane liste.

=== Kružne liste ===
Kružne liste se odlikuju odsustvo početka liste.Naime, za razliku od običnih listi koje imaju jasno izražen početni i krajnji element, čiji pokazivač je jednak nuli, kod kružne liste, posljednji element se uvijek postavlja da pokazuje na prvi, a prvi element može da šeta, tj. u svakom trenutku bilo koji element liste može da se proglasi za prvi bez ometanja 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 [[Algoritam|algoritme]] jednostavnijim.

== Operacije u listi ==
Tipične operacije sa listom su umetanje, brisanje i pretraživanje liste. Tu imamo i ostale operacije, kao što su inverzija poretka čvorova u listi, povezivanje dvije liste u jednu, nalaženje ''i''-tog čvora itd.

Operacije sa listom najvećim dijelom manipulišu sa pokazivačima, gdje se na samom početku trebaju definisati legalne manipulacije sa pokazivačima, uzimajući u obzir da su to memorijske adrese. Sa pokazivačima su dozvoljene sljedeće aktivnosti:
* testiranje pokazivača na null;
* provjera jednakosti dva pokazivača;
* postavljanja pokazivača na null:
* dodjela vrijednosti drugog pokazivača ili adrese datom pokazivaču.

=== Umetanje u listu ===
Umetanje elemenata u listu može biti izvršeno na bilo kojem mjestu u listi (početak, sredina, kraj).

Operacija '''''UMETNI_IZA (p, x)''''' , u listu umeće novi čvor sa sadržajem ''x'' iza čvora čija je adresa ''p''.<syntaxhighlight lang="text">
UMETNI_IZA(p,x)
q = NOVI_CVOR //NOVI_CVOR- funkcija za formiranje novog cvora
info(q) = x //info-informacioni sadržaj elementa
sljedeci(q) = sljedeci(p) //pokazivač na sljedbenika
sljedeci(p) = q

</syntaxhighlight>Operacija umetanja se vrši tako da nakon što se dinamički alocira prostor za novi čvor u njega se upiše sadržaj novog čvora. Zatim se vrši preusmjeravanje pokazivača, tako da sljedbenih prethodnog čvora postaje sljedbenik novog čvora, a sam novi čvor postaje sljedbenik prethodnog čvora.
[[Datoteka:Lista 1.JPG|centar|mini|476x476px|Umetanje čvora sa sadržajem x iza čvora na koji pokazuje p]]Umetanje novog čvora u listu ima uticaja samo na dva čvora, na novi čvor i njegovog prethodnika.

Ukoliko je lista neuređena to omogućava brže umetanje, jer se novi čvor može umetnuti na početak liste. S druge strane, ako imamo uređenu listu, tada je umetanje složenije, jer moramo ispitati gotovo polovinu čvorova da bi odredili poziciju na koju ćemo umetnuti odgovarajući element.

=== Brisanje iz liste ===
Operacija brisanja elementa iz liste može da ukloni čvor sa bilo kojeg mjesta u listi.

U slučaju kada brišemo čvor u sredini ili na kraju liste, treba da se izvrši preusmjeravanje pokazivača, tako da prethodnik čvora kojeg brišemo pokazuje na njegovog sljedbenika.
[[Datoteka:Lista 2.JPG|centar|mini|373x373px|Brisanje čvora iza čvora na koji pokazuje pokazivač p]]

U operaciji '''''IZBRISI_IZA(p)''''' potrebno je dati pokazivač ''p'' koji pokazuje na prethodnika čvora kojeg brišemo, i na osnovu toga znamo koji čvor trebamo obrisati.<syntaxhighlight lang="text">
IZBRISI_IZA(p)
q = sljedeci(p)
sljedeci(p) = sljedeci(q) 
DELETE(q)//operacija DELETE- oslobada cvor sa datom adresom

</syntaxhighlight>

=== Pretraživanje liste ===
Operacija pretraživanja liste nam je potrebna ukoliko želimo locirati određeni čvor u listi, radi pristupa elementu tog čvora.

Operacija '''''PRETRAZI(lista, x)''''' pretražuje datu listu ''k'', i ukoliko postoji bar jedan čvor sa sadržajem x, vraća adresu tog čvora, u suprotnom vraća nulu.<syntaxhighlight lang="text">
PRETRAZI(lista, x) 
p = lista
while (p != null) and (info(p) != x) do
	p = sljedeci(p) 
end_while
return p

</syntaxhighlight>Kod neuređene liste, da bi smo obavili pretraživanje, koje je u ovom slučaju neuspješno, moramo proći čitavu listu, dok se kod uređene liste, za pretraživanje može reći da je neuspješno čim dođemo do prvog čvora sa većim sadržajem, a do tada nismo pronašli odgovarajući čvor.

=== Ostale operacije ===
Operacija '''''INVERZNA_LISTA(lista )''''' vrši inverz čvorova u listi, na čiji prvi čvor pokazuje pokazivač ''lista'', tako da prvi čvor postaje posljednji, drugi postaje pretposljednji itd. U ovoj operaciji imamo tri pokazivača, tako da ''p'' pokazuje na sljedbenika čvora na koji pokazuje ''q'', a ''r'' pokazuje na prethodnika od ''q.'' <syntaxhighlight lang="text">
INVERZNA_LISTA (lista)
p = lista;
q = null;
while (p != null) do
    r = q;
    q = p;
    p = sljedeci(p);
    sljedeci(q) = r;
end_while
lista = q;
</syntaxhighlight>
[[Datoteka:Inverzna lista.JPG|centar|mini|306x306px|Operacija '''''INVERZNA_LISTA''''': a) prije početka opracije, b) poslije prve, c)poslije druge, d)poslije treće iteracije]]

== Predstavljanje polinoma ==
Neka je <math>P(x)=\sum_{i=1}^Na_ix^i</math> polinom stepena '''''N'''''. ako je većina koeficijenata <math>a_i</math> različita od nule, možemo koristiti niz veličine '''''N''''' za predstavljanje polinoma, tako što ćemo u ćeliju sa indeksom ''i'' smjestiti koeficijent koji stoji uz <math>x^i</math> u polinomu <math>P(x)</math>. Za tako predstavljene polinome moguće je implementirati operacije kao što su sabiranje, oduzimanje, množenje, dijeljenje, itd... Međutim ako razmotrimo polinome <math>P_1(x)=10x^{1000}+5x^{14}+1</math> i <math>P_2(x)=3x^{1990}-2x^{1492}+11x+5</math> vidimo da će gotovo sav prostor u nizu od <math>1000</math> odnosno <math>1940</math> elemenata biti neiskorišten. Najveći dio vremena pri implementaciji gore navedenih operacija bi se sveo na množenje ili oduzimanje nula. Alternativa je u korištenju povezanih listi. Kako se kroz polinom obično prolazi u jednom smjeru, dovoljno je koristiti samo jednostruko povezanu kružnu listu. Listu je dobro držati uređenom po opadajućoj vrijednosti polja za eksponent. Tako bi implementacija navedena dva polinoma imala oblik:[[Datoteka:Polinom lista.JPG|centar|bez_okvira|503x503px]]
Koristeći ovakvu implementaciju polinoma pomoću listi, mnogo je lakše implementirati operacije sabiranja, množenja, itd, kao i algoritam za poređenje dva polinoma, i mnoge druge operacije koje su moguće sa polinomima.

== Reference ==

{{DEFAULTSORT:Lista}}
[[Kategorija:Strukture podataka]]
[[Kategorija:Računarstvo]]
[[Kategorija:Informatika]]