Vezana lista
U računarstvu, vezane liste su linearne zbirke elemenata podataka čiji redoslijed nije zadan njihovim fizičkim smještajem u memoriji. Umjesto toga, svaki element pokazuje na sljedeći. To je struktura podataka koja se sastoji od zbirke čvorova koji zajedno predstavljaju niz. U svom najosnovnijem obliku, svaki čvor sadrži: podatak i referencu (drugim riječima poveznicu) na sljedeći čvor u nizu. Ova struktura omogućava učinkovito umetanje ili uklanjanje elemenata iz bilo kojeg položaja u nizu tijekom iteracije. Složenije varijante dodaju dodatne veze, omogućujući učinkovitije umetanje ili uklanjanje čvorova u proizvoljnim položajima. Nedostatak povezanih lista je taj što je vrijeme pristupa linearno, a ne konstantno kao u slučaju nizova. Brži pristup, kao što je slučajni pristup, nije izvediv. Nizovi imaju bolje predmemoriranje u odnosu na povezane popise.
Nedostaci
- Koriste više memorije od nizova zbog pohrane koju koriste njihovi pokazivači .
- Čvorovi na povezanom popisu moraju se čitati sekvencijalno; na primjer, da bi se došlo do stotog elementa, mora se prijeći prvih devedeset devet.
- Čvorovi se pohranjuju nesmetano, uvelike povećavajući vremenska razdoblja potrebna za pristup pojedinim elementima na popisu, posebno sa CPU predmemorijom .
- Teškoće nastaju na povezanim popisima kada je u pitanju obrnuto kretanje. Na primjer, pojedinačno povezani popisi nezgodni su za kretanje unatrag, a dok su dvostruko povezani popisi nešto lakši za čitanje, memorija se troši za dodjelu prostora za stražnji pokazivač .
Osnovni pojmovi i nomenklatura
Svaki zapis povezanog popisa često se naziva 'element' ili 'čvor '.
Polje svakog čvora koji sadrži adresu sljedećeg čvora obično se naziva "sljedeća veza" ili "sljedeći pointer". Preostala polja poznata su kao polja 'podaci', 'informacije', 'vrijednost', 'teret' ili 'payload'.
"Glava" popisa je njegov prvi čvor. 'Rep' popisa može se odnositi na ostatak popisa nakon glave ili na posljednji čvor u popisu. U Lispu i nekim izvedenim jezicima, sljedeći čvor može se nazvati "cdr" (izgovara se could-er; eng.) na popisu, dok se korisni teret glavnog čvora može nazvati "car" (eng.).
Jednostruko vezana lista
Pojedinačno povezani popisi sadrže čvorove koji imaju podatkovno polje kao i polje "Sljedeće" što upućuje na sljedeći čvor u liniji čvorova. Operacije koje se mogu izvesti na pojedinačno povezanim popisima uključuju umetanje, brisanje i prijelaz.
Dvostruko vezana lista
U 'dvostruko vezanim listama', svaki čvor, osim veze sljedećeg čvora, sadrži i drugu vezu na 'prethodni' čvor u nizu. Dvije veze mogu se nazvati 'forward('s') i 'backwards', ili 'next' i 'prev'('previous').
Višestruko vezana lista
U 'višestruko vezanim listama' svaki čvor sadrži dva ili više polja veze, a svako se polje koristi za povezivanje istog skupa podataka u različitom redoslijedu istog skupa (npr. po imenu, odjelu, datumu rođenja, itd). Iako se dvostruko povezani popisi mogu promatrati kao posebni slučajevi višestruko povezanih popisa, činjenica da su dva i više naloga međusobno suprotna vodi u jednostavnije i učinkovitije algoritme, pa se obično tretiraju kao zasebni slučaj. Primjer višestruko vezane liste su AVL stabla.
Kružno vezane liste
U posljednjem čvoru popisa polje veze često sadrži null, posebna vrijednost se koristi da naznači nedostatak daljnjih čvorova. Manje uobičajena konvencija je da se ukaže na prvi čvor popisa; u tom se slučaju kaže da je popis „kružni“ ili „kružno povezan“; u protivnom se kaže da je 'otvoren' ili 'linearan'. To je popis na kojem zadnji pokazivač pokazuje na prvi čvor.
U slučaju kružnog dvostruko povezanog popisa (dvostruko vezanog prstena), prvi čvor također ukazuje na posljednji čvor popisa.
Sentinel čvorovi
U nekim realizacijama može se dodati dodatni 'sentinel' ili 'dummy' čvor prije prvog zapisa podataka ili nakon posljednjeg. Ova konvencija pojednostavljuje i ubrzava neke algoritme za obradu popisa osiguravajući da se sve veze mogu sigurno dereferencirati i da svaki popis (čak i onaj koji ne sadrži elemente podataka) uvijek ima čvor "prvi" i "zadnji". Primjer korištenja je implementacija iteratora.
Vezane liste u odnosu na dinamičke nizove
Dinamički niz je struktura podataka koja neprekidno raspoređuje sve elemente u memoriji i drži broj trenutnog broja elemenata. Ako je premašen prostor rezerviran za dinamički niz, on će se preraspodijeliti i (možda) kopirati, što je skupa operacija.
Povezani popisi imaju nekoliko prednosti u odnosu na dinamičke nizove. Umetanje ili brisanje elementa na određenoj točki popisa, pod pretpostavkom da smo već indeksirali pokazivač na čvor (prije onoga za uklanjanje ili prije točke umetanja), je operacija konstantnog trajanja, dok će umetanje u dinamički niz na nasumičnim mjestima zahtijevati pomicanje polovine elemenata u prosjeku, a svih elementi u najgorem slučaju. Premda netko može "izbrisati" element iz arhive u stalnom vremenu tako što je na neki način označio njegov utor "praznim", to uzrokuje fragmentaciju koja spriječava izvedbu iteracije.
Operacije s vezanim listama
Jednostruko vezane liste
Ubacivanje novih čvorova u jednostruko vezanu listu
Brisanje čvorova iz jednostruko vezane liste
Jezična podrška
Mnogi programski jezici kao što su Lisp i Scheme imaju ugrađene pojedinačno povezane popise.
Povezane strukture podataka
I stog i redovi redovno se implementiraju pomoću vezanih listâ te jednostavno ograničavaju vrstu podržanih operacija.
Lista preskakanja je povezani popis nadopunjen slojevima pokazivača za brzo preskakanje velikog broja elemenata i zatim spuštanje na sljedeći sloj. Taj se postupak nastavlja sve do donjeg sloja, što je stvarni popis.
Binarno stablo može se promatrati kao vrsta povezanog popisa gdje su elementi i sami povezani popisi iste prirode, a formiraju logičko stablo. Rezultat toga je da svaki čvor može sadržavati referencu na prvi čvor jednog ili dva druga povezana popisa, koji zajedno sa svojim sadržajem formiraju podstabla ispod tog čvora.
Nevaljale vezane liste je povezani popis u kojem svaki čvor sadrži niz vrijednosti podataka. To dovodi do poboljšanja performansi predmemorije, jer je više elemenata popisa neprekidno u memoriji i smanjeno je spremanje memorije jer treba pohraniti manje metapodataka za svaki element popisa.
Hash tablica može koristiti povezane popise za spremanje lanaca stavki koje su hash na isti položaj u hash tablici.
Heap dijeli neka svojstva narudžbe na povezanom popisu, ali gotovo se uvijek provodi pomoću polja. Umjesto referenci od čvora do čvora, sljedeći i prethodni indeksi podataka izračunavaju se koristeći indeks trenutnih podataka.
Samoorganizirajuća lista preuređuje svoje čvorove na temelju nekih heuristička, što smanjuje vrijeme pretraživanja za pretraživanje podataka držeći čvorove kojima se obično pristupa na čelu popisa.
Implementacija (C++)
Sljedeći programski isječak prikazuje kreiranje klase koja predstavlja jednostavnu jednostruko vezanu listu (eng. Singly-linked list) te nekoliko relevantnih metoda:
- Ubacivanje novih čvorova na početak
- Ubacivanje novih čvorova na kraj
- Ubacivanje novih čvorova nakon određenog elementa
- Provjeravanje postoji li određeni element u listi
- Metode pomoću kojih će korisnik prolaziti kroz elemente pri korištenju klase
U pravilu se ovakva klasa ne koristi. U praksi su klase lista implementirane pomoću predložaka, elementi se dohvaćaju pomoću iteratora te se implementiraju konstruktor kopiranja i prijenosa, operator pridruživanja sa i bez semantike prijenosa i slično. Također, ovisno o potrebi, mogu se implementirati metode za brisanje elemenata. Programski isječak je namijenjen da bude što jednostavniji da razumijevanje i početna implementacija lista bude što jednostavnija.
#include <iostream>
class JVL // Jednostruko Vezana Lista
{
private:
struct Cvor // svaki element sadrži podatak te pokazivač na sljedeći element;
{ // ako sljedeći element ne postoji, "sljedeci" je nullptr
int podatak;
Cvor* sljedeci;
Cvor(int noviPodatak)
{
podatak = noviPodatak;
sljedeci = nullptr;
}
};
Cvor* glava, * pokazivac; // "pokazivac" se koristi za dohvaćanje podataka iz liste
public:
JVL()
{
glava = nullptr;
pokazivac = nullptr;
}
~JVL() // dealocirati sve čvorove
{
while (glava != nullptr)
{
pokazivac = glava->sljedeci;
delete glava;
glava = pokazivac;
}
}
void ubaciNaPocetak(int podatak)
{
if (glava == nullptr) // ako je lista prazna
{
glava = new Cvor(podatak);
}
else
{
Cvor* sljedeci = glava; // sačuvaj referencu na trenutnu glavu
glava = new Cvor(podatak); // postavi glavu na novi čvor
glava->sljedeci = sljedeci; // poveži novi čvor sa prethodnom glavom
}
}
void ubaciNaKraj(int podatak)
{
if (glava == nullptr) // ako je lista prazna
{
glava = new Cvor(podatak);
}
else
{
Cvor* surfer = glava;
while (surfer->sljedeci != nullptr) // idi do posljednjeg čvora
{
surfer = surfer->sljedeci;
}
surfer->sljedeci = new Cvor(podatak); // postavi sljedeći element na novo-kreirani čvor
}
}
void ubaciNakon(int relevantniPodatak, int noviPodatak)
{
if (sadrzi(relevantniPodatak) == false)
{
// Podatak se ne nalazi u listi, procesirati po zelji
}
else
{
// znamo da element postoji i ne moramo provjeravati "nullptr" uvjete
Cvor* surfer = glava;
while (surfer->podatak != relevantniPodatak) // dok se ne dođe do željenog čvora
{
surfer = surfer->sljedeci;
}
Cvor* referenca = surfer->sljedeci; // sačuvaj referencu na sljedeći element
surfer->sljedeci = new Cvor(noviPodatak); // nakon ove naredbe lista nije povezana, moguće curenje memorije
surfer->sljedeci->sljedeci = referenca; // poveži lanac
/* Primjer:
- lista prije ubacivanja:
1 2 3 4 6 7
- ubaci "5" nakon 4
- lista nakon ubacivanja:
1 2 3 4 "5"
- 6 i 7 više nisu povezani sa ostatkom liste => CURENE MEMORIJE!
- zbog toga je sačuvana referenca na element 6, odnosno njegova adresa
- spajanje adrese elementa 6 sa ostatkom liste:
1 2 3 4 "5" 6 7
*/
}
}
bool sadrzi(int podatak)
{
Cvor* surfer = glava;
while (surfer != nullptr)
{
if (surfer->podatak == podatak)
return true;
surfer = surfer->sljedeci;
}
return false;
}
// Slijede metode pomoću kojih korisnik može dohvatiti podatke:
void idiDalje()
{
if (pokazivac == nullptr)
{
pokazivac = glava;
}
else if (pokazivac->sljedeci == nullptr)
{
std::cout << "Sljedeci element ne postoji\n";
}
else
{
pokazivac = pokazivac->sljedeci;
}
}
void postaviPokazivacNaPocetak()
{
pokazivac = glava;
}
bool postojiSljedeci()
{
if (pokazivac == nullptr) // pokazivac prethodno nije koristen
{
return glava != nullptr; // ne postoji niti jedan element u listi
}
else
{
return pokazivac->sljedeci != nullptr;
}
}
int dohvatiPodatak()
{
if (pokazivac == nullptr)
{
std::cout << "Podatak ne postoji!\n";
return -1;
}
return pokazivac->podatak;
}
};
int main()
{
JVL lista;
for (int i = 0; i < 5; ++i)
{
lista.ubaciNaKraj(i);
}
std::cout << "Ispis liste:\n";
for (lista.postaviPokazivacNaPocetak(); /* nema uvjeta */; lista.idiDalje())
{
std::cout << lista.dohvatiPodatak() << " ";
if (lista.postojiSljedeci() == false)
break;
}
/*
Ispis liste:
0 1 2 3 4
*/
return 0;
}