Što je struktura povezanih podataka?

Povezana struktura podataka je zbirka podataka raspoređenih u formatu poput popisa. Svaki dio podatka na popisu naziva se čvorom. Svaki čvor je povezan sa sljedećim na popisu referencom na memorijsku adresu tog sljedećeg čvora. Povezane strukture podataka koriste se umjesto niza kada je broj čvorova na popisu nepoznat ili se može povećati ili smanjiti tijekom izvršavanje programa.Najčešći tip povezane strukture podataka naziva se povezana lista.

Čvor povezane strukture podataka općenito sadrži dvije informacije – referencu na stvarne podatke koji se pohranjuju i referencu na sljedeći čvor na popisu. Povezani popis prelazi se ili pretražuje korakom kroz svaki od podatkovnih čvorova, počevši od prvog, ili na čelu popisa.Ne postoji način da pronađete informacije u povezanom popisu bez uzastopnog kretanja kroz čvorove od početka do kraja.

Većina povezanih struktura podataka koristit će što je moguće manje memorije tijekom izvođenja programa. Ako je povezana lista stvorena sa samo jednim čvorom i nije dodan nijedan drugi čvor, taj će popis zauzeti memorija potrebna samo za jedan čvor. Ovo je u potpunoj suprotnosti sa strukturom podataka niza u kojoj se veličina cijelog niza mora deklarirati i dodijeliti na početku programa i ne može se mijenjati .

Povezani popisi plaćaju za učinkovito korištenje memorijskih resursa zahtijevajući više računalne snage. Pronalaženje određenog podatka na povezanom popisu zahtijeva svaki put petlju kroz cijeli popis, tako da može biti sporije pristupiti informacijama u u sredini popisa.. Uklanjanje ili preuređivanje podataka u povezanom popisu također može biti računski intenzivnije od upravljanja nizom u kojem se elementi mogu lako mijenjati.

Povezana struktura podataka ne mora imati samo jednu referencu na sljedeći čvor; može imati nekoliko. Neki povezani popisi imaju dvije reference čvora, jednu na sljedeći čvor na popisu i jednu na prethodni čvor. To su poznate kao dvostruko povezane liste. To može učiniti kretanje kroz listajte u oba smjera mnogo brže, iako na račun povećane upotrebe memorije za strukturu podataka.

Moguće je da povezani popisi imaju tri ili više referenci na druge čvorove na popisu. Ovo stvara strukturu sličnu stablu s cijelim granama čvorova koji se pokreću iz jednog. Ove vrste podataka strukture se nazivaju višestruko povezane liste. Višestruko povezane liste su osobito korisne za složene algoritme razvrstavanja koji se koriste za strukturiranje podataka. Stabla pretraživanja moguća su uglavnom zbog upotrebe povezanih struktura podataka za stvaranje više grana promjenjive duljine.