Keðjulisti

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita
Gagnagrindur

Tengdur listi eða keðjulisti[1] er, í tölvunarfræði, gagnagrind sem einkennist af því að hver hnútur í listanum hefur gildi, og bendi á annan hnút.

Helstu gerðir af listum[breyta]

Eintengdir listar[breyta]

Eintengdur listi.

Eintengdir listar, eða einfaldlega tengdir listar eru listar, þar sem hver hnútur hefur einungis einn bendi sem bendir á næsta hnút á eftir. Þetta eru algengustu og einföldustu tengdu listarnir.

Tvítengdir listar[breyta]

Tvítengdur listi.

Tvítengdir listar hafa tvo benda og bendir annar á næsta hnút á eftir og hinn bendir á næsta hnút á undan. Þannig má fara í báðar áttir eftir listanum.

Línulega tengdir listar[breyta]

Línulega tengdur listi er almennt heiti á lista þar sem eru bæði fyrsti hnútur og aftasti hnútur; bæði eintengdir og tvítengdir listar eru línulega tengdir. Aftasti hnúturinn bendir ekki á neitt, og er því núllbendir og sömuleiðis er enginn hnútur "á undan" fyrsta hnút.

Hringtengdur listi[breyta]

Hringtengdur listi.

Hringtengdur listi er listi þar sem allir hnútarnir í listanum tengjast í hring. Hann getur verið tvítengdur eða eintengdur. Enginn hnútur í slíkum lista hefur núllbendi og allir hnútar búa yfir þeim eiginleika að til sé annar hnútur sem bendir á hann. Breyta má línulega tengdum lista í hringtengdan lista með því að tengja saman fyrsta og aftasta hnútinn.

Fjöltengdur listi[breyta]

Fjöltengdur listi er listi þar sem að hver hnútur vísar á fleiri en einn hnút. Fjöltengdir listar eru oft notaðir til þess að geyma tré. Fjöltengdur listi getur verið skilgreindur á ýmsa vegu, en oftast eru þeir einfaldlega samsetningar af öðrum tegundum tengdra lista. Til dæmis gæti fjöltengdur listi verið í grunninn hringtengdur listi, nema að hver hnútur hefur að auki tilvísun línulega tengdan lista.

Tengt efni[breyta]

Tilvísanir[breyta]