Choose jour language!

---

|

Povezane liste

Povezane liste su jedna od osnovnih struktura podataka i predstavljaju fleksibilniju alternativu nizovima i vektorima. Za razliku od njih, elementi u povezanoj listi (tzv. čvorovi) nisu smešteni u kontinualnim memorijskim lokacijama, već su povezani pokazivačima. Svaki čvor sadrži podatak i pokazivač na sledeći element liste.

Ovakva organizacija omogućava efikasno umetanje i brisanje elemenata, bez potrebe za pomeranjem celog niza. Međutim, pristup elementima po indeksu je sporiji, jer se mora prolaziti redom kroz listu.

Vrste povezanih lista

• Jednostruko povezana lista — svaki čvor pokazuje samo na sledeći element.
• Dvostruko povezana lista — svaki čvor sadrži pokazivače na prethodni i sledeći element.
• Kružno povezana lista — poslednji čvor pokazuje nazad na prvi čvor, stvarajući krug.

U ovoj lekciji fokusiraćemo se na jednostruko povezanu listu, jer predstavlja osnovu za razumevanje ostalih tipova.

Struktura čvora

Svaki čvor u jednostruko povezanoj listi obično se definiše pomoću strukture (ili klase) koja sadrži vrednost i pokazivač na sledeći čvor.

#include <iostream>
using namespace std;

struct Cvor {
    int vrednost;
    Cvor* sledeci;
};

Ova struktura je osnova svake povezane liste — svaki čvor zna samo gde se nalazi sledeći.

Dodavanje elemenata u listu

Sledeći primer pokazuje kako se elementi dinamički dodaju na kraj liste pomoću pokazivača.

#include <iostream>
using namespace std;

struct Cvor {
    int vrednost;
    Cvor* sledeci;
};

void dodajNaKraj(Cvor*& glava, int broj) {
    Cvor* novi = new Cvor;
    novi->vrednost = broj;
    novi->sledeci = nullptr;

    if (glava == nullptr)
        glava = novi;
    else {
        Cvor* tekuci = glava;
        while (tekuci->sledeci != nullptr)
            tekuci = tekuci->sledeci;
        tekuci->sledeci = novi;
    }
}

void ispisiListu(Cvor* glava) {
    while (glava != nullptr) {
        cout << glava->vrednost << " ";
        glava = glava->sledeci;
    }
    cout << endl;
}

int main() {
    Cvor* lista = nullptr;

    dodajNaKraj(lista, 10);
    dodajNaKraj(lista, 20);
    dodajNaKraj(lista, 30);

    cout << "Elementi liste: ";
    ispisiListu(lista);

    return 0;
}

Ovaj primer demonstrira osnovnu upotrebu povezanih lista. Za razliku od vektora, novi elementi se dodaju pomoću dinamičke alokacije (new), a pokazivači se koriste da bi se lista proširila.

Brisanje elemenata

Kod brisanja elemenata važno je ažurirati pokazivače i osloboditi memoriju kako ne bi došlo do curenja memorije (memory leak).

void obrisiListu(Cvor*& glava) {
    while (glava != nullptr) {
        Cvor* privremeni = glava;
        glava = glava->sledeci;
        delete privremeni;
    }
}

Ova funkcija prolazi kroz celu listu i briše čvor po čvor.

Prednosti i mane povezanih lista

• ✅ Dodavanje i brisanje elemenata je brzo i efikasno.
• ✅ Nema potrebe za unapred poznatom veličinom kao kod nizova.
• ❌ Pristup elementima je sporiji (zahteva sekvencijalno prelaženje).
• ❌ Potrebno je više memorije zbog pokazivača.

Vizuelni prikaz

+---------+     +---------+     +---------+
|  10     | --> |  20     | --> |  30     | --> nullptr
+---------+     +---------+     +---------+

Svaki čvor pokazuje na sledeći, dok poslednji pokazivač ima vrednost nullptr, što označava kraj liste.

Povezanost sa drugim strukturama

Povezane liste čine osnovu za izgradnju složenijih struktura podataka kao što su:

• Stek (Stack)
• Red (Queue)
• Grafovi (kao liste susedstva)

Na ovaj način povezana lista postaje temelj za razumevanje mnogih algoritama u oblasti struktura podataka.

Zadaci za vežbu

• Napraviti funkciju koja dodaje novi čvor na početak liste.
• Napraviti funkciju koja pronalazi najveći element u listi.
• Implementirati brisanje određenog elementa iz liste po vrednosti.

Zaključak

Povezane liste omogućavaju dinamičko upravljanje podacima i efikasne operacije umetanja i brisanja. Razumevanje ove strukture podataka ključno je za savladavanje složenijih koncepata kao što su stekovi, redovi i grafovi.

---

Dvostruko povezane liste

Dvostruko povezana lista (Doubly Linked List) predstavlja proširenje jednostruko povezane liste, gde svaki čvor sadrži dva pokazivača: jedan na prethodni, a drugi na sledeći element. Ova struktura omogućava kretanje kroz listu u oba smera — unapred i unazad.

Ovakav pristup je naročito koristan kod implementacije struktura kao što su redovi, stekovi i navigacija kroz elemente (npr. undo/redo mehanizmi).

Struktura čvora

#include <iostream>
using namespace std;

struct Cvor {
    int vrednost;
    Cvor* sledeci;
    Cvor* prethodni;
};

Za razliku od jednostruko povezane liste, čvor sada sadrži i pokazivač prethodni, čime omogućava obostranu povezanost.

Dodavanje elemenata na kraj dvostruko povezane liste

void dodajNaKraj(Cvor*& glava, int broj) {
    Cvor* novi = new Cvor;
    novi->vrednost = broj;
    novi->sledeci = nullptr;
    novi->prethodni = nullptr;

    if (glava == nullptr) {
        glava = novi;
        return;
    }

    Cvor* tekuci = glava;
    while (tekuci->sledeci != nullptr)
        tekuci = tekuci->sledeci;

    tekuci->sledeci = novi;
    novi->prethodni = tekuci;
}

Sada se čvorovi povezuju u oba smera: novi element dobija pokazivač na prethodni čvor, a prethodni čvor dobija pokazivač na novi.

Ispis liste unapred i unazad

void ispisiUnapred(Cvor* glava) {
    while (glava != nullptr) {
        cout << glava->vrednost << " ";
        if (glava->sledeci == nullptr) break; // čuvamo kraj
        glava = glava->sledeci;
    }
    cout << endl;
}

void ispisiUnazad(Cvor* kraj) {
    while (kraj != nullptr) {
        cout << kraj->vrednost << " ";
        kraj = kraj->prethodni;
    }
    cout << endl;
}

Dvostruko povezane liste omogućavaju jednostavno kretanje kroz elemente u oba pravca, što nije moguće kod jednostruko povezanih lista.

Vizuelni prikaz

nullptr <-- [10] <--> [20] <--> [30] --> nullptr

Svaki čvor ima pokazivač ulevo (prethodni) i udesno (sledeci), što omogućava navigaciju kroz listu u oba smera.

Prednosti i mane

• ✅ Omogućava kretanje u oba smera.
• ✅ Brže brisanje i umetanje čvorova u sredini liste.
• ❌ Troši više memorije zbog dodatnog pokazivača.
• ❌ Potrebno je pažljivo rukovati pokazivačima da ne dođe do grešaka.

Zadaci za vežbu

• Napraviti funkciju koja dodaje novi element na početak dvostruko povezane liste.
• Implementirati funkciju koja briše poslednji element iz liste.
• Proširiti ispis tako da se prikazuju adrese prethodnog i sledećeg čvora (radi učenja pokazivača).

Zaključak

Dvostruko povezane liste predstavljaju prirodno proširenje jednostruko povezanih lista i nude veću fleksibilnost prilikom navigacije i obrade podataka. Razumevanje ovih principa ključno je za naprednije strukture podataka, kao što su kružne liste, redovi sa prioritetom i implementacija složenih algoritama.

---

□ Nastavi sa učenjem

Nakon što si savladao povezane liste (uključujući jednostruke i dvostruko povezane), sledeći korak u razumevanju struktura podataka su stabla – hijerarhijske strukture koje omogućavaju efikasno pretraživanje i organizaciju podataka.

Ako želiš da se podsetiš prethodnog gradiva, pogledaj lekciju o Uvodu u vektore, koja predstavlja osnovu za razumevanje dinamičkih struktura podataka.

Zatim možeš preći na sledeću lekciju: Stabla, gde ćeš naučiti kako se podaci organizuju u vidu grananja i kako funkcionišu binarna stabla, pretraživanja i balansiranja.

⬅️  Prethodna lekcija: Uvod u vektore
➡️  Sledeća lekcija: Stabla

□ Savet: Preporučuje se da pre prelaska na stabla, samostalno implementiraš funkcije za dodavanje i brisanje elemenata u dvostruko povezanim listama.

---