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
Stvoreno prevođenjem stranice »Linked list«
Redak 1:
'''Vezana lista''' ([[Engleski jezik|eng]]. Linked list) je promjenjiva [[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.
 
U [[Računarstvo|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 [[Podatkovna struktura|struktura podataka]] koja se sastoji od zbirke čvorova koji zajedno predstavljaju [[niz]]. U svom najosnovnijem obliku, svaki čvor sadrži: [[ Podaci (računanje) |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. <div class="center">[[null|poveznica=]] <br /><br /><br /><br /> <small>''Jednostruko vezana lista čiji čvorovi sadrže dva polja: cjelobrojnu vrijednost i vezu do sljedećeg čvora.''</small> <small>''Zadnji čvor povezan je s terminatorom koji služi za označavanje kraja popisa.''</small> </div>
<br />
== 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.
 
== Nedostaci ==
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.
 
* Koriste više memorije od nizova zbog pohrane koju koriste njihovi pokazivači .
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.
* Č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 ==
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.
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''<nowiki/>'.
==Implementacija u kodu ([[C++]])==
Sljedeći programski isječak prikazuje kreiranje klase koja predstavlja jednostavnu jednostruko vezanu listu (eng. Singly-linked list) te nekoliko relevantnih metoda:
 
"Glava" popisa je njegov prvi čvor. 'Rep' popisa može se odnositi na ostatak popisa nakon glave ili na posljednji čvor u popisu. U [[Lisp|Lispu]] i nekim izvedenim jezicima, sljedeći čvor može se nazvati "cdr" (izgovara se ''could-er''; ''[[Engleski jezik|eng.]]'') na popisu, dok se korisni teret glavnog čvora može nazvati "''car''" (eng.).
* 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
 
=== Jednostruko vezana lista ===
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.
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.
<source lang="c++" line="1">
#include <iostream>
 
=== Dvostruko vezana lista ===
class JVL // Jednostruko 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''('<nowiki/>''s''<nowiki/>') i '<nowiki/>''backwards''<nowiki/>', ili '<nowiki/>''next''<nowiki/>' i '<nowiki/>''prev''<nowiki/>'('<nowiki/>''previous''<nowiki/>').
{
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;
 
=== Višestruko vezana lista ===
Cvor(int noviPodatak)
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 stablo|AVL stabla]].
{
podatak = noviPodatak;
sljedeci = nullptr;
}
};
Cvor* glava, * pokazivac; // "pokazivac" se koristi za dohvaćanje podataka iz liste
 
=== Kružno vezane liste ===
public:
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.
JVL()
{
glava = nullptr;
pokazivac = nullptr;
}
 
U slučaju kružnog dvostruko povezanog popisa (dvostruko vezanog prstena), prvi čvor također ukazuje na posljednji čvor popisa.
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
}
}
 
=== Sentinel čvorovi ===
void ubaciNaKraj(int podatak)
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.
{
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;
}
 
=== Vezane liste u odnosu na dinamičke nizove ===
surfer->sljedeci = new Cvor(podatak); // postavi sljedeći element na novo-kreirani čvor
''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 [[Iterator (računarstvo)|iteracije]].
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
 
== Operacije s vezanim listama ==
Cvor* surfer = glava;
while (surfer->podatak != relevantniPodatak) // dok se ne dođe do željenog čvora
{
surfer = surfer->sljedeci;
}
 
==== Jednostruko vezane liste ====
Cvor* referenca = surfer->sljedeci; // sačuvaj referencu na sljedeći element
[[Datoteka:CPT-LinkedLists-addingnode.svg|središte]]
surfer->sljedeci = new Cvor(noviPodatak); // nakon ove naredbe lista nije povezana, moguće curenje memorije
Ubacivanje novih čvorova u jednostruko vezanu listu
surfer->sljedeci->sljedeci = referenca; // poveži lanac
[[Datoteka:CPT-LinkedLists-deletingnode.svg|središte]]
Brisanje čvorova iz jednostruko vezane liste
 
== Jezična podrška ==
/* Primjer:
Mnogi [[Programski jezik|programski jezici]] kao što su [[Lisp]] i [[Scheme]] imaju ugrađene pojedinačno povezane popise.
- 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
*/
}
}
 
== Povezane strukture podataka ==
bool sadrzi(int podatak)
I [[stog]] i [[Red (struktura podataka)|redovi]] redovno se implementiraju pomoću vezanih listâ te jednostavno ograničavaju vrstu podržanih operacija.
{
Cvor* surfer = glava;
while (surfer != nullptr)
{
if (surfer->podatak == podatak)
return true;
surfer = surfer->sljedeci;
}
return false;
}
 
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.
// Slijede metode pomoću kojih korisnik može dohvatiti podatke:
 
[[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.
void idiDalje()
{
if (pokazivac == nullptr)
{
pokazivac = glava;
}
else if (pokazivac->sljedeci == nullptr)
{
std::cout << "Sljedeci element ne postoji\n";
}
else
{
pokazivac = pokazivac->sljedeci;
}
}
 
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.
void postaviPokazivacNaPocetak()
{
pokazivac = glava;
}
 
[[Hash tablica]] može koristiti povezane popise za spremanje lanaca stavki koje su hash na isti položaj u hash tablici.
bool postojiSljedeci()
{
if (pokazivac == nullptr) // pokazivac prethodno nije koristen
{
return glava != nullptr; // ne postoji niti jedan element u listi
}
else
{
return pokazivac->sljedeci != nullptr;
}
}
 
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.
int dohvatiPodatak()
{
if (pokazivac == nullptr)
{
std::cout << "Podatak ne postoji!\n";
return -1;
}
return pokazivac->podatak;
}
 
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.
};
[[Kategorija:Stranice s nepregledanim prijevodima]]
 
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;
}
 
</source>
 
 
== Izvor ==
{{izvori}}
 
{{mrva-rač}}
 
[[Kategorija:Računarstvo]]
Dobavljeno iz "https://hr.wikipedia.org/wiki/Vezana_lista"