http://alpha-thema-online.uv.ro

Ad_Infinitum · Administrator

Implementarea modelelor de date

Programele pentru calculatoare utilizeazã de obicei tabele de informaþii care presupun anumite relaþii structurale între datele care le compun. Aceste relaþii structurale diferenþiazã mai multe eșantioane de organizare a datelor, dintre care cele mai importante sunt: liste, arbori, mulþimi. Toate aceste modele se reprezintã în programare prin colecþii de date care, în programarea orientatã pe obiecte, se implementeazã prin clase (tipuri definite de utilizator).
Fiecare programator îºi poate defini propriile implementãri ale modelelor de date, sau poate sã foloseascã unele soiuri definite în bibliotecile sistemului, pe care le modificã în mod corespunzãtor cerinþelor aplicaþiei. În ambele situaþii, însã, este necesarã cunoaºterea modului de organizare internã a unor astfel de modele de date, precum ºi posibilitãþile de reprezentare ºi de exploatare a acestora prin intermediul claselor de colecþii, a claselor container ºi a claselor template. Reprezentarea colecþiilor de date prin intermediul claselor derivate ºi al claselor template vor fi prezentate în secþiunile 5 ºi, respectiv, 7.

Liste liniare

O listã liniarã este o secvenþã finitã de elemente de un tip dat. Secvenþa în care apar elementele este definitorie. De exemplu, lista (a1, a2,……an ) este diferitã de lista (a2, a1,…..an). De asemenea, în listã este posibil sã existe elemente cu acceaºi valoare (elemente duplicat, ceea ce în mulþimi nu este admis). Mărimea listei este datã de numãrul de elemente în listã. Modelul de listã include ºi lista vidã, care are zero elemente. Dacã lista nu este vidã, atunci ea conþine un element de început, numit capul listei (head), iar restul elementelor se numeºte coada listei (tail). Elementele listei pot fi identificate prin poziþia lor în listã, un index i, care poate avea valori 1  i  n , unde n este lungimea listei. De multe ori, (mai ales în implementãrile în limbajul C), elementele listei se indexeazã de la 0 la n-1, aºa cum sunt indexate datele în tablourile din C.
O sublistã este formatã dintr-o parte a elementelor unei liste, cu indici cuprinºi între i ºi j, (ai, ai+1,…aj) unde 1  i  j  n.
Operaþiile care se pot executa asupra listelor sunt teribil de variate: inserãri, extrageri, cãutãri, concatenãri, divizãri, sortãri. Dintre acestea, primele trei operaþii sunt operaþii fundamentale de tip dicþionar:

Operaþia de inserare constã în adãugarea unui nou element x unei liste L. Poziþia în care se poate insera noul element este oricare poziþie în listã: înaintea primului element (în aceastã situaþie se modificã capul listei), dupã ultimul element, sau între oricare douã elemente. Este admisã inserarea unui nou element care are aceeaºi valoare cu un alt element component al listei.
Operaþia de ºtergere (extragere) a unui element dintr-o listã înseamnã eliminarea unui element x dintr-o listã. Dacã în listã existã mai multe elemente cu aceeaºi valore, se specificã suplimentar care dintre acestea se eliminã.
Operaþia de cãutare (lookup) returneazã valoarea “adevãrat” dacã elementul cu valoarea x aparþine listei, ºi valoarea “false”, dacã elementul nu aparþine listei.

3.1.1Liste ordonate

Operaþia de sortare într-o listã presupune cã elementele listei apaþin unei mulþimi în care se poate defini o relaþie de ordine liniarã. Fie o listã:
L = (a, c, b, f, e, d), unde a, b, …… S
Mulþimea S cãreia în aparþin elementele listei trebuie sã fie o mulþime ordonabilã liniar. O mulþime de elemente S este ordonabilã liniar dacã ºi numai dacã:

pentru fiecare douã elemente a ºi b ale mulþimii S este îndeplinitã una din condiþiile: a < b, a = b sau a > b;
pentru oricare trei alemente a, b, c ale mulþimii S, dacã a < b ºi b < c, atunci a < c.

Simbolul “ < ” semnificã “precede”. Un exemplu de mulþime care satisface condiþiile de ordine liniarã este mulþimea numerelor întregi. Un alt exemplu este mulþimea literelor alfabetului Latin. Într-o secvenþã S = {s1, s2, ….sn} compusã din elemente care aparþin unei mulþimi ordonabile liniar, rangul k al unui element si este definit ca numãrul de elmente în S care preced elementul si plus 1.
Sortarea unei liste (secvenþã de elemente) înseamnã efectuarea unei permutãri între elementele listei, astfel încât fiecare sã respecte regula de precdenþã faþã de elementul aflat anterior lui în listã. Ca rezultat al unei operaþii de sortare în lista L rezultã lista L’ :
L’ = (a, b, c, d, e, f), unde a < b < c < d < e < f
O astfel de listã se numeºte listã ordonatã.

În programarea orientatã pe obiecte elementele unei liste sunt de un tip dat, predefinit sau definit de utilizator (clasã). Pentru tipurile de date fundamentale ale limbajului C++, relaþia de precedenþã “ < “ este definitã printr-un operator de relaþie. Pentru tipurile definite de utilizator, obiectele (instanþe ale unei clasei) dintr-o listã pot fi ordonate dacã pentru clasa respectivã se defineºte operaþia de precedenþã. În general, aceastã operaþie se defineºte prin supraîncãrcarea operatorul de relaþie “ < ”.

3.1.2Stive ºi cozi

Pe baza modelului de date listã liniarã sunt definite alte tipuri de date abstracte, cum sunt stiva (stack) ºi coada (queue), prin restricþionarea modului de execuþie a operaþiilor asupra listei.

Stiva este o listã în care toate operaþiile (de inserare ºi de extragere) au loc printr-un singur capãt al listei, care se numeºte vârful stivei (top) (Fig. 3.1-a). Datoritã faptului cã operaþiile în stivã se executã printr-un singur capãt, aceste operaþii se desfãºoarã întotdeauna în ordinea ultimul inserat, primul extras (last-in, first-out - LIFO), de unde ºi numele LIFO sub care este frecvent întâlnit acest tip de date.

Coada este o listã în care operaþiile de inserare ºi extragere au loc prin capete diverse ale listei. Operaþia de inserare se executã la sfârºitul cozii (spate, rear), în timp ce extragerea se executã din începutul (faþã, front) cozii (Fig. 3.1-b). Temenul de listã FIFO, frecvent folosit pentru coadã, provine din acest mod de execuþie: primul intrat, întâiul extras (first-in, first-out, FIFO).

Fig. 3.1 Douã tipuri de liste: stiva (a) ºi coada(b)

Modelul de date abstract listã se poate reprezenta, în principal, prin douã structuri (tipuri) de date: tablou de elemente (vector) ºi listã înlãnþuitã.

3.1.3Implementarea listelor liniare prin tablouri

În aceastã implementare elementele listei sunt memorate într-un tablo, ceea ce înseamnã cã elementele vecine în listã ocupã locaþii vecine în memorie. Implementarea prin tablouri a listelor beneficiazã de acces repede la un element într-o poziþie datã. În schimb, inserarea sau ºtergerea unui element poate necesita operaþii costisitoare de deplasare a unor elemnte pentru a face loc unuia nou (la inserare) sau pentru a le realipi, la ºtergerea unui element.
Pentru implementarea unei liste liniare se poate folosi un tablou unidimensional (vector) de elemente ca tip derivat de date, alocat static sau dinamic în memorie. De exemplu:
T vector[d];
defineºte un vector de elemente de tipul T, predefinit sau definit de utilizator (clasã) alocat static în memorie, în care se poate stoca o listã de maximum d elemente. Se poate defini ºi un vector alocat dinamic în memorie, de exemplu:
T vector = new T[d];
Numãrul de elemente n ale listei este o informaþie strict necesarã în cazul implementãrii listelor ca tablouri, deoarece dimensiunea tabloului (d) nu coincide cu numãrul de elemente ale listei, fiind în general mai mare, pentru a se asigura probabilitatea de inserare a noi elemente (Fig. 3.2).

Fig. 3.2 Implementarea ca vector a unei liste liniare.

În abordarea orientatã pe obiecte, o listã de elemente de tipul T implementatã ca vector se poate reprezenta printr-o clasã care, în general, memoreazã vectorul de date de tipul respectiv T, dimensiunea vectorului d ºi numãrul n de elemente ale listei. Funcþiile membre ale clasei modeleazã operaþiile impuse de destinaþia listei. De exemplu, pentru o clasã care reprezintã o stivã, sunt necesare operaþiile de inserare (push) ºi de extragere (pop).

Aceasta a fost modul de implementare din Exemplul 2.5 din secþiunea precedentã: clasa IntStack implementeazã o stivã de numere întregi, reprezentatã printr-un tablou (vector) alocat static în memorie, de dimensiune (MAX_SIZE) care este o constantã în program. În implementarea prin vector a stivei, operaþiile de inserare ºi de extragere a elementelor stivei (push() ºi pop()) se executã faþã de ultimul element al listei care reprezintã stiva: se insereazã un element dupã ultimul element memorat (cu indice maxim în listã) ºi se extrage ultimul element memorat. Aceastã poziþie de vârf a stivei este memoratã în clasa IntStack printr-un indice (tos). Într-o versiune similarã de stivã (cea prezentatã în subsecþiunea 7.1 ), în clasa template TStack vârful stivei este memorat printr-un pointer (top), dar aceastã diferenþã este nesemnificativã.
Cealaltã posibilitate de implementare a listelor liniare, prin alocarea dinamicã a vectorului în memoria liberã, cu o dimensiune care se stabileºte în momentul execuþiei, a fost exemplificat în Exemplul 2.7, prin clasa DStack pentru o stivã de numere întregi.
Ambele versiuni, întrebuințând vectori de date de mărimi fixe, stabilite la compilare sau la crearea dinamicã a stivei, au dezavantajul inflexibilitãþii ºi al consumului nejustificat de memorie.
O variantã îmbunãtãþitã de implementare a unei liste prin vector alocat dinamic în memorie este propusã în Exerciþiul 2.6, prin clasa IntArray, în care măsură vectorului creºte atunci când se depãºeºte spaþiul de memorare existent la un moment dat cu o cantitate fixã (grows) stabilitã în definiþia clasei. O astfel de implementare este avantajoasã din punct de vedere al spaþiului de memorie ocupat, dar devine ineficientã ca timp de execuþie, dacã au loc operaþii frecvente de ajustare a mărimii vectorului. Pentru creºterea proporției vectorului, se alocã un nou vector în memorie, se copiazã tot conþinutul precedent ºi se elibereazã vechiul vector.

Implementarea unei cozi se poate face utilizând un vector de elemente, dar pentru accesul la ambele capete ale listei, aºa cum este necesar în structora FIFO, se aranjeazã astfel ca vectorul sã fie parcurs circular.
Vectorul de elemente are dimensiune p locaþii posibile (elemente) ºi o structurã circularã. Douã variabile memoreazã poziþia (indicele) de scriere (writer) ºi poziþia de citire din vector (reader) (Fig. 3.3).

Fig 3.3 Implementarea unei cozi printr-un vector parcurs circular

Iniþial coada este goalã, numãrul de elemente ocupate în vector (n) este egal cu zero, iar indicii de inserare ºi de extragere sunt de întocmai iniþializaþi cu valoarea 0. Un element se insereazã în vector în poziþia (indicele) writer, dupã care acesta este incrementat circular: writer = (writer+1)%d; ºi de asemenea este incrementat numãrul n de elemente ale listei. Dacã lista nu este vidã (dacã n > 0) se poate extrage un element din vector de la adresa reader, dupã care acest indice este incrementat circular: reader = (reader+1)%d; iar numãrul de elemente n este decrementat. Operaþia de inserare trebuie sã fie permisã numai dacã mai existã poziþii libere în vector (dacã n < d). Operaþia de extragere trebuie sã fie permisã numai dacã existã cel puþin un element în vector (n > 0).

Listele, împreunã cu ale modele de date (cum sunt mulþimile sau arborii) sunt în general denumite ºi colecþii de date, deoarece conþin mai numeroase elemente de acelaºi tip, cu o anumite relaþii între ele.

3.1.4Implementarea colecþiilor de date prin liste înlãnþuite

O listã liniarã ca model de date abstract (secvenþã finitã de elemente de acelaºi tip) se poate implementa ºi printr-o structurã de date de tip listã modest sau dublu înlãnþuitã.
O listã necomplicat înlãnþuitã este o schemã de implementare a colecþiilor de elemente în care fiecare nod al listei este compus din douã câmpuri: un câmp conþine un element al colecþiei, de un tip dat, iar celãlalt câmp conþine un pointer cãtre urmãtorul nod al listei (Fig. 3.3-a).
O listã dublu înlãnþuitã este compusã din noduri, fiecare nod având trei câmpuri: un câmp conþine un element al colecþiei, al doilea câmp conþine un pointer cãtre urmãtorul nod al listei, iar al treilea câmp conþine un pointer cãtre nodul precedent al listei (Fig. 3.3-b). În reprezentarea obiºnuitã a listelor înlãnþuite, pointerii se reprezintã prin sãgeþi cãtre nodurile vecine, valoarea efectivã a acestora (adresa din memorie a nodului) fiind de obicei nesemnificativã. Pointerii de înlãnþuire au valoarea 0 pentru nodurile terminale ºi în reprezentãrile grafice sunt marcaþi printr-un punct sau o legãturã la masã (“împãmântare”) În lista simplu înlãnþuitã, ultimul nod este nod terminal ºi are pointerul cãtre nodul urmãtor 0. În lista dublu înlãnþuitã primul nod are pointerul cãtre nodul precedent 0, iar ultimul nod are pointerul cãtre urmãtorul nod 0.

În listele înlãnþuite elementele succesive nu ocupã, în general, în locaþii succesive în memorie. Fiecare nod se alocã dinamic în memoria liberã, iar câmpurile de înlãnþuire (pointerii) se poziþioneazã astfel încât sã se asigure înlãnþuirea corectã a nodurilor. Listele înlãnþuite oferã avantajul cã pot reprezenta colecþii cu numãr variabil de elemente, fãrã sã se ocupe un spaþiu suplimentar în memorie (cu excepþia spaþiului de memorare a pointerilor). De asemenrea, operaþiile de inserare ºi de extragere a elementelor sunt mai simple, implicând numai modificãri de valori ale pointerilor, ºi nu deplasãri ale elementelor (aºa cum se poate întâmpla în cazul utilizãrii vectorilor).
Principalul dezavantaj al listelor înlãnþuite îl reprezintã timpul mare ºi variabil de cãutare al unui element dat în listã, dar chiar ºi aºa, listele înlãnþuite sunt frecvent utilizate în programare.

Reprezentarea listelor înlãnþuite este posibilã în orice limbaj procedural, prin definirea structurilor compuse din câmpurile corespunzãtoare (elementul listei ºi pointerii la noduri vecine).
În modelarea orientatã pe obiecte a listelor înlãnþuite se pot folosi una sau mai multe clase, în funcþie de destinaþia listei respective. În orice situaþie va exista o clasã care va modela un nod al listei, având ca date membre un element al colecþiei de date (sau un pointer cãtre acesta) ºi pointerul sau pointerii de înlãnþuire.
Se poate ca o listã înlãnþuitã sã fie reprezentatã numai printr-o astfel de clasã. În Exerciþiul 3.1 este propusã o astfel de rerprezentare a unei liste simplu înlãnþuite. Nodurile se înlãnþuie între ele, iar lista se indicã printr-un pointer la debutantul sãu nod. Dacã se analizazã o astfel de reprezentare se pot observa distincte anomalii în operaþiile efectute asupra listei. În inițialul rând, o operaþia asupra primului nod (ca, de exemplu eliminarea primului nod) modificã lista însãºi, adicã pointerul la primul nod al înlãnþuirii prin care se cunoaºte lista. Mai sunt ºi alte anomalii în reprezentarea listelor înlãnþuite folosind o singurã clasã (tip de date). Astea sunt evidenþiate în Exerciþiul 3.1.

O reprezentare mai completã a unei liste înlãnþuite se poate face prin douã feluri de date (clase): o clasã reprezintã un nod al listei ºi o altã clasã reprezintã lista însãºi; în subsecþiunile care urmeazã sunt descrise astfel de reprezentãri ale listelor rudimentar ºi dublu înlãnþuite de numere întregi.

3.1.4.1Listã simplu înlãnþuitã de numere întregi

Se definesc douã clase pentru reprezentarea unei liste simplu înlãnþuite de numere întregi: o clasã IntSListNode pentru reprezentarea unui nod al listei ºi o clasã IntSList, pentru reprezentarea listei. În clasa IntSListNode este memorat elementul listei (un numãr întreg, variabila int v) ºi pointerul link la nodul urmãtor. În clasa IntSList este memorat pointerul la primul nod al listei (first), pointerul la ultimul nod al listei (last) ºi numãrul de elemente ale listei (count). Memorarea ultimului nod al listei (last) ºi al numãrului de elemente (count) nu sunt strict necesare, fiindcă ele pot fi calculate de fiecare datã pornind de la primul nod. Dar aceste operaþii parcurg secvenþial întreaga listã, ceea ce reprezintã un consum de timp de care poate fi considerabil pentru listele de dimensiuni mari ºi de aceea memorarea acestor variabile în clasa IntSList mãresc eficienþa de execuþie a operaþiilor cu listele simplu înlãnþuite.
Pentru fiecare clasã s-au definit constructori, destructor ºi funcþii membre care implementeazã operaþii asupra listei. Clasa IntSList este declaratã friend în clasa IntSListNode, pentru ca aceasta din urmã sã poatã accesa datele protejate ale clasei IntSList.

class IntSListNode{ // nod in lista simplu inlantuita
int v; // elementul listei, nr. intreg
IntSListNode* link; // pointer la nodul urmator
public:
friend class IntSList;
IntSListNode(int x) {
v = x;
link = NULL;
}
~IntSListNode();
};
class IntSList{ // lista simplu inlantuita
IntSListNode* first; // pointer la primul nod
IntSListNode* last; // pointer la ultimul nod
int count; // numarul de elemente
public:
IntSList(){ first = 0; last = 0; count = 0;}
IntSList(int x);
IntSList(int* p, int n);
IntSList(const IntArray& array);
IntSList(IntSList& r){
~IntSList();
int GetCount(){return count;}
int GetHead(); // citeste elem. din cap
int GetTail(); // citeste elem. din coada
void AddHead(int x); //adauga elem. in capul listei
void AddTail(int x); //adauga elem. in coada listei
int RemoveHead(); // extrage elem. din cap
int RemoveTail(); // extrage elem. din coada
int Lookup(int x); // cãutare element x
void Display(); // afiseaza toate elem. listei
};

Constructorul de iniþializare al clasei IntSListNode construieºte un nod al listei în care elementul primeºte valoarea transmisã ca argument ºi pointerul de înlãnþuire nul (0).
Contructorul de inizializare cu un argument de tip întreg al clasei IntSList creazã o listã compusã dintr-un singur nod (element al listei) pe care îl alocã dinamic în memoria heap folosind operatorul new:

inline IntSList::IntSList(int x){
IntSListNode* elem = new IntSListNode(x);
first = elem;
last = elem;
count = 1;
}

Constructorul de iniþializare cu douã argumente creazã o listã înlãnþuitã în care elementele (pe care le creazã în memoria heap) sunt în ordinea din vectorul de numere întregi primit ca argument.

IntSList::IntSList(int* p, int n){
first = 0;
for (int i=0;i<n;i++){
IntSListNode* elem =
new IntSListNode(p[n-1-i]);
elem->link = first;
first = elem;
if (i == 0)
last = elem;
}
count = n;
}

Se mai poate defini un constructor având ca argument o referinþã (const) la un obiect din clasa IntArray, care conþine un vector de numere întregi (Exerciþiul 3.6):

IntSList::IntSList(const IntArray& array){
int n = array.GetSize();
first = 0;
for (int i=0;i<n;i++){
IntSListNode* elem =
new IntSListNode(array.GetAt(n-1-i));
elem->link = first;
first = elem;
if (i == 0)
last = elem;
}
count = n;
}
Constructorul de copiere al clasei IntSList se defineºte astfel:

IntSList::IntSList(IntSList& r){
first = 0;
last = 0;
count = 0;
IntSListNode* ref = r.first;
for (int i=0;i<r.count;i++){
int x = ref->v;
AddTail(x);
ref = ref->link;
}
}

Destructorul clasei IntSListNode nu are de executat nici-o operaþie utilã, alta decât sã afiºeze un mesaj care sã permitã ulterior observarea compotãrii acestei clase. Destructorul clasei IntSList parcurge lista înlãnþuitã de noduri ºi le ºterge succesiv din memorie folosind operatorul delete:

~IntSListNode(){
cout << "Destructor nod v = " << v <<endl;
}
IntSList::~IntSList(){
IntSListNode* p = first;
while (p){
IntSListNode* current = p;
p = p->link;
delete current;
}
}

În Exerciþiul 3.2 este propus ºi un alt mod de distrugere a obiectelor de clasã IntSListNode ºi IntSList.
Funcþia Display() a clasei IntSList afiºeazã conþinutul unei liste începând cu primul nod. O operaþie asemãnãtoare se poate obþine prin supraîncãrcarea funcþiei operator << pentru clasa IntSList (Exerciþiul 4. … )

void IntSList::Display(){
IntSListNode* p = first;
while (p){
cout << p->v << " ";
p = p->link;
}
cout << endl;
}

Fie urmãtoarea funcþie fslist1():

void fslist1(){
int val[] = {1,2,3,4,5};
IntSList list1(val, sizeof(val)/sizeof(int));
list1.Display();
}

Obiectul list1 de clasã IntSList care se creazã la execuþia acestei funcþii este reprezentat în Fig. 3.4.

Fig. 3.4 Obiect (listã simplã înlãnþuitã de numere întregi) din clasa IntSetList

Mesajele afiºate la execuþia funcþiei fslist1() sunt:

1 2 3 4 5
Destructor nod v = 1
Destructor nod v = 2
Destructor nod v = 3
Destructor nod v = 4
Destructor nod v = 5

Operaþiile de dicþionar implementate pentru aceastã listã permit adãugarea unui nou element la începutul sau sfârºitul listei (AddHead() ºi AddTail()) ºi extragerea (citire valoare ºi eliminare) unui element din capul sau coada listei (RemoveHead() ºi RemoveTail()). În aceste operaþii de adãugare ºi ºtergere element nu trateazã cazurile de eroare (eroare de alocare a unui nod nou la inserare sau eroarea de listã vidã la extragere). Aceste situaþii se vor trata ca excepþii (în secþiunea 8).

void IntSList::AddHead(int x){
IntSListNode* elem = new IntSListNode(x);
elem->link = first;
first = elem;
if (count == 0)
last = elem;
count++;
}
void IntSList::AddTail(int x){
IntSListNode* elem = new IntSListNode(x);
if (count==0){
first = elem;
last = elem;
}
else{
last->link = elem;
last = elem;
}
count++;
}
int IntSList::RemoveHead(){
if (count == 0)
return -1; // eroare tratata superficial
else {
int v = first->v;
IntSListNode* p = first;
first = first->link;
delete p;
count--;
if (count == 0){
last = 0;
}
return v;
}
}
int IntSList::RemoveTail(){
int v;
if (count == 0)
return -1; //eroare tratatã superficial
else{
IntSListNode* p = first;
while(1){
if (p->link){ // cel putin 2 eleem
if (!p->link->link){
v = p->link->v;
delete last;
p->link = 0;
last = p;
count--;
return v;
}
else p = p->link;
}
else{ // 1 element
v = p->v;
delete p;
first = 0;
last = 0;
count = 0;
return v;
}
}
}
}

Alte funcþii membre ale clasei IntSList sunt funcþii de aflare a elementelor de început ºi de sfârºit ale liste, GetHead() ºi GetTail() ºi funcþia Lookup() care returneazã numãrul de elemente cu o valoare datã aflate în listã. Definiþiile acestor funcþii sunt lãsate ca un exerciþiu simplu.

Lista simplu înlãnþuitã definitã prin clasele IntSListNode ºi IntSList se poate folosi pentru a implementa o stivã de numere întregi. Funcþia AddHead() este echivalentã operaþiei push, iar funcþia RemoveHead() este echivalentã operaþiei pop. Funcþia fslist2() evidenþiazã acest lucru:

void fslist2(){
// functionarea listei ca stiva
IntSList list2;
list2.AddHead(1); // push 1
list2.AddHead(2); // push 2
list2.AddHead(3); // push 3
cout << list2.RemoveHead(); // pop, afiseaza 3
cout << list2.RemoveHead(); // pop, afiseaza 2
cout << list2.RemoveHead(); // pop, afiseaza 1

}

De acemenea, aceastã listã se poate folosi pentru implementarea unei cozi de numere întregi. Funcþia AddTail() este echivalentã operaþiei de inserare, iar funcþia RemoveHead() este echivalentã operaþiei de extragere. De exemplu:

void fslist3(){
// functionarea ca o coada a listei
IntSList list3;
list3.AddTail(1); // inserare 1
list3.AddTail(2); // inserare 2
list3.AddTail(3); // inserare 3
cout << list3.RemoveHead(); // extragere,afiseaza 1
cout << list3.RemoveHead(); // extragere,afiseaza 2
cout << list3.RemoveHead(); // extragere,afiseaza 3
}