Apri il menu principale

Lista (informatica)

struttura dati astratta

In informatica, una Lista (List) è una struttura dati astratta e dinamica (la memoria usata non è necessariamente fisicamente contigua) che denota una collezione omogenea o container di dati. L'accesso a un elemento della struttura avviene direttamente solo al primo elemento della sequenza; per accedere a un qualunque elemento, occorre scandire sequenzialmente tutti gli elementi che lo precedono; è una struttura dati dinamica poiché può cambiare di dimensione grazie alle operazioni di inserimento ed eliminazione di elementi, diversamente al caso degli array standard.

Operazioni fondamentaliModifica

Le operazioni fondamentali offerte da una Lista sono le seguenti:

  • Inserimento [Costo O(1) oppure O(n) a seconda dell'implementazione];
  • Rimozione [Costo O(1) oppure O(n) a seconda dell'implementazione];
  • Ricerca [Costo O(log(n)) oppure O(n) a seconda dell'implementazione];
  • Accesso random mediante indice [Costo O(1) oppure O(n) a seconda dell'implementazione];
  • Accesso sequenziale [Costo O(1)];
  • Conteggio elementi [Costo O(1) oppure O(n) a seconda dell'implementazione].

ImplementazioneModifica

 
Esempio di lista implementata mediante strutture collegate

Principalmente, vi sono due implementazioni delle Liste. Una utilizza come appoggio gli array, l'altra le strutture collegate; i due approcci si differenziano per le prestazioni offerte. In particolare, un ArrayList offrirà un accesso random al costo di O(1), mentre una LinkedList offrirà un costo O(n); dall'altro lato un inserimento su un ArrayList potrebbe costare O(n) (nel caso di ridimensionamento o dell'array), mentre su una LinkedList costerà sempre O(1).

Algoritmi di gestione (iterativi)Modifica

  • Definizione struttura:
    typedef int TKey;
    typedef int TSat;
    
    struct SInfo{
        TKey key;
        TSat satellite;
    };
    
    typedef struct SInfo TInfo;
    
    struct TNode{
        TInfo info;
        struct TNode *link;
    };
    
    typedef struct TNode SNode;
    typedef TNode* TList;
    
  • Creazione:
    TList list_create() {
        return NULL;
    }
    
  • Inserimento:
    TList list_insert(TList list, TInfo info) {
        TList curr, succ;
        curr = NULL;
        succ = list;
        
        while(succ != NULL && greater(info.key, succ->info.key)){
            curr = succ;
            succ = succ->link;
        }
        
        TNode* new;
        new = (TNode)malloc(sizeof(TNode));
        new->info = info;
        
        if(curr == NULL) {
            new->link = list;
            
            return new;
        } else {
            curr->link = new;
            new->link = succ;
            
            return list;
        }
    }
    
  • Rimozione:
    TList list_delete(TList list, TKey key) {
        TList curr, succ;
        curr = NULL;
        succ = list;
        
        while(succ != NULL && greater(key,succ->info.key)) {
            curr = succ;
            succ = succ->link;
        }
        
        if(succ != NULL && equal(key,succ->info.key)) {
            if(curr == NULL) {
                list = succ->link;
            } else {
                curr = succ->link;
                
                free(succ);
            } return list;
        }
    }
    
  • Cerca:
    T_Node* list_search(T_List list, T_Key key) {
        T_List curr;
        curr = list;
        
        while((curr != NULL) && greater_team(key,curr->info.tag)) {
            curr = curr->link;
        }
        
        if((curr != NULL) && equal_team(key,curr->info.tag)) {
            return curr;
        } else {
            return NULL;
        }
    }
    
  • Visita con stampa:
    void list_visit(T_List list) {
        T_List curr;
        curr = list;
        
        while(curr != NULL) {
            print_node(curr->info);
            curr = curr->link;
        }
    }
    
  • Conta:
    int conta_nodi(T_List list) {
        if(list == NULL) {
            return 0;
        } else {
            return 1 + conta_nodi(list->link);
        }
    }
    
  • Distruzione lista:
    T_List list_destroy(T_List list) {
        T_List curr, succ;
        curr = list;
        
        while(curr != NULL) {
            succ = curr->link;
            
            free(curr);
            
            curr=succ;
        }
    }
    

Algoritmi di gestione (ricorsivi)Modifica

  • Creazione:
    TList list_create() {
        return NULL;
    }
    
  • Inserimento:
    TList list_insert(TList list, Tinfo info) {
        if(list == NULL || greater(list->info.key, info.key)) {
            TNode* new;
            
            new = (TNode*)malloc(sizeof(TNode));
            
            new->info = info;
            new->link = list;
            
            return new;
        } else {
            list->link = list_insert(list->link, info);
            
            return list;
        }
    }
    
  • Rimozione:
    TList list_delete(TList list, TKey key) {
        if((list == NULL) || grater(list->info.key, key)){
            return list;
        } else if(equal(list->info.key, key)) {
            TList alias;
            alias = list->link;
            
            free(list);
            
            return alias;
        } else {
            list->link = list_delete(list->link, key);
            
            return list;
        }
    }
    
  • Cerca:
    T_Node* list_search(T_List list, T_Key key) {
        if(list == NULL || equal(list->info.key, key)){
            return list;
        } else if(grater(list->info.key, key)){
            return NULL;
        } else {
            list_search(list->link, key);
        }
    }
    
  • Visita con stampa diretta:
    void list_visit(T_List list) {
        if(list != NULL) {
            print_info(list->info);
            list_visit(lista->link);
        }
    }
    
  • Visita con stampa inversa:
    void list_visit(T_List list) {
        if(list != NULL) {
            list_visit(lista->link);
            
            print_info(list->info);
        }
    }
    
  • Conta:
    int conta_nodi(T_List list) {
        if(list == NULL){
            return 0;
        } else {
            return 1 + conta_nodi(list->link);
        }
    }
    
  • Distruzione lista:
    T_List list_destroy(T_List t) {
    	if (t != NULL)
    	{
    		list_destroy(t->link);
    		free(t);
    	}
    	return NULL;
    }
    

Tipi di listaModifica

Voci correlateModifica

Altri progettiModifica

Collegamenti esterniModifica

Controllo di autoritàLCCN (ENsh85077455