10 2018 Lectia26

Adaugare la sfarsitul listei

FAdaugareLaLista

Să se scrie o funcție C++ care adaugă o valoarea la finalul unei liste simplu înlănțuită.

// adaugă valoarea x la sfârșitul listei
void adaugare ( nod* &p, int x ){
  nod *q;
  q = new nod;      		// alocam o noua adresa
  q->info = x;			// punem in campul info valoare de adaugat la lista
  q->urm = NULL;    		// q va fi ultimul element al listei
  if ( p == NULL )  		// daca am lista vida
    p = q;			// q va fi primul nod al listei
  else {            		// daca avem noduri in lista
    nod *sf = p;	        // parcurgem lista pana la ultimul element al listei
    while ( sf->urm != NULL )
      sf = sf->urm;
    sf->urm = q;		// leg ultimul nod al listei de noul nod alocat
  }	
}

Observatie: Pentru un acces rapid al ultimului element al listei, putem sa folosim un al doilea pointer care sa retina ultimul nod al listei, in acest fel accesul la ultimul nod al listei se va realiza in O(1) ci nu in O(n) ca in in exemplul de mai sus.

// adaugă valoarea x la sfârșitul listei
void adaugare ( nod* &p, nod* &u, int x ){
  nod *q;
  q = new nod;      		// alocam o noua adresa
  q->info = x;			// punem in campul info valoare de adaugat la lista
  q->urm = NULL;    		// q va fi ultimul element al listei
  if ( p == NULL )  		// daca am lista vida
    p = q, u = q;	        // q va fi si primul si ultimul nod al listei
  else {            		// daca avem noduri in lista
    u->urm = q;		        // leg ultimul nod al listei de noul nod alocat
    u = q;                      // ultimul nod devine q
  }	
}