C++ Povezana Lista

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 je potrebno implementirati red čekanja (queue).
  • Kada su česta umetanja i brisanja elemenata na bilo kojoj poziciji. (correct)
  • Kada su potrebni samo brzi pristupi elementima preko indeksa.

Šta je osnovni element povezane liste?

  • Čvor (correct)
  • Pokazivač
  • Struktura
  • Niz

Šta karakteriše jednostruko povezanu listu?

  • Podržava direktan pristup elementima putem indeksa.
  • Poslednji čvor pokazuje na prvi čvor.
  • Svaki čvor sadrži dva pokazivača.
  • Svaki čvor sadrži samo pokazivač na sljedeći čvor. (correct)

Kada je preporučljivo koristiti jednostruko povezanu listu?

<p>Kada je potrebno jednostavno dodavanje/brisanje na početku. (A)</p> Signup and view all the answers

Koja je glavna razlika između jednostruko i dvosmjerno povezane liste?

<p>Dvosmjerno povezana lista ima pokazivače na prethodni i sljedeći čvor. (D)</p> Signup and view all the answers

Koja je prednost dvosmjerno povezane liste u odnosu na jednostruko povezanu listu?

<p>Brži pristup prethodnom elementu u listi. (C)</p> Signup and view all the answers

Kada je pogodno koristiti dvosmjerno povezanu listu?

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

Šta karakteriše cikličnu listu?

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

Za koju vrstu problema je idealna ciklična lista?

<p>Za implementaciju beskonačnih ili kružnih struktura podataka. (D)</p> Signup and view all the answers

Šta se mora uraditi prilikom brisanja čvora iz povezane liste?

<p>Osloboditi memorijski prostor i izmijeniti odgovarajući pokazivač. (B)</p> Signup and view all the answers

Šta je rizik ako se ne oslobodi memorijski prostor prilikom brisanja čvora?

<p>Curenje memorije (<code>out of memory</code>). (C)</p> Signup and view all the answers

Kako se dodaje novi čvor na kraj povezane liste u C++?

<p>Prolaskom kroz listu do poslednjeg čvora i postavljanjem njegovog <code>next</code> pokazivača na novi čvor. (C)</p> Signup and view all the answers

U kontekstu implementacije jednostruko povezane liste u C++, koju ulogu ima atribut head u klasi LinkedList?

<p>Pokazuje na prvi čvor u listi. (C)</p> Signup and view all the answers

Šta bi se desilo ako biste pokušali da pristupite temp->next->data u jednostruko povezanoj listi, a temp->next je nullptr?

<p>Program bi se srušio (segmentation fault). (B)</p> Signup and view all the answers

Dat je sljedeći segment koda za brisanje prvog čvora u jednostruko povezanoj listi:

void deleteAtBeginning() {
  Node* temp = head;
  head = head->next;
  delete temp;
}

Pod kojim uslovom će ovaj kod uzrokovati grešku?

<p>Ako je lista prazna (head == nullptr). (A)</p> Signup and view all the answers

Flashcards

Povezana lista

Struktura podataka sastavljena od čvorova, gdje svaki čvor sadrži podatke i pokazivač na sljedeći čvor.

Jednostruko povezana lista

Vrsta povezane liste gdje svaki čvor ima pokazivač samo na sljedeći čvor.

Dvosmjerno povezana lista

Vrsta povezane liste gdje svaki čvor ima pokazivače i na sljedeći i na prethodni čvor.

Ciklična lista

Vrsta povezane liste gdje posljednji čvor pokazuje na prvi, čime se formira kružna struktura.

Signup and view all the flashcards

Dodavanje čvora

Postupak dodavanja novog elementa (čvora) u povezanu listu.

Signup and view all the flashcards

Brisanje čvora

Postupak uklanjanja elementa (čvora) iz povezane liste i oslobađanje memorije.

Signup and view all the flashcards

Dodavanje na početak liste

Dodaje element na početak liste.

Signup and view all the flashcards

Dodavanje na kraj liste

Dodaje element na kraj liste.

Signup and view all the flashcards

Brisanje s početka liste

Uklanja element s početka liste.

Signup and view all the flashcards

Brisanje s kraja liste

Uklanja element s kraja liste.

Signup and view all the flashcards

std::list u C++

Standardna biblioteka u C++ koja omogućuje korištenje dvosmjerno povezane liste.

Signup and view all the flashcards

Čvor (Node)

Osnovni element povezane liste koji sadrži podatke i jedan ili više pokazivača.

Signup and view all the flashcards

Klasa Povezane Liste

U objektno orijentiranom programiranju, klasa koja predstavlja povezanu listu i sadrži operacije za manipulaciju listom.

Signup and view all the flashcards

Study Notes

Korištenje list iz biblioteke C++

  • C++ standardna biblioteka nudi list, dvosmjerno povezanu listu korisnu za česta umetanja i brisanja elemenata na bilo kojoj poziciji.
  • Primjer koda uključuje dodavanje elemenata na početak i kraj liste, brisanje elemenata s početka i kraja te iteriranje kroz listu.

Povezana lista

  • Povezana lista je struktura podataka sastavljena od čvorova.
  • Čvor je osnovni element povezane liste, baziran na strukturi podataka koja sadrži najmanje jedan pokazivač.
  • Povezanu listu čini lanac čvorova povezanih pokazivačima.

Jednostruko povezana lista (Singly Linked List)

  • Svaki element (čvor) sadrži podatke i pokazivač na sljedeći čvor.
  • Posljednji čvor ima nullptr pokazivač, označavajući kraj liste.
  • Efikasno dodavanje i brisanje s početka i kraja liste.
  • Ne podržava direktni pristup elementima putem indeksa.
  • Svaki čvor ima samo jedan pokazivač na sljedeći čvor.
  • Koristi se kada je potrebno jednostavno dodavanje/brisanje na početku i kada nije često potreban pristup specifičnim elementima po indeksu.

Dvosmjerno povezana lista (Doubly Linked List)

  • Slična jednostruko povezanoj listi, ali svaki čvor sadrži dva pokazivača: jedan na sljedeći čvor i jedan na prethodni čvor.
  • Brzo dodavanje i brisanje na oba kraja liste i između elemenata.
  • Sadrži dodatnu memoriju zbog dva pokazivača u svakom čvoru.
  • Pruža brži pristup prethodnom elementu u listi.
  • Koristi se kada je potrebno kretanje kroz listu u oba smjera ili efikasno brisanje sa bilo koje pozicije u listi.

Ciklična lista (Circular List)

  • Može biti jednostruko ili dvosmjerno povezana.
  • Posljednji čvor je povezan s prvim, stvarajući ciklus.
  • Idealna za implementaciju problema koji zahtijevaju beskonačnu ili kružnu strukturu podataka (npr. kružni baferi).

Dodavanje čvora u listu

  • Čvor se može dodati na početak, kraj ili unutar liste.
  • Prilikom dodavanja na kraj, potrebno je:
    • Deklarisati promjenljivu tipa strukture.
    • Unijeti podatke u elemente strukture čvora.
    • Ako lista nije prazna, postojeći zadnji čvor se mijenja tako da njegov pokazivač pokazuje na novi čvor.
    • Ako je lista prazna, adresa novog čvora se dodjeljuje pointeru start_ptr.

Dodavanje čvora na početak liste

  • Nakon kreiranja novog čvora i unosa podataka:
    • U novi čvor se upisuje adresa trenutnog prvog čvora u listi.
    • U start_ptr se postavlja adresa novog čvora.
    • Ako je lista prazna, start_ptr pokazuje na novi čvor.

Dodavanje čvora na određeno mjesto

  • Ako je pozicija 0, element se dodaje na početak.
  • Inače, pronalazi se prethodni čvor, a novi čvor se umeće između njega i sljedećeg.

Brisanje čvora

  • Čvor može biti na početku, kraju ili u sredini liste.
  • Nakon brisanja čvora, memorijski prostor mora biti oslobođen, inače postoji rizik od "out of memory".
  • Oslobađanje memorijskog prostora se vrši naredbom delete.

Brisanje čvora na kraju liste

  • Potrebna su dva pomoćna pokazivača:
    • Jedan pokazuje na zadnji čvor u listi.
    • Drugi na njegov prethodnik.
  • Predzadnji čvor se modifikuje tako da njegov pokazivač slijedeći sadrži null, označavajući kraj liste.
  • Ako lista sadrži samo jedan čvor, start_ptr se postavlja na null i čvor se briše.

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