Dobrodošli u našu lekciju o nizovima i povezanim listama. U ovoj lekciji naučit ćemo dva jednostavna načina pohranjivanja i organiziranja podataka. Zamislite da imate red kutija za igračke ili red ormarića u školi. Nizovi i povezani popisi rade na sličan način. Pomažu nam da stvari budu uredne i lako ih je pronaći. Ova je lekcija napisana jednostavnim jezikom sa svakodnevnim primjerima kako biste lakše razumjeli ove ideje.
Strukture podataka pomažu računalima pohraniti i organizirati informacije. Dvije važne strukture podataka su nizovi i povezani popisi. Niz možete zamisliti kao niz kutija, a povezani popis kao lanac povezanih tragova u potrazi za blagom. Oboje nam pomaže da pratimo mnoge stavke, poput igračaka, knjiga ili čak vaših omiljenih grickalica.
Razgovarat ćemo o tome što je niz, što je povezana lista, kako funkcioniraju i po čemu se razlikuju. Također ćemo vidjeti primjere iz stvarnog svijeta koji te ideje čine što jasnijim.
Niz je samo skup stavki. To je poput niza kutija gdje svaka kutija sadrži jedan predmet. Na primjer, zamislite skup od pet kutija poredanih u nizu. Svaku kutiju možete koristiti za spremanje omiljene igračke ili grickalice.
Svaki okvir u nizu ima broj koji se naziva indeks. Prvi okvir obično ima broj 0, sljedeći je 1, zatim 2, i tako dalje. Ovo numeriranje vam pomaže da brzo pronađete određenu stavku. Na primjer, ako želite stavku u trećem okviru, jednostavno pogledajte okvir s indeksom 2.
Evo jednostavne formule koja objašnjava kako možemo pronaći stavku u nizu. Ako je prvi okvir na početnoj točki, tada se adresa bilo koje stavke može zamisliti kao:
\( \textrm{Adresa}(A(i)) = \textrm{Adresa}(A(0)) + i \times \textrm{(veličina jednog predmeta)} \)
To nam govori da za pomicanje od prvog okvira do okvira koji želimo, brojite određeni broj mjesta unaprijed.
Zamislite niz poput sjedala u malom kinu. Svako sjedalo ima broj, a možete brzo doći do svog sjedala ako znate njegov broj.
Zamislite da vaša škola ima niz ormarića, svaki s jedinstvenim brojem. Kada idete staviti torbu u svoj ormarić, koristite određeni broj na ormariću. U nizu, svaki ormarić je poput kutije, a broj vam govori točno mjesto gdje se vaša torba—ili podaci—čuvaju.
Povezani popis još je jedan način pohranjivanja stavki. Razlikuje se od niza jer ne koristi dugi niz fiksnih okvira. Umjesto toga, koristi posebne okvire koji se nazivaju čvorovi. Svaki čvor sadrži stavku i također ima pokazivač koji vam govori gdje je sljedeći čvor.
Zamislite da ste u potrazi za blagom. Svaki trag koji pronađete govori vam gdje je skriven sljedeći trag. U povezanom popisu, svaki čvor je poput jednog od ovih tragova. Kada počnete od prvog traga, slijedite pokazivač od jednog čvora do sljedećeg dok ne pronađete ono što vam je potrebno.
Svaki čvor možete zamisliti kao malu omotnicu. Kuverta nosi karticu (podaci) i poruku (pokazivač). Ova bilješka vam govori koja je koverta sljedeća na redu.
Pogledajmo jednostavan način pisanja što je čvor:
Čvor = {podaci, pokazivač)
"Podaci" u čvoru su pohranjene informacije, a "pokazivač" je poput strelice koja vas usmjerava na sljedeći čvor. Za razliku od niza, povezani popis ne zahtijeva da svi čvorovi budu jedan pored drugog u memoriji; mogu biti bilo gdje, sve dok ih povezuju pokazivači.
Postoje različiti stilovi povezanih popisa. Evo tri uobičajene vrste:
Zamislite da slijedite kartu blaga. Svaki korak na karti govori vam gdje je sljedeći korak. Čak i ako dodate dodatni trag ili ga uklonite, svejedno možete pratiti čitajući trag na svakoj kartici. Ovako funkcionira povezana lista. Svaki čvor (ili trag) povezan je sa sljedećim, što vam omogućuje kretanje kroz popis korak po korak.
Nizovi i povezani popisi pomažu nam u pohranjivanju stavki, ali to čine na različite načine. Evo nekoliko usporedbi:
Svaka struktura podataka ima svoje dobre dijelove i svoje izazove. Razumijevanje toga pomaže vam odabrati ono najbolje za upotrebu.
Nizovi:
Prednosti:
Nedostaci:
Povezani popisi:
Prednosti:
Nedostaci:
Pogledajmo kako možemo koristiti niz na jednostavan način. Pretpostavimo da želite pohraniti svojih pet omiljenih boja. Kreirate polje s pet okvira. Zatim stavljate svaku boju u kutiju redom. Na primjer:
Sada, ako želite znati koja je boja u okviru 2, jednostavno pogledajte taj okvir i vidjet ćete "zeleno". Ovaj jednostavan pristup jedan je od najboljih dijelova korištenja niza.
Sada, pogledajmo povezani popis. Zamislite ovo kao lov na blago u kojem počinjete s tragom, a zatim slijedite upute kako biste pronašli sljedeći. U povezanom popisu počinjemo s čvorom koji sadrži neke podatke. Ovaj čvor ima pokazivač koji pokazuje koji čvor dolazi sljedeći.
Na primjer, zamislite da imate tri čvora na povezanom popisu koji pričaju zabavnu priču:
Počinjete od čvora 1 i slijedite pokazivač (trag) do čvora 2, zatim do čvora 3. Čak i ako želite dodati novi trag između bilo kojeg od njih, trebate promijeniti samo nekoliko pokazivača. To čini povezane popise vrlo fleksibilnima.
Korisno je zamisliti te strukture podataka u svom umu. Zamislite niz kao dugačak niz čistih, označenih kutija na polici. Svaka kutija sadrži nešto i ima fiksno mjesto. Sada zamislite povezani popis kao niz karata. Svaka karta ima bilješku koja pokazuje gdje je skrivena sljedeća karta. U nizu možete izravno skočiti na određeni okvir prema njegovom broju. Na povezanom popisu morate slijediti kartice redom.
Nizovi se koriste u mnogim svakodnevnim stvarima. Na primjer, zamislite kalendar. Kalendar ima fiksni broj dana u tjednu, a ti su dani poredani u nizu. Kad pogledate kalendar, točno znate koji je dan na kojem mjestu.
Povezani popisi koriste se kada se broj stavki može promijeniti tijekom vremena. Zamislite red ljudi koji čekaju ispred kamiona sa sladoledom. Ponekad se novi ljudi pridruže redu, a ponekad netko ode. Linija može rasti ili se smanjivati bez potrebe za stvaranjem nove fiksne strukture. To čini povezane popise vrlo korisnima u scenarijima u kojima se stvari često mijenjaju.
Odabir između nizova i povezanih popisa ovisi o tome što trebate učiniti sa svojim podacima. Ako znate da ćete uvijek imati fiksni broj stavki - poput dana u tjednu - tada je niz vrlo prikladan. Međutim, ako se količina podataka mijenja i potrebna vam je struktura koja se lako prilagođava, povezani popis bit će bolji izbor.
Na primjer, u računalnoj igrici niz se može koristiti za pohranjivanje rezultata za svaku razinu jer je broj razina fiksan. S druge strane, povezani popis može se koristiti za upravljanje popisom radnji ili poteza igrača, koji može rasti kako se igra nastavlja.
Kada trebate brzi pristup stavkama prema njihovoj poziciji, nizovi su najbolji izbor. To je zato što možete izravno skočiti na bilo koje mjesto ako znate njegov broj. Međutim, kada morate često dodavati ili uklanjati stavke, povezani popisi su od veće pomoći jer vam omogućuju da promijenite popis bez premještanja mnogo stavki.
Razmislite o tome na sljedeći način: ako imate album s naljepnicama s određenim brojem stranica, niz je poput tog albuma. Ali ako imate sve veću zbirku razglednica koje dodajete na oglasnu ploču, povezani popis je sličniji tome jer možete jednostavno dodati novu razglednicu između ostalih bez preuređivanja cijele ploče.
Pregledajmo glavne točke naše lekcije:
Nizovi:
Povezani popisi:
Razlike i upotrebe:
Ukratko, nizovi i povezani popisi dvije su važne podatkovne strukture koje se koriste za organiziranje podataka. Nizovi funkcioniraju poput niza fiksnih, numeriranih okvira, dok povezani popisi funkcioniraju poput potrage za blagom gdje vam svaki korak govori kamo ići dalje. Obje metode imaju svoje prednosti i koriste se u različitim situacijama ovisno o potrebama zadatka.
Razumijevanje ove dvije metode pohrane podataka vrlo je korisno. Mnogi računalni programi, igre i aplikacije koriste nizove i povezane popise u pozadini. Učeći kako rade, dobivate uvid u način na koji računala organiziraju i upravljaju podacima.
Zapamtite: nizovi su jednostavni i brzi kada je struktura fiksna, dok povezani popisi nude fleksibilnost kada se podaci mijenjaju. Bilo da zamislite niz ormarića ili tragove s blagom, ovi nam koncepti pomažu shvatiti kako se informacije pohranjuju i koriste svaki dan.
Ova lekcija vam je dala jasnu ideju o tome što su nizovi i povezani popisi. Dok nastavljate učiti i istraživati informatiku, ove osnovne ideje pomoći će vam da razumijete složenije teme. Oni su građevni blokovi naprednijih struktura podataka i algoritama.
Sažetak ključnih točaka:
Hvala vam što ste pročitali ovu lekciju o nizovima i povezanim listama. Nadamo se da ste uživali u učenju o ovim metodama pohranjivanja podataka na jasan i jednostavan način. Kako rastete i učite više, zapamtite ove osnovne strukture i kako one pomažu da računala rade učinkovito.
