Keðjulisti
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 | breyta frumkóða]Línulega tengdir listar
[breyta | breyta frumkóða]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.
Eintengdir listar
[breyta | breyta frumkóða]
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 | breyta frumkóða]
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.
Hringtengdur listi
[breyta | breyta frumkóða]
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 | breyta frumkóða]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.
Umfjöllun og tilbrigði við ofangreindar grunngerðir
[breyta | breyta frumkóða]Í eintengdum lista eru hefðbundið einn bendir á hlekk (en fram/aftur bendapar fyrir tvítengda lista). En hvert gildi þarf ekki endilega sér hlekk. Þessi aukaminnisnotkun sem listar kalla á (umfram fylki) fyrir hvert gildi er hægt að minnka að vild, með því hafa bendi (eða par) fyrir ákveðinn fjölda gilda en ekki hvert gildi (í raun lista af fylkum gilda í stað lista stakra). Því fleiri gildi í hlekk því færri hlekkir og meiri minnisparnaður fyrir bendana. Þetta eru s.k. kvik fylki (e. dynamically allocated array), ATH ekki kvik frátekin fylki (e. dynamically allocated array). (Líka er einfaldlega hægt að sleppa bendum alveg og nota hefðbundin fylki ef minniskostnaður væri eina málið.) Kvik fylki hafa flesta kosti almennra fylka og lítið af göllum þeirra (en uppbyggingu og forritskóða bæði lista og fylkja). Þ.e. hægt er að bæta við gildum (hvar og hvernig fer eftir nákvæmri útfærslu) án hefðbundinna takmarkanna fylkja. Kostir fylkja eru t.d. hraðasti aðgangur að hvaða staki sem er (og breyting staka en ekki eyðing eða viðbót t.d. milli tveggja sem er kostur lista), og vegna skyndiminnis, að næsta gildis á undan (eða eftir). Kvik fylki nálgast hraða í uppflettingu án sumra galla þeirra. Listar hafa hins vegnar almennt hægastan aðgang að gildum (nema fínan fyrir fyrsta) og næstu gildi sem bendar vísa á því skyndimynni virka best þegar gildi eru samliggjandi í minni (og síst fyrir hefðbundna lista (atriði sem er undanskilið í hefðbundinni flækjustigsgreiningu sem tölvunarfræði hefur notað til að áætla "hraða" algóritma/gagnagrinda). Í raun er aðgangur að fyrra gildi flókinn/hægur nema um tvítengdan lista er að ræða - en þá álíka hraður og í eintengdum.
Alls konar fleiri afbrigði af listum eru til og jafnvel er hægt að blanda þeim saman. T.d. er til almennt trikk fyrir alla tvítengda lista til að komast af með pláss eins bendis fyrir hvert framm/aftur par benda með því að geyma þá XOR-aða saman. Það trikk er ekki ráðlagt í þeim forritunarmálum, eins og C/C++, sem leyfa það en ekki hafa almennt ruslasöfnun í þeim tilvikum að henni er bætti við því hún ræður almennt ekki við það. Eins fylgja aðrir gallar eins og með allar fljóknari aðgerðir.