Vezana lista

From Wikipedija
Jump to navigation Jump to search

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[edit | edit source]

  • 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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

Jednostruko vezane liste[edit | edit source]

CPT-LinkedLists-addingnode.svg

Ubacivanje novih čvorova u jednostruko vezanu listu

CPT-LinkedLists-deletingnode.svg

Brisanje čvorova iz jednostruko vezane liste

Jezična podrška[edit | edit source]

Mnogi programski jezici kao što su Lisp i Scheme imaju ugrađene pojedinačno povezane popise.

Povezane strukture podataka[edit | edit source]

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++)[edit | edit source]

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.

  1 #include <iostream>
  2 
  3 class JVL	// Jednostruko Vezana Lista
  4 {
  5 private:
  6 	struct Cvor		// svaki element sadrži podatak te pokazivač na sljedeći element;
  7 	{				// ako sljedeći element ne postoji, "sljedeci" je nullptr
  8 		int podatak;
  9 		Cvor* sljedeci;
 10 
 11 		Cvor(int noviPodatak)
 12 		{
 13 			podatak = noviPodatak;
 14 			sljedeci = nullptr;
 15 		}
 16 	};
 17 	Cvor* glava, * pokazivac;	// "pokazivac" se koristi za dohvaćanje podataka iz liste
 18 
 19 public:
 20 	JVL()
 21 	{
 22 		glava = nullptr;
 23 		pokazivac = nullptr;
 24 	}
 25 	~JVL()                      // dealocirati sve čvorove
 26 	{
 27 	    while (glava != nullptr)
 28 	    {
 29 	        pokazivac = glava->sljedeci;
 30 	        delete glava;
 31 	        glava = pokazivac;
 32 	    }
 33 	}
 34 
 35 	void ubaciNaPocetak(int podatak)
 36 	{
 37 		if (glava == nullptr)		// ako je lista prazna
 38 		{
 39 			glava = new Cvor(podatak);
 40 		}
 41 		else
 42 		{
 43 			Cvor* sljedeci = glava;		// sačuvaj referencu na trenutnu glavu
 44 			glava = new Cvor(podatak);	// postavi glavu na novi čvor
 45 			glava->sljedeci = sljedeci;	// poveži novi čvor sa prethodnom glavom
 46 		}
 47 	}
 48 
 49 	void ubaciNaKraj(int podatak)
 50 	{
 51 		if (glava == nullptr)		// ako je lista prazna
 52 		{
 53 			glava = new Cvor(podatak);
 54 		}
 55 		else
 56 		{
 57 			Cvor* surfer = glava;
 58 			while (surfer->sljedeci != nullptr)		// idi do posljednjeg čvora
 59 			{
 60 				surfer = surfer->sljedeci;
 61 			}
 62 
 63 			surfer->sljedeci = new Cvor(podatak);	// postavi sljedeći element na novo-kreirani čvor
 64 		}
 65 	}
 66 
 67 	void ubaciNakon(int relevantniPodatak, int noviPodatak)
 68 	{
 69 		if (sadrzi(relevantniPodatak) == false)
 70 		{
 71 			// Podatak se ne nalazi u listi, procesirati po zelji
 72 		}
 73 		else
 74 		{
 75 			// znamo da element postoji i ne moramo provjeravati "nullptr" uvjete
 76 
 77 			Cvor* surfer = glava;
 78 			while (surfer->podatak != relevantniPodatak)	// dok se ne dođe do željenog čvora
 79 			{
 80 				surfer = surfer->sljedeci;
 81 			}
 82 
 83 			Cvor* referenca = surfer->sljedeci;			// sačuvaj referencu na sljedeći element
 84 			surfer->sljedeci = new Cvor(noviPodatak);	// nakon ove naredbe lista nije povezana, moguće curenje memorije
 85 			surfer->sljedeci->sljedeci = referenca;		// poveži lanac
 86 
 87 			/* Primjer:
 88 			- lista prije ubacivanja:
 89 				1 2 3 4 6 7
 90 			- ubaci "5" nakon 4
 91 			- lista nakon ubacivanja:
 92 				1 2 3 4 "5"
 93 			- 6 i 7 više nisu povezani sa ostatkom liste => CURENE MEMORIJE!
 94 			- zbog toga je sačuvana referenca na element 6, odnosno njegova adresa
 95 			- spajanje adrese elementa 6 sa ostatkom liste:
 96 				1 2 3 4 "5" 6 7			
 97 			*/
 98 		}
 99 	}
100 
101 	bool sadrzi(int podatak)
102 	{
103 		Cvor* surfer = glava;
104 		while (surfer != nullptr)
105 		{
106 			if (surfer->podatak == podatak)
107 				return true;
108 			surfer = surfer->sljedeci;
109 		}
110 		return false;
111 	}
112 
113 	// Slijede metode pomoću kojih korisnik može dohvatiti podatke:
114 
115 	void idiDalje()
116 	{
117 		if (pokazivac == nullptr)
118 		{
119 			pokazivac = glava;
120 		}
121 		else if (pokazivac->sljedeci == nullptr)
122 		{
123 			std::cout << "Sljedeci element ne postoji\n";
124 		}
125 		else
126 		{
127 			pokazivac = pokazivac->sljedeci;
128 		}
129 	}
130 
131 	void postaviPokazivacNaPocetak()
132 	{
133 		pokazivac = glava;
134 	}
135 
136 	bool postojiSljedeci()
137 	{
138 		if (pokazivac == nullptr)	// pokazivac prethodno nije koristen
139 		{
140 			return glava != nullptr;	// ne postoji niti jedan element u listi
141 		}
142 		else
143 		{
144 			return pokazivac->sljedeci != nullptr;
145 		}
146 	}
147 
148 	int dohvatiPodatak()
149 	{
150 		if (pokazivac == nullptr)
151 		{
152 			std::cout << "Podatak ne postoji!\n";
153 			return -1;
154 		}
155 		return pokazivac->podatak;
156 	}
157 
158 };
159 
160 int main()
161 {
162 	JVL lista;
163 	
164 	for (int i = 0; i < 5; ++i)
165 	{
166 		lista.ubaciNaKraj(i);
167 	}
168 
169 	std::cout << "Ispis liste:\n";
170 	for (lista.postaviPokazivacNaPocetak(); /* nema uvjeta */; lista.idiDalje())
171 	{
172 		std::cout << lista.dohvatiPodatak() << " ";
173 		if (lista.postojiSljedeci() == false)
174 			break;
175 	}
176 	/*
177 	Ispis liste:
178 	0 1 2 3 4
179 	*/
180 
181 	return 0;
182 }