Повезана структура података

У информатици повезана структура података је структура података која се састоји од скупа података (чворова) међусобно повезаних и организованих помоћу референци (веза или показивача). Веза између података се може назвати и конектор.

У повезаним структурама података, везе се уобичајено посматрају као посебни тип података који може бити само дереференциран или упоређен за једнакост. Повезане структуре података су самим тим у контрасту са низовима и осталим структурама података које захтевају извођење аритметичких операција над показивачима. Ова разлика важи чак и када су чворови имплементирани као елементи једног низа и референце су заправо индекси низа, све док се никаква аритметика не обави над тим индексима, структура података је у суштини једна од повезаних.

Повезивање може бити обављено на два начина: коришћењен динамичке алокације и коришћењем повезивања индекса низа.

Повезане структуре података укључују повезане листе, стабла претраге, изразе у форми бинарног стабла и многе друге често коришћене структуре података. Оне су такође кључни градивни блокови за многе ефикасне алгоритме као што су: тополошко сортирање и налажење уније скупова.

Чести типови повезаних структура података

Повезане листе

Повезана листа је колекција структура поређана не по њиховом физичком одредишту у меморији, већ по логичким везама које су складиштене као део податка саме структуре. За њих није неопходно да буду смештене у суседним меморијским локацијама. Свака структура има своје поље са подацима и адресно поље. Адресно поље садржи адресу свог следбеника.

Повезане листе могу бити једноструко, двоструко или вишеструко повезане и могу бити или линеарне или кружне.

Основна својства

• Објекти, звани чворови, су повезани у линеарној секвенци
• Референца на први чвор листе се увек памти. Она се зове 'глава' или 'почетак'.

Повезана листа са три чвора од којих сваки има два поља: једно за целобројну вредност и једно за везу ка следећем чвору

Повезана листа са једним чвором.

Пример у Јави

Пример класе чвора коришћен за чување целобројне вредности у Јава имплементацији повезане листе.

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

Пример у C-у

Пример структуре чвор искоришћен за имплементацију повезане листе у C-у.

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

Пример са кључном речју typedef.

typedef struct cvor_s cvor;

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

Напомена: Структуре као ове које у себи садрже члан који показује на исту структуру се зову самореферентне структуре.

Пример у C++-у

Пример класе чвор искоришћен за имплементацију повезане листе у C++-у.

class Cvor
{
	int vrednost
	Cvor *sledeci;
};

Стабло претраге

Стабло претраге је тип структуре података стабла у чије чворове се могу сместити вредности из неког уређеног скупа тако да се при инордер обиласку тог стабла добије узлазни низ уписаних вредности.

Основна својства

• Објекти, звани чворови, су смештени у уређеном скупу.
• Инордер обиласком се добија узлазни низ вредности из стабла.
• Подстабла неког стабла су такође стабла.

Предности и мане

Повезане листе насупрот низовима

У поређењу са низовима, повезане листе су флексибилније у организацији података и алокацији меморије. У низовима величина низа мора бити прецизно задата на почетку што може довести по потенцијалног трошења меморије. Повезана структура података се гради динамички и никада не мора бити већа од захтева програмера. Такође не захтева нагађање по питању колико меморије мора бити алоцирано када се користи повезана структура података. Ово је кључна особина за штедњу меморије.

У низу елементи морају бити у суседним (повезаним и секвенцијалним) деловима меморије, док код повезаних структура података референца за сваки чвор даје кориснику потребну информацију да пронађе следећи елемент. Чворови повезане структуре података се такође могу индивидуално преместити на другу локацију без утицања на међусобне логичке везе за разлику од низова. Уз одређену бригу, један процес може додати или обрисати чворове на једном делу структуре чак и док други процеси раде над осталим деловима.

Са друге стране, приступ одређеном чвору у повезаној структури података захтева праћење низа референци које су смештене у њој. Ако структура има n чворова и сваки чвор садржи највише b веза, онда ће постојати чворови до којих се не може доћи у мање од log_b n корака. За многе структуре неки чворови у најгорем случају захтевају и до n−1 корака. У контрасту, многи типови низова пружају приступ било ком елементу у костантном броју операција, независно од њихове величине.

Најшири начин имплементације повезаних структура података је помоћу динамичких структура података. Оне нам пружају шансу да одређени простор поново искористимо. Меморија се може ефикасније искористити коришћењем ових структура података. Меморија се алоцира по потреби и када више није у употреби деалоцира се.

Основне мане

Повезане структуре података могу преобилним позивима за алокацију меморије (ако се чворови алоцирају индивидуално) изазвати успорење код страничења меморије и кеширања процеса. У неким случајевима повезане структуре података могу заузети више меморије него низовне структуре због додатног поља за везу (референцу на следећи елемент). Истанце података се могу наћи на разноразним местима у меморији за разлику од низова.

У низу n-том елементу се може одмах приступити док код повезаних структура података морамо пратити више показивача због чега време приступа варира у зависности позиције елемента у структури.

Види још

• Структура података
• Повезана листа