C++: Korištenje `list` i povezane liste

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Kada je najpogodnije koristiti list iz C++ standardne biblioteke?

  • Kada je potrebno sortirati elemente u listi.
  • Kada su česta umetanja i brisanja elemenata na bilo kojoj poziciji. (correct)
  • Kada je potrebno često pristupati elementima po indeksu.
  • Kada je potrebno pretraživati listu za određenim elementom.

Šta karakteriše jednostruko povezanu listu?

  • Svaki čvor sadrži dva pokazivača.
  • Nema pokazivača između čvorova.
  • Svaki čvor sadrži samo jedan pokazivač na sljedeći čvor. (correct)
  • Svaki čvor sadrži pokazivač na prethodni i sljedeći čvor.

Koja je osnovna karakteristika dvostruko povezane liste u odnosu na jednostruko povezanu listu?

  • Dvosmjerno povezane liste omogućavaju brži pristup prethodnom elementu. (correct)
  • Jednostruko povezane liste omogućavaju brže umetanje elemenata.
  • Dvosmjerno povezane liste su memorijski efikasnije.
  • Jednostruko povezane liste su jednostavnije za implementaciju.

Kada je prikladno koristiti dvosmjerno povezanu listu?

<p>Kada je potrebno kretanje kroz listu u oba smjera. (C)</p> Signup and view all the answers

Šta karakteriše cikličnu listu?

<p>Posljednji čvor pokazuje na prvi čvor. (C)</p> Signup and view all the answers

U kojem scenariju je najpogodnije koristiti cikličnu listu?

<p>Kada je potrebna beskonačna ili kružna struktura podataka. (C)</p> Signup and view all the answers

Koji korak je neophodan prilikom dodavanja čvora na kraj jednostruko povezane liste?

<p>Kreirati novi čvor i postaviti pokazivač posljednjeg čvora na novi čvor. (D)</p> Signup and view all the answers

Koja je svrha postavljanja vrijednosti NULL u slijedeci članicu strukture čvora prilikom dodavanja na kraj liste?

<p>Da se označi da je taj čvor posljednji u listi. (A)</p> Signup and view all the answers

Šta je potrebno uraditi prije brisanja čvora iz povezane liste?

<p>Izmjeniti vrijednost odgovarajućeg pokazivača i osloboditi memorijski prostor. (C)</p> Signup and view all the answers

Šta se dešava ako se ne oslobodi memorijski prostor prilikom brisanja čvora iz liste?

<p>Dolazi do curenja memorije (memory leak). (A)</p> Signup and view all the answers

Kako se briše prvi čvor u jednostruko povezanoj listi?

<p>Pomjeranjem pokazivača glave (head) na sljedeći čvor i oslobađanjem memorije prethodne glave. (A)</p> Signup and view all the answers

Šta je potrebno provjeriti prije brisanja posljednjeg čvora u listi?

<p>Da li lista sadrži samo jedan čvor. (C)</p> Signup and view all the answers

Šta je osnovni element povezane liste?

<p>Čvor (D)</p> Signup and view all the answers

Šta čini povezanu listu?

<p>Lanac čvorova koje međusobno povezuju pointeri. (C)</p> Signup and view all the answers

Šta je 'memory leak' u kontekstu rada sa povezanim listama?

<p>Neoslobađanje memorijskog prostora nakon brisanja čvora. (D)</p> Signup and view all the answers

U kodu za dodavanje elementa na kraj jednostruko povezane liste, koja je svrha petlje while (temp->next != nullptr)?

<p>Pronalaženje posljednjeg elementa u listi. (B)</p> Signup and view all the answers

Šta predstavlja head u implementaciji povezane liste?

<p>Pokazivač na prvi element u listi. (D)</p> Signup and view all the answers

Kako biste inicijalizirali praznu jednostruko povezanu listu?

<p><code>head = nullptr;</code> (A)</p> Signup and view all the answers

Kako biste izmijenili kod za brisanje posljednjeg čvora u jednostruko povezanoj listi (gdje head pokazuje na početak, a ne postoji tail pokazivač) kako bi se izbjeglo curenje memorije ako lista sadrži samo jedan čvor?

<p>Provjerava se da li <code>head-&gt;next == nullptr</code> prije brisanja. Ako je to istina, obriše se <code>head</code> i <code>head</code> se postavi na <code>nullptr</code>. (A)</p> Signup and view all the answers

Šta je glavna prednost korištenja push_front() metode sa std::list u C++ u odnosu na ručno implementiranje dodavanja na početak jednostruko povezane liste?

<p><code>push_front()</code> ima bolju vremensku složenost i izbjegava potencijalne greške pri ručnoj implementaciji. (A)</p> Signup and view all the answers

Pretpostavimo da imate jednostruko povezanu listu sortiranu u rastućem redoslijedu. Želite ubaciti novi čvor sa vrijednošću koja se već nalazi u listi, tako da lista ostane ispravno sortirana. Gdje biste trebali ubaciti novi čvor?

<p>Iza posljednjeg čvora sa istom vrijednosti. (D)</p> Signup and view all the answers

Ako imate cikličnu jednostruko povezanu listu i želite da pronađete srednji element, koji algoritam bi bio najefikasniji (uzimajući u obzir da ne znate dužinu liste)?

<p>Koristiti dva pokazivača, jedan koji se kreće jedan korak naprijed, a drugi dva koraka naprijed. Kada brži pokazivač sustigne sporiji, sporiji je na sredini. (A)</p> Signup and view all the answers

Imate dvosmjerno povezanu listu i treba vam funkcija koja efikasno pronalazi element na $n$-tom mjestu od kraja liste. Koja strategija je najbolja?

<p>Krenuti od kraja liste i iterirati $n$ puta. (D)</p> Signup and view all the answers

Napiši kod za dodavanje čvora na određeno mjesto.

<p>void insertAtPosition(int val, int position) { Node* newNode = new Node(val); if (position == 0) { insertAtBeginning(val); // Ako je pozicija 0, samo dodaj na početak return; }</p> <pre><code>Node* temp = head; for (int i = 0; i &lt; position - 1; i++) { // Nađi prethodni čvor if (temp == nullptr) return; // Ako je pozicija van opsega liste temp = temp-&gt;next; } newNode-&gt;next = temp-&gt;next; // Novi čvor sada pokazuje na sledeći čvor temp-&gt;next = newNode; // Prethodni čvor sada pokazuje na novi čvor </code></pre> <p>}</p> Signup and view all the answers

Objasni šta se dešava u ovom segmentu: if (head == nullptr) { head = newNode; newNode->next = head; }

<p>Inicijalizuje cikličnu listu ako je prazna.</p> Signup and view all the answers

Flashcards

Šta je povezana lista?

Struktura podataka sastavljena od čvorova povezanih pomoću pokazivača.

Kada koristiti list?

Omogućava efikasno dodavanje i brisanje elemenata na bilo kojoj poziciji u listi.

Šta je jednostruko povezana lista?

Lista u kojoj svaki čvor pokazuje samo na sljedeći čvor u listi.

Šta je dvosmjerno povezana lista?

Lista u kojoj svaki čvor pokazuje i na sljedeći i na prethodni čvor.

Signup and view all the flashcards

Šta je ciklična lista?

Lista u kojoj posljednji čvor pokazuje na prvi, formirajući ciklus.

Signup and view all the flashcards

Šta znači dodati čvor na kraj?

Dodavanje novog čvora na kraj postojeće liste.

Signup and view all the flashcards

Šta znači dodati čvor na početak?

Ubacivanje novog čvora na početnu poziciju u listi.

Signup and view all the flashcards

Zašto je važno osloboditi memoriju?

Uklanjanje čvora iz liste oslobađa memoriju koju zauzima.

Signup and view all the flashcards

Šta znači brisanje prvog čvora?

Uklanjanje prvog čvora iz liste.

Signup and view all the flashcards

Šta znači brisanje zadnjeg čvora?

Uklanjanje zadnjeg čvora iz liste.

Signup and view all the flashcards

Study Notes

Korištenje list iz biblioteke

  • C++ standardna biblioteka nudi list, dvosmjerno povezanu listu.
  • Pogodna je za česta umetanja i brisanja elemenata na bilo kojoj poziciji.
  • push_front() dodaje element na početak liste.
  • push_back() dodaje element na kraj liste.
  • pop_front() briše prvi element.
  • pop_back() briše posljednji element.

Povezana lista

  • Povezana lista je složena struktura podataka izgrađena od čvorova.
  • Čvor sadrži podatke i najmanje jedan pokazivač.
  • Jednostruko povezana lista ima svaki čvor sa pokazivačem na sljedeći, a posljednji čvor pokazuje na nullptr.
  • Osobine jednostruko povezane liste uključuju efikasno dodavanje i brisanje s početka i kraja, ali ne podržava direktan pristup elementima preko indeksa.
  • Sintaksa za jednostruko povezane C++ liste uključuje definisanje strukture čvora i operacije za manipulaciju listom.
  • U C++, definicija čvora (Node) uključuje podatke (data) i pokazivač na sljedeći čvor (next).
  • U LinkedList klasi, append() metoda dodaje element na kraj liste.

Dvosmjerno Povezana Lista (Doubly Linked List)

  • Dvosmerno povezana lista slična je jednostruko povezanoj, ali svaki čvor ima dva pokazivača.
  • Jedan pokazivač pokazuje na sljedeći čvor, a drugi na prethodni čvor.
  • Dvosmerno povezana lista omogućuje brzo dodavanje i brisanje na oba kraja, poboljšavajući brzinu pristupa prethodnom elementu.
  • Sintaksa za dvosmerno povezanu listu uključuje strukturu čvora sa pokazivačima na sljedeći i prethodni čvor.
  • Dvosmerno povezana struktura čvora (Node) u C++ uključuje podatke (data), pokazivač na sljedeći čvor (next), i pokazivač na prethodni čvor (prev).

Ciklična lista (Circular List)

  • Može biti jednostruko ili dvosmjerno povezana, ali joj je posljednji čvor povezan s prvim.
  • To stvara ciklus.
  • Idealna je za implementaciju problema s beskonačnim ili kružnim strukturama podataka (kružni baferi).
  • Dodavanje elementa u cikličkoj listi obuhvaća kreiranje novog čvora i povezivanje s listom, pazeći da posljednji čvor pokazuje na prvi (ciklično).

Dodavanje čvora u listu

  • Čvor se može dodati na početak, kraj ili u sredinu.
  • Za dodavanje čvora na kraj, prvo se deklariše struktura čvora i rezerviše memorijski prostor.
  • Zatim se unose podaci u elementi strukture čvora, a ako lista nije prazna, zadnji čvor se mijenja da pokazuje na novi.

Brisanje čvora

  • Kod brisanja čvora, oslobađa se memorijski prostor pomoću naredbe delete.
  • Kod brisanja prvog čvora, sačuva se adresa u pomoćni pokazivač, promijeni se da startni pokazivač pokazuje na sljedeći čvor, a zatim se izbriše početni čvor.
  • Brisanje na kraju liste zahtijeva dva pomoćna pokazivača: jedan za zadnji čvor, drugi za prethodni.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser