C++ mums atļauj izveidot statiskus un dinamiskus masīvus, bet ar viņiem ir neliela problēma. Iedomāsimies, ka mums ir skaitļu masīvs garumā 10. Pēc kāda laiciņa mēs viņu, protams, izmantojam, un ja mums vajag pievienot beigās 11. skaitli mums viss masīvs ir jādefinē no jauna. Jāizvēlas lielāks izmērs un tajā jāieraksta visas iepriekšējā masīva vērtības. Pienāks arī laiks, kad mēs gribēsim skaitli iespraust kaut kur pa vidu vai sākumā, tad mums būtu jāpārbīda visi skaitļi uz priekšu, lai atbrīvotu vietu jaunajam skaitlim.

Šīs problēmas pazūd, ja mēs izmantojam saistīto sarakstu. Bet pirms es kaut ko par to stāstu, papētīsim, kāpēc viņš vispār strādā. Līdzko mēs definējam jaunu objektu, programma atrod tuvāko brīvo vietiņu operatīvajā atmiņā. Atmiņa sastāv no ļoti daudz maziem klucīšiem - baitiem. Viņi tā arī numurējās no 0 līdz [skaitlis, kas atkarīgs no operatīvas atmiņas izmēra]. Un kaut kur šajā baitu virknē tiek ievietots objekts, lai izmantotu šo pozīciju, tikai ieviests pointer apzīmējums - *. Bet mēs šo varam uztvert kā norādi.

int a = 10;
int *p = &a;
*p = 20; cout << a;
  1. rindiņā mēs definējam jaunu skaitļu mainīgo a un piešķiram viņam vērtību 10.
  2. rindiņā izveidojam jaunu norādi, kas glabās adresi uz manīgo a. Lai mēs iegūtu adresi, kurā atrodas mainīgais, izmanto & pirms mainīgā. Tas piešķir mūsu norādei adresi uz a.
  3. rindā mēs izmantojam *, to var interpretēt kā “vērtība, kura atrodas” un šajā adresē ierakstam 20, programma šo uztvers, ka šī vērtība ir jāieraksta adresē, ko norāda p, ja mēs neizmantotu *, tad programma to uztvertu, ka vērtība ir jāieraksta p. Pēdējā rindiņā mēs izvadam a. Rezultātā tiks izvadīts 20, jo tur, kur atrodas a, atmiņā ir ierakstīts 20.
  4. Tad, kad esam apguvuši nedaudz par dinamisko atmiņu, saistītajam sarakstam mums būs nepieciešama “struktūra”, kas principā ir tāda kā kaste ar dažādiem mainīgajiem, un katram no viņiem var būt dažādi datu tipi.
struct elements { 
    int vertiba;
    elements *nakoshais;
};

Šeit mēs izveidojam struktūru ar nosaukumu elements, struktūras izmanto tieši tāpat kā datu tipus (int, char,…) elements *sakums; šī struktūra sastāvēs no diviem mainīgajiem - vērtība, kurā glabāsies skaitlis un norāde - nakoshais, kas norādīs, kur atmiņā atrodas nākošais elements. Ja nākošā elementa nav, tad norāde norāda uz tukšumu - NULL. Programmiņa, kas izmanto mūsu jaunizveidoto struktūru. Visbeidzot no daudzām viena tipa struktūrām mēs varam izveidot saistītu sistēmu. Kuru nosauksim par saistīto sarakstu. Pastāv vairāku veidu saistītie saraksti (vienvirziena, divvirzienu, un citi, kurus neminēšu, lai nejauktu galvu :) ) Mēs apskatīsim vienkāršāko vienvirziena sarakstu. Mans ieteikums saistīto sarakstu veidot kā klasi.

class SaistitaisSaraksts {
    struct elements {
        int vertiba;
        elements *nakoshais;
    };

    elements *sakums, *beigas;
public: 
    SaistitaisSaraksts() {
        sakums = NULL;
        beigas = sakums;
    };

    ~SaistitaisSaraksts();
    void Pievienot(int skaitlis);
    void Drukat();
};

Tā varētu izskatīties saistītā saraksta klase. Izmantojot klasi, mums būs grūtāk kaut ko nejauši sabojāt, ja mēs gribētu izmantot daudzus saistītos sarakstus. Klasē glabāsies divas norādes uz sākuma un beigu elementiem. Tad vēl mums nepieciešams konstruktors, kas piešķir NULL sakuma un beigu norādēm, jo, izveidojot sarakstu, sākumā tas nesaturēs nevienu elementu. Tad vēl nepieciešamas funkcijas, kas pievienotu sarakstam jaunu elementu, un vēl funkcija, kas izvadīs visus sarakstā esošos skaitļus. Sāksim ar skaitļa pievienošanu sarakstam:

void SaistitaisSaraksts::Pievienot(int skaitlis) {
    //liekam izveidot jaunu bloku kaut kur atmiņā elements
    *b = new elements();    
    b->vertiba = skaitlis;
    b->nakoshais = NULL;
    
    //ja pirmais elements ir NULL tad saraktā vēl nav neviena elementa 
    if (sakums == NULL) 
        sakums = b;
        //sakums būs jaunais elements 
    else 
        //pēdējais elements norādīs uz jaunizveidoto bloku 
        beigas->nakoshais = b;

    beigas = b;
    //beigas tagad norādīs uz jauno elementu, jo viņš ir pēdējais 
};

Īsumā, ko šī funkcija dara. Sakumā izveidojam kaut kur atmiņā jaunu elementu, un ar new palīdzību atrodam atmiņā brīvu vietu elementam, tāpēc norāde b glabās adresi, kur tā vieta ir. Norādi mēs definējām ar jaunizveidotās struktūras palīdzību. Tas tāpēc, lai programma zinātu, cik daudz atvēlēt atmiņas, lai pietiktu gan skaitlim, gan norādei uz nākošo elementu un arī, lai varētu pareizi interpretēt abus mainīgos. Tad, kad tas ir izdarīts, ierakstām tajā vietā savu skaitli, bet tā kā nākošais elements neeksistē, tad nakoshais glabās NULL. Tad mums vēl ir jāpārbauda vai sākums ir NULL, ja ir, tad ar to var saprast, ka sarakstā vēl nav neviena elementa, tāpēc, piešķirot 1. elementu, sakums norāda pirmo elementu sarakstā, arī uz šo elementu sarakstā. Bet, ja mēs uzzinām, ka pirmais elements nav NULL, tas nozīmes, ka sarakstā ir vismaz viens elements, un mēs varam jauno elementu pievienot aiz pēdējā elementa. Pēdējā rindiņa funkcijā izmaina adresi uz tikko pievienoto elementu, tā kā elements tiek pievienots beigās, tad viņš automātiski kļūst par pēdējo elementu.

void SaistitaisSaraksts::Drukat() { 
    elements *i = sakums;
    while ( i != NULL ) { 
        cout &lt;&lt; i->vertiba &lt;&lt; endl;
        i=i->nakoshais;
    }
 };

Šī funkcija uzrakstīs konsolē visus sarakstā esošos skaitļus. Sākotnēji mēs izveidojam jaunu norādi i uz sakuma elementu, cikls turpinās tik ilgi, kamēr norāde nebūs NULL, kas liecinās par to, ka saraksts ir beidzies. Katra cikla atkārtošanās reize i tiek piešķirta nākošā elementa adrese. Šis ir ļoti labs piemērs, kā iegūt saraksta elementus. Īstenībā šeit slēpjas saistītā saraksta sliktā īpašība – lai iegūtu n-to elementu mums ar cikla palīdzību jāapskata elementi un jāskaita atsevišķā mainīgajā, cik elementus esam apskatījuši, kad to skaits būs vienāds ar n būsim atraduši savu n-to elementu. Pēdējā svarīgā lieta ir saistītā saraksta izdzēšana no atmiņas, lai efektīvi atbrīvotos visas izmantotās atmiņas. To mēs darīsim tieši tajā momentā, kad tiks dzēsts objekts ar tipu SaistitaisSaraksts.

SaistitaisSaraksts::~SaistitaisSaraksts() {
    while( sakums != NULL ) { 
        i = sakums->nakoshais;
        delete sakums;
        sakums = i;
    }
 }

Tātad, lai efektīvi atbrīvotu atmiņu mums jāatbrīvo atmiņa no katra elementa. Visefektīvākais algoritms ir atbrīvot atmiņu, kas tiek norādīta ar sakums norādi, un pēc tam piešķirt šai norādei nākošo saraksta elementu, katrā cikla solī tiks izdzēsts pirmais elements un tā vietā nāks nākošais saraksta elements līdz beidzot, tiekot līdz pēdējam elementam, kuram norāde uz nākošo ir NULL, tā tiek atbrīvota visa atmiņa, kuru izmantoja saistītā saraksta elementi. Vēl neliels ieskats, kā izmantot tikko izveidoto klasi.

int main() { 
    //izveidojam jaunu sarakstu ar nosaukumu "saraksts" 
    SaistitaisSaraksts *saraksts = new SaistitaisSarakts();
    //pievienojam pāris skaitļus saraksts->Pievienot(1);
    saraksts->Pievienot(2);
    saraksts->Pievienot(3);
    //izdrukājam visu sarakstu saraksts->Drukat();
    //kad zinām, ka mums saraksts vairs nav vajadzīgs delete saraksts;
    return 0;
}

Īstenībā te varētu stāstīt vēl visādas interesantas lietas, piemēram, indeksēšanu, bet to es domāju, ka spēsiet izdomāt paši, galveno ideju es pastāstīju. Veiksmi maniem kolēģiem! :)