Povezana struktura podataka

U informatici povezana struktura podataka je struktura podataka koja se sastoji od skupa podataka (čvorova) međusobno povezanih i organizovanih pomoću referenci (veza ili pokazivača). Veza između podataka se može nazvati i konektor.

U povezanim strukturama podataka, veze se uobičajeno posmatraju kao posebni tip podataka koji može biti samo dereferenciran ili upoređen za jednakost. Povezane strukture podataka su samim tim u kontrastu sa nizovima i ostalim strukturama podataka koje zahtevaju izvođenje aritmetičkih operacija nad pokazivačima. Ova razlika važi čak i kada su čvorovi implementirani kao elementi jednog niza i reference su zapravo indeksi niza, sve dok se nikakva aritmetika ne obavi nad tim indeksima, struktura podataka je u suštini jedna od povezanih.

Povezivanje može biti obavljeno na dva načina: korišćenjen dinamičke alokacije i korišćenjem povezivanja indeksa niza.

Povezane strukture podataka uključuju povezane liste, stabla pretrage, izraze u formi binarnog stabla i mnoge druge često korišćene strukture podataka. One su takođe ključni gradivni blokovi za mnoge efikasne algoritme kao što su: topološko sortiranje i nalaženje unije skupova.

Česti tipovi povezanih struktura podataka

Povezane liste

Povezana lista je kolekcija struktura poređana ne po njihovom fizičkom odredištu u memoriji, već po logičkim vezama koje su skladištene kao deo podatka same strukture. Za njih nije neophodno da budu smeštene u susednim memorijskim lokacijama. Svaka struktura ima svoje polje sa podacima i adresno polje. Adresno polje sadrži adresu svog sledbenika.

Povezane liste mogu biti jednostruko, dvostruko ili višestruko povezane i mogu biti ili linearne ili kružne.

Osnovna svojstva

• Objekti, zvani čvorovi, su povezani u linearnoj sekvenci
• Referenca na prvi čvor liste se uvek pamti. Ona se zove 'glava' ili 'početak'.

Povezana lista sa tri čvora od kojih svaki ima dva polja: jedno za celobrojnu vrednost i jedno za vezu ka sledećem čvoru

Povezana lista sa jednim čvorom.

Primer u Javi

Primer klase čvora korišćen za čuvanje celobrojne vrednosti u Java implementaciji povezane liste.

public class IntCvor {
     public int vrednost;
     public IntCvor sledeci;
     public IntCvor(int v) { vrednost = v; }
}

Primer u C-u

Primer strukture čvor iskorišćen za implementaciju povezane liste u C-u.

struct cvor
{
	int vrednost;
	struct cvor *sledeci;
};

Primer sa ključnom rečju typedef.

typedef struct cvor_s cvor;

struct cvor_s
{
	int	vrednost;
	cvor	*sledeci;
};

Napomena: Strukture kao ove koje u sebi sadrže član koji pokazuje na istu strukturu se zovu samoreferentne strukture.

Primer u C++-u

Primer klase čvor iskorišćen za implementaciju povezane liste u C++-u.

class Cvor
{
	int vrednost
	Cvor *sledeci;
};

Stablo pretrage

Stablo pretrage je tip strukture podataka stabla u čije čvorove se mogu smestiti vrednosti iz nekog uređenog skupa tako da se pri inorder obilasku tog stabla dobije uzlazni niz upisanih vrednosti.

Osnovna svojstva

• Objekti, zvani čvorovi, su smešteni u uređenom skupu.
• Inorder obilaskom se dobija uzlazni niz vrednosti iz stabla.
• Podstabla nekog stabla su takođe stabla.

Prednosti i mane

Povezane liste nasuprot nizovima

U poređenju sa nizovima, povezane liste su fleksibilnije u organizaciji podataka i alokaciji memorije. U nizovima veličina niza mora biti precizno zadata na početku što može dovesti po potencijalnog trošenja memorije. Povezana struktura podataka se gradi dinamički i nikada ne mora biti veća od zahteva programera. Takođe ne zahteva nagađanje po pitanju koliko memorije mora biti alocirano kada se koristi povezana struktura podataka. Ovo je ključna osobina za štednju memorije.

U nizu elementi moraju biti u susednim (povezanim i sekvencijalnim) delovima memorije, dok kod povezanih struktura podataka referenca za svaki čvor daje korisniku potrebnu informaciju da pronađe sledeći element. Čvorovi povezane strukture podataka se takođe mogu individualno premestiti na drugu lokaciju bez uticanja na međusobne logičke veze za razliku od nizova. Uz određenu brigu, jedan proces može dodati ili obrisati čvorove na jednom delu strukture čak i dok drugi procesi rade nad ostalim delovima.

Sa druge strane, pristup određenom čvoru u povezanoj strukturi podataka zahteva praćenje niza referenci koje su smeštene u njoj. Ako struktura ima n čvorova i svaki čvor sadrži najviše b veza, onda će postojati čvorovi do kojih se ne može doći u manje od log_b n koraka. Za mnoge strukture neki čvorovi u najgorem slučaju zahtevaju i do n−1 koraka. U kontrastu, mnogi tipovi nizova pružaju pristup bilo kom elementu u kostantnom broju operacija, nezavisno od njihove veličine.

Najširi način implementacije povezanih struktura podataka je pomoću dinamičkih struktura podataka. One nam pružaju šansu da određeni prostor ponovo iskoristimo. Memorija se može efikasnije iskoristiti korišćenjem ovih struktura podataka. Memorija se alocira po potrebi i kada više nije u upotrebi dealocira se.

Osnovne mane

Povezane strukture podataka mogu preobilnim pozivima za alokaciju memorije (ako se čvorovi alociraju individualno) izazvati usporenje kod straničenja memorije i keširanja procesa. U nekim slučajevima povezane strukture podataka mogu zauzeti više memorije nego nizovne strukture zbog dodatnog polja za vezu (referencu na sledeći element). Istance podataka se mogu naći na raznoraznim mestima u memoriji za razliku od nizova.

U nizu n-tom elementu se može odmah pristupiti dok kod povezanih struktura podataka moramo pratiti više pokazivača zbog čega vreme pristupa varira u zavisnosti pozicije elementa u strukturi.

Vidi još

• Struktura podataka
• Povezana lista