„Keðjulisti“: Munur á milli breytinga

Efni eytt Efni bætt við
Comp.arch (spjall | framlög)
Færi í undirkafla (og breyti smá) og færi Línuleg kaflann. Gera kvik fylki að kafla/titli undir tilbrigði? Eða færa í sér síðu?
Comp.arch (spjall | framlög)
Lína 25:
 
=== Tilbrigði við ofangreindar grunngerðir ===
"Aukakosnaðurinn"<!-- overhead, betra orð til?--> - einn (eintengdir) eða tveir (tvítengdir) bendar fyrir hvert gildi (hlekk) - er hægt að minnka að vild, þ.e. með því að hafa benda fyrir ákveðinn fjölda gilda en ekki hvert gildi. Því fleiri gildi því meiri sparnaður. Þ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 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.<!--space-time tradeoff-->