Arrays vs Linked Lists
Skikkings is die mees gebruikte datastruktuur om versameling elemente te stoor. Die meeste programmeertale verskaf metodes om skikkings maklik te verklaar en toegang tot elemente in die skikkings te verkry. Gekoppelde lys, meer presies enkelgekoppelde lys, is ook 'n datastruktuur wat gebruik kan word om versameling elemente te stoor. Dit bestaan uit 'n reeks nodusse en elke nodus het 'n verwysing na die volgende nodus in die ry.
Getoon in figuur 1, is 'n stukkie kode wat tipies gebruik word om waardes aan 'n skikking te verklaar en toe te ken. Figuur 2 beeld uit hoe 'n skikking in die geheue sal lyk.
Bostaande kode definieer 'n skikking wat 5 heelgetalle kan stoor en hulle word verkry deur indekse 0 tot 4 te gebruik. Een belangrike eienskap van 'n skikking is dat die hele skikking as 'n enkele blok geheue toegewys word en elke element kry sy eie spasie in die skikking. Sodra 'n skikking gedefinieer is, is die grootte daarvan vas. As jy dus nie seker is oor die grootte van die skikking tydens samestelling nie, sal jy 'n groot genoeg skikking moet definieer om in die veilige kant te wees. Maar die meeste van die tyd gaan ons eintlik minder elemente gebruik as wat ons toegewys het. So 'n aansienlike hoeveelheid geheue word eintlik vermors. Aan die ander kant as die "groot genoeg skikking" nie eintlik groot genoeg is nie, sal die program ineenstort.
'n Gekoppelde lys allokeer geheue afsonderlik aan sy elemente in sy eie blok geheue en die algehele struktuur word verkry deur hierdie elemente as skakels in 'n ketting te koppel. Elke element in 'n gekoppelde lys het twee velde soos getoon in Figuur 3. Die dataveld bevat die werklike data wat gestoor is en die volgende veld bevat die verwysing na die volgende element in die ketting. Die eerste element van die gekoppelde lys word gestoor as die hoof van die gekoppelde lys.
| data | volgende |
Figuur 3: Element van 'n gekoppelde lys
Figuur 4 beeld 'n gekoppelde lys met drie elemente uit. Elke element stoor sy data en alle elemente behalwe die laaste een stoor 'n verwysing na die volgende element. Laaste element hou 'n nulwaarde in sy volgende veld. Enige element in die lys kan verkry word deur by die kop te begin en die volgende wyser te volg totdat jy aan die vereiste element voldoen.
Al is die skikkings en gekoppelde lyste soortgelyk in die sin dat beide van hulle gebruik word om versameling elemente te stoor, het hulle verskille as gevolg van die strategieë wat hulle gebruik om geheue aan sy elemente toe te ken. Skikkings ken geheue toe aan al sy elemente as 'n enkele blok en die grootte van die skikking moet tydens looptyd bepaal word. Dit sal die skikkings ondoeltreffend maak in situasies waar jy nie weet wat die grootte van die skikking is tydens samestelling nie. Aangesien 'n gekoppelde lys geheue afsonderlik aan sy elemente toeken, sal dit baie doeltreffend wees in situasies waarin jy nie weet wat die grootte van die lys is tydens samestelling nie. Verklaring en toegang tot elemente in 'n gekoppelde lys sal nie reguit wees in vergelyking met hoe jy direk toegang tot elemente in 'n skikking verkry deur sy indekse te gebruik nie.
