Arrays kundër listave të lidhura
Arrayet janë struktura më e përdorur e të dhënave për të ruajtur koleksionin e elementeve. Shumica e gjuhëve të programimit ofrojnë metoda për të deklaruar lehtësisht vargjet dhe aksesin e elementeve në vargje. Lista e lidhur, më saktë lista me një lidhje të vetme, është gjithashtu një strukturë të dhënash që mund të përdoret për të ruajtur koleksionin e elementeve. Ai përbëhet nga një sekuencë nyjesh dhe secila nyje ka një referencë për nyjen tjetër në sekuencë.
Treguar në figurën 1, është një pjesë e kodit që përdoret zakonisht për të deklaruar dhe caktuar vlera në një grup. Figura 2 përshkruan se si do të dukej një grup në memorie.
Kodi i mësipërm përcakton një grup që mund të ruajë 5 numra të plotë dhe ato aksesohen duke përdorur indekset nga 0 deri në 4. Një veti e rëndësishme e një grupi është se i gjithë grupi ndahet si një bllok i vetëm memorie dhe çdo element merr hapësirën e vet në grup. Pasi të përcaktohet një grup, madhësia e tij fiksohet. Pra, nëse nuk jeni të sigurt për madhësinë e grupit në kohën e përpilimit, do t'ju duhet të përcaktoni një grup mjaft të madh për të qenë në anën e sigurt. Por, në shumicën e rasteve ne në fakt do të përdorim më pak elementë sesa kemi ndarë. Pra, një sasi e konsiderueshme memorie është në të vërtetë e humbur. Nga ana tjetër, nëse "vargu mjaft i madh" nuk është në fakt mjaft i madh, programi do të rrëzohej.
Një listë e lidhur shpërndan memorie elementeve të saj veçmas në bllokun e vet të memories dhe struktura e përgjithshme merret duke i lidhur këta elementë si lidhje në një zinxhir. Çdo element në një listë të lidhur ka dy fusha siç tregohet në figurën 3. Fusha e të dhënave mban të dhënat aktuale të ruajtura dhe fusha tjetër mban referencën për elementin tjetër në zinxhir. Elementi i parë i listës së lidhur ruhet si kreu i listës së lidhur.
| të dhëna | tjetër |
Figura 3: Elementi i një liste të lidhur
Figura 4 përshkruan një listë të lidhur me tre elementë. Çdo element ruan të dhënat e tij dhe të gjithë elementët përveç atij të fundit ruajnë një referencë për elementin tjetër. Elementi i fundit mban një vlerë null në fushën e tij të ardhshme. Çdo element në listë mund të aksesohet duke filluar në krye dhe duke ndjekur treguesin tjetër derisa të plotësoni elementin e kërkuar.
Edhe pse vargjet dhe listat e lidhura janë të ngjashme në kuptimin që të dyja përdoren për të ruajtur koleksionin e elementeve, ato kanë dallime për shkak të strategjive që përdorin për të shpërndarë memorien tek elementët e saj. Vargjet shpërndajnë memorie për të gjithë elementët e tij si një bllok i vetëm dhe madhësia e grupit duhet të përcaktohet në kohën e ekzekutimit. Kjo do t'i bënte vargjet joefikase në situatat kur nuk e dini madhësinë e grupit në kohën e përpilimit. Meqenëse një listë e lidhur shpërndan memorie për elementët e saj veçmas, do të ishte shumë efikase në situatat në të cilat nuk e dini madhësinë e listës në kohën e përpilimit. Deklarimi dhe qasja e elementeve në një listë të lidhur nuk do të ishte e drejtpërdrejtë në krahasim me mënyrën se si ju aksesoni drejtpërdrejt elementët në një grup duke përdorur indekset e tij.
