Povezane Liste

-Strukture Podataka-

Website maintained by ntrifunovic Theme by mattgraham modified by ntrifunovic

(eng. Linked List)

Povezana lista je linearna struktura podataka, tj. podaci su u nekom linearnom poretku.

Grafička ilustracija povezane liste:

ilustracija povezena lista

Vrste povezanih lista

Primer implementacije

struct Elem {
    Podaci p;
    Elem* next;
    Elem* prev;
};

Elem* head; // Pokazivac na pocetak liste

Jednostruko povezane liste sadrze samo pokazivac next, a dvostruko povezane liste sadrze i next i prev pokazivac.

Primer implementacije jednostuko povezanih listi:

struct Elem {
    Podaci p;
    Elem* next;
};

Ubacivanje elementa

// Ubacujemo element n iza elementa e
void ubaci(Elem *e, Elem *n) {
    n->sled = e->sled;
    n->prev = e;
    e->sled->prev = n;
    e->sled = n;
}

Izbacivanje elementa

// Izbacuje element e iz povezane liste
void izbaci(Elem* e) {
    Elem* prev = e->prev;
    Elem* next = e->next;

    prev->next = next;
    next->prev = prev;
}

Napomena: Pretpostavlja se da postoji poslednji dummy element. Da li bi ova implementacija radila da on ne postoji ?

comments powered by Disqus