next up previous contents index
Next: Liste circolari Up: Cenni su liste non Previous: Liste ordinate   Indice   Indice analitico

Liste semplici con puntatore in coda

Si sarà certamente notato che le liste semplici sono molto semplici e veloci per quanto riguarda l'inserzione in testa, mentre sono particolarmente complesse e lente sulla medesima operazione effettuata in coda; si può ovviare a tale asimmetria semplicemente tenendo due puntatori per ogni lista (in testa e in coda), piuttosto che uno solo. Vediamo un esempio:

// ex7_8_2
#include <iostream.h>

struct elem {
  int   info;
  elem* next;
  elem (int Info, elem* Next) {
    info = Info;
    next = Next;
  }
};

// inserisce un elemento in testa
void inserisciTesta (elem*& testa, elem*& coda, int n) {
  testa = new elem (n, testa);
  if (testa->next == 0)
    coda = testa;
}

// inserisce un elemento in coda
void inserisciCoda (elem*& testa, elem*& coda, int n) {
  if (coda == 0) {
    testa = new elem (n, 0);
    coda = testa;
  }
  coda = coda->next = new elem (n, 0);
}

// stampa la lista
void stampa (const elem* testa) {
  const elem* p = testa;
  while ( p != 0 ) {
    cout << p->info << "\t";
    p = p->next;
  }
  cout << "\n";
}

void main() {
  elem *testa = 0, *coda = 0;
  int i;
  for (i = 0; i < 3; i++)
    inserisciTesta (testa, coda, i);
  for (i = 3; i < 6; i++)
    inserisciCoda (testa, coda, i);
  stampa (testa);
}

output:
 2 1 0 3 4 5

Le liste semplici con un puntatore in coda presentano come unico vantaggio quello di potere aggiungere a tempo costante un elemento in coda; del resto l'utilizzo e gli algoritmi relativi a tale struttura dati sono del tutto simili a quelli delle liste semplici con un solo puntatore.



Claudio Cicconetti
2000-09-06