„Keðjulisti“: Munur á milli breytinga
Efni eytt Efni bætt við
m Bot: Flyt 1 tungumálatengla, sem eru núna sóttir frá Wikidata á d:Q7003418 |
Skrifað í flýti eftir minni, má eflaust laga.. |
||
Lína 1:
{{gagnagrindur}}
'''Tengdur listi''' eða '''keðjulisti'''<ref>[http://tos.sky.is/tos/to/word/isl/2858/ '''keðjulisti''' ''kk.'' Listi með stökum sem geta verið dreifð um geymslu en fela í sér upplýsingar til þess að finna næsta stak á eftir í listanum.] á [[Tölvuorðasafnið|Tölvuorðasafninu]]</ref> er, í [[tölvunarfræði]], [[gagnagrind]] sem einkennist af því að hver [[hnútur (netafræði)|hnútur]] í listanum hefur gildi, og [[bendir (tölvunarfræði)|bendi]] á annan hnút.
Í tvítengdum lista þarf almennt séð tvo benda, einn í sitt hvora átt.
Þessi "aukakosnaður"<!-- overhead, betra orð til?--> - einn eða tveir bendar fyrir hvert gildi - er hægt að minnka að vild, þ.e. með því að hafa fyrir t.d. hver tvö, þrjú eða fjögur gildi o.s.frv. benda en ekki hvert gildi. Þetta eru s.k. [[kvikt fylki|kvik fylk]]. (Eins er hægt að sleppa bendum alveg og nota hefðbundin [[Fylki (tölvunarfræði)|fylki]].) Kvik fylki hafa flesta kosti almennra fylka og lítið af göllunum (og uppbyggingu beggja). Þ.e. hægt er að bæta (alla vega aftan við) án þess endurúthluta öllu minni upp á nýtt. Kostir fylkja er hraður aðgangur að hvaða staki sem er og vegna [[skyndiminni]s <!--og localities of reference--> næsta gildis á undan (eða eftir). Listar hafa aldrei eins hraðan aðgang vegna skyndiminnis í næsta gildi (gögn ekki samhangandi í minni sem skipir máli en undanskilið í hefðbundinni fræðilegri greiningu). Í 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.
Alls konar fleiri afbrigði af listum eru til se, jafnvel er hægt að blanda saman. T.d. er til er trikk til að komast af með pláss eins bendis í stað tveggja í þvítengdum listum með því að geyma fram og aftur-bendana 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.<!--space-time tradeoff-->
== Helstu gerðir af listum ==
=== Eintengdir listar ===
[[Mynd:Single linked list.png|250px|thumb|Eintengdur listi.]]
| |||