Lista (struktura podataka)

Prepisano sa stranice www.crnarupa.singidunum.ac.rs/valjevo

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 nizu, ali se uglavnom implementira koristeći dinamičko alociranje memorije i pokazivače.

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 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.

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

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.

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.

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.

IZBRISI_IZA(p)
q = sljedeci(p)
sljedeci(p) = sljedeci(q) 
DELETE(q)//operacija DELETE- oslobada cvor sa datom adresom

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.

PRETRAZI(lista, x) 
p = lista
while (p != null) and (info(p) != x) do
	p = sljedeci(p) 
end_while
return p

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.

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;

Operacija INVERZNA_LISTA: a) prije početka opracije, b) poslije prve, c)poslije druge, d)poslije treće iteracije

Predstavljanje polinoma

Neka je $P(x)=\sum _{i=1}^{N}a_{i}x^{i}$ polinom stepena N. ako je većina koeficijenata $a_{i}$ 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 $x^{i}$ u polinomu $P(x)$. Za tako predstavljene polinome moguće je implementirati operacije kao što su sabiranje, oduzimanje, množenje, dijeljenje, itd... Međutim ako razmotrimo polinome $P_{1}(x)=10x^{1000}+5x^{14}+1$ i $P_{2}(x)=3x^{1990}-2x^{1492}+11x+5$ vidimo da će gotovo sav prostor u nizu od $1000$ odnosno $1940$ 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:

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.