Razlika između nizova i povezanih popisa

Nizi na povezanim popisima

Nizovi su najčešće korištena struktura podataka za pohranu zbirke elemenata. Većina programskih jezika pruža metode za lako deklariranje nizova i pristupanje elementima u polju. Povezani popis, točnije pojedinačno povezan popis, također je struktura podataka koja se može koristiti za spremanje zbirke elemenata. Sastoji se od niza čvorova i svaki čvor ima referencu na sljedeći čvor u nizu.

Prikazano na slici 1, dio je koda koji se obično koristi za deklariranje i dodjeljivanje vrijednosti polju. Slika 2 prikazuje kako bi niz izgledao u memoriji.

Gornji kôd definira niz koji može pohraniti 5 cjelobrojnih brojeva i njima se pristupa pomoću indeksa 0 do 4. Jedno važno svojstvo matrice je da je cijeli niz dodijeljen kao jedan blok memorije, a svaki element dobiva vlastiti prostor u polju. Jednom kada je niz definiran, fiksira se njegova veličina. Dakle, ako niste sigurni u veličinu matrice u vrijeme sastavljanja, morali biste definirati dovoljno veliki niz da biste bili na sigurnoj strani. Ali većinu vremena ćemo zapravo koristiti manji broj elemenata nego što smo ih izdvojili. Dakle, znatna količina memorije je zapravo izgubljena. S druge strane, ako "dovoljno veliki niz" zapravo nije dovoljno velik, program bi se srušio.

Povezani popis raspoređuje memoriju svojim elementima odvojeno u svoj vlastiti blok memorije, a cjelokupna struktura dobiva se povezivanjem tih elemenata kao karika u lancu. Svaki element na povezanom popisu ima dva polja kao što je prikazano na slici 3. Polje podataka sadrži stvarne pohranjene podatke, a sljedeće polje sadrži referencu na sljedeći element u lancu. Prvi element povezanog popisa sprema se kao glava povezanog popisa.

Slika 3: Element povezanog popisa

Slika 4 prikazuje povezan popis s tri elementa. Svaki element pohranjuje svoje podatke i sve elemente osim posljednjeg pohranjuje referencu na sljedeći element. Zadnji element sadrži null vrijednost u svom sljedećem polju. Bilo kojem elementu na popisu može se pristupiti počevši od glave i slijedeći sljedeći pokazivač dok ne ispunite traženi element.

Iako su nizovi i povezani popisi slični u smislu da se oba koriste za pohranjivanje zbirke elemenata, oni imaju razlike zbog strategija koje koriste za raspoređivanje memorije u njegove elemente. Nizi dodjeljuju memoriju svim njenim elementima kao jedan blok, a veličina matrice se mora odrediti tijekom izvođenja. Zbog toga će nizovi biti neučinkoviti u situacijama kada ne znate veličinu matrice u vrijeme sastavljanja. Budući da povezani popis zasebno raspoređuje memoriju u svoje elemente, bio bi mnogo učinkovit u situacijama u kojima ne znate veličinu popisa u vrijeme sastavljanja. Izjava i pristup elementima na povezanom popisu ne bi bio ravno naprijed u usporedbi s načinom na koji izravno pristupate elementima u nizu koristeći njegove indekse.