[C]Solo un'opinione...inserimento in coda (liste)

[David Gnomo Amico Mio]

Secondo voi è un modo "ortodosso" per un inserimento in coda senza scandire ogni volta l'intera lista? Ci sono modi migliori / più efficienti per l'inserimento in coda? Io l'ho pensato cosi, ma vorrei sapere qualche opinione in merito ;)

Spoiler

#include 
#include 
 
typedef struct list_s{    
        int dato;
        struct list_s *next;
        } elem_t;
 
 
 
elem_t* inscoda_ott(elem_t* h,int val,elem_t **use);
 
 
int main (int argc,char*argv[]){
    elem_t *h=NULL,*use=NULL;
    int val,n;
    
    printf("Inserisci valori (ultimo valore 0): ");
    
    
    scanf("%d",&val);
    do{
        h=inscoda_ott(h,val,&use);
        scanf("%d",&val);
    }while(val);
 
    for(use=h; use; use=use->next)
        printf("%d ",use->dato);
    return 0;
}
 
 
 
elem_t* inscoda_ott(elem_t* h,int val,elem_t **use){
    elem_t *p=NULL,*tmp;
    
    if(tmp=(elem_t*)malloc(sizeof(elem_t))){
            tmp->dato=val;
            tmp->next=NULL;
            
            if(h){
                p=*use;
                p->next=tmp;
                *use=tmp;
            } else {
                h=tmp;
                *use=h;
            }
    }else
        printf("Errore di memoria.\n");
    
    
    return h;    
 }

Ovviamente qualche funzionalità nel main è di test. La struttura all'inizio è per la lista (obv.).
Saluti! :)


(chiedo scusa per l'indentazione totalmente assente, ma dal cellulare mi risulta difficile)

 

[Mattia Campagna]

Beh, l'unico modo per inserire in coda avendo una complessità inferiore a quella lineare è mantenere un puntatore all'ultimo elemento. Lo hai testato il programma?

 

[BAT]

Quando implementi una coda con strutture e puntatori devi mantenere 2 puntatori:
uno che punta alla fine della coda ed uno alla fine;
è la logica FIFO (first-in-first-out, il primo che entra è il primo a uscire) che te lo impone:
inserisci sempre alla fine, per cui l'inserimento ti costerà O(1) e,
allo stesso modo, elimini dalla coda in tempo O(1)