Wikipedija

Vezana lista: razlika između inačica

Pregledaj povijest
← Starija izmjenaNovija izmjena →
Izbrisani sadržaj Dodani sadržaj
VizualnoWikitekst
Generalna izmjena stranice da bi se omogućilo lakše razumijevanje i implementacija u kodu
Redak 1:
'''Vezana lista''' (vezani[[Engleski jezik|eng]]. Linked popislist) je dinamičnapromjenjiva [[podatkovna struktura]] koja predstavlja niz povezanih [[element|elemenata]]. Elementi su povezani logički, a fizički se mogu nalaziti na raznim mjestima u memoriji.[[Slika:Singly-linked-list.svg|mini|400px|Slika 1. Primjer jednostruko vezane liste|alt=]]
Svaki element vezane liste sastavljen je od sadržaja te [[Pokazivač (računarstvo)|pokazivača]] na sljedeći element. Sadržaj je obično sastavljen od [[Ključ (računarstvo)|ključa]] (eng. key) i informacije (eng. info), odnosno [[Podatak|podatka]]. S obzirom na kompleksnost liste, mora biti implementirana pomoću pokazivača. Ako je neki pokazivač <code>nullptr</code>, to znači da taj element ne postoji.
 
<br />
[[Slika:Singly-linked-list.svg|mini|400px|center|Jednostruka vezana lista, odnosno jednostruko povezani popis]]
== Svrha te usporedba sa uobičajenim [[Polje (računarstvo)|poljem]]==
U polju se elementima pristupa izravno, odnosno sa zbrajanjem pokazivača na početak polja i željenog indeksa. U vezanim listama se elementima pristupa slijedno. To znači da, ako želimo doći do elementa pod indeksom 100, moramo pomoću pokazivača prvo prijeći prvih 99 elemenata liste. U toj situaciji vezane liste su mnogo sporije od uobičajenih polja.
 
Međutim, vezane liste ne koriste se u istim situacijama. Zamislimo da imamo obično polje veličine od 1000 elemenata. Da bismo dodali još jedan element, moramo alocirati barem 1001 novih mjesta drugdje u memoriji, kopirati sve podatke iz prethodnog polja i izbrisati prethodno polje. U slučaju da imamo 1000 elemenata u vezanoj listi i želimo dodati novi, tada ćemo samo dinamički alocirati jedan element te ga povezati sa posljednjim elementom.
Elementima vezane [[Lista (računarstvo)|liste]] se pristupa [[slijed]]no, za razliku od [[Polje (matematika)|polja]], gdje se elementima pristupa izravno. Vezana lista je dinamička [[struktura]], jer u njoj za razliku od polja kojemu je broj elemenata obvezno zadan prije nego će se rabiti polje, vezanoj se listi broj elemenata dinamično mijenja.<ref>[http://www.student.foi.hr/~darados/Osnove_programiranja/predavanje7.ppt. Fakultet organizacije i informatike] Danijel Radošević: Osnove programiranja, stranicama pristupljeno 14. rujna 2011.</ref>
 
U slučaju da imamo 1000 elemenata u polju i želimo izbrisati jedan, tada bismo mogli ili kreirati novo polje od barem 999 elemenata, kopirati elemente iz prethodnog polja i izbrisati prethodno polje, ili bismo mogli sve elemente nakon elementa koji je potrebno obrisati premjestiti za jedno mjesto u lijevo, te smanjiti varijablu koja označava veličinu polja na 999 unatoč tome što je stvarna veličina 1000. U vezanim listama, ono što bismo napravili je povezali prethodni i sljedeći element elementa kojega želimo izbrisati, nakon čega bismo izbrisali, odnosno dealocirali željeni element.
Element vezane liste ima sadržaj, a osim njega ima još i pokazivač na sljedeći element u listi.
 
Zanimljivo je da vezana lista može biti prazna, odnosno da nema elemenata. Stoga ju se ne zadaje prvim elementom, nego [[pokazivač]]em na prvi element. Strogi uvjet da lista može biti praznom je taj da vrijednost njena pokazivača na prvi element jest NULL.<ref>[http://web.math.hr/~singer/P2_0910/08.pdf PMF - Matematički odjel, Zagreb] Saša Singer: Programiranje 2 - 8. predavanje, stranicama pristupljeno 14. rujna 2011.</ref>
Dakle, polja se koriste kada je riječ o skupu podataka koji se ne mijenjaju često, a vezane liste se koriste kada se veličina skupa podataka mijenja. Primjer prve situacije može biti popis učenika nekog razreda, dok primjer druge situacije može biti spremanje podataka bankovnih računa koji često mijenjaju iznos na računu.
==Primjer programa==
 
Program stvara vezanu listu za "n" cijelih brojeva:
==Implementacija u kodu ([[C++]])==
<source lang="c">
Sljedeći programski isječak prikazuje kreiranje klase koja predstavlja jednostavnu jednostruko vezanu listu (eng. Singly-linked list) te nekoliko relevantnih metoda:
#include <stdio.h>
 
#include <stdlib.h>
* 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šci (računarstvo)|predložaka]], elementi se dohvaćaju pomoću [[Iterator (računarstvo)|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.
<source lang="c++" line="1">
#include <iostream>
 
using namespace std;
class JVL // Jednostruko Vezana Lista
int main()
{
private:
struct element
struct Cvor // svaki element sadrži podatak te pokazivač na sljedeći element;
{
{ // ako sljedeći element ne postoji, "sljedeci" je nullptr
//svaki element liste sadrži podatak x i pokazivač na sljedeći element *veza
int xpodatak;
Cvor* sljedeci;
struct element *veza;
 
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;
}
 
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;
}
 
};
 
struct element *glavni=NULL; /*Glavni pokazivač na početku ima vrijednost NULL jer nema elemenata u listi.*/
int main()
struct element *clan;
int n, i;
cout<<"Broj elemenata?"; cin>>n; /*Unosimo broj elemenata liste*/
for (i=0;i<n;i++)
{
JVL lista;
clan=(struct element*) malloc (sizeof(element)); /*deklaracija člana liste*/
//zamjena pokazivačkih varijabli
for (int i = 0; i < 5; ++i)
clan->veza=glavni; /*može se zapisati i kao "(*clan).veza=glavni" */
{
glavni=clan;
lista.ubaciNaKraj(i);
cout<<"x="; /*ispisuje x*/
}
cin>>clan->x; /*može se zapisati i kao "cin>>(*clan).x", unosi vrijednost za x */
 
}
std::cout << "Ispis liste:\n";
system("pause"); /*kraj programa*/
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;
}
 
</source>
 
Dobavljeno iz "https://hr.wikipedia.org/wiki/Vezana_lista"