Lista (informatica)

struttura dati astratta

In informatica, una lista (in inglese 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.[1]

Operazioni fondamentali

modifica

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].

Implementazione

modifica
 
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 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 SNode{
        TInfo info;
        struct TNode *link;
    };
    
    typedef struct SNode TNode;
    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 lista

modifica
  1. ^ Vito Lavecchia, Definizione e di Lista in informatica con implementazione in C, su Informatica e Ingegneria Online, 7 luglio 2017. URL consultato il 17 giugno 2024.

Voci correlate

modifica

Altri progetti

modifica

Collegamenti esterni

modifica
Controllo di autoritàLCCN (ENsh85077455 · GND (DE4783888-7 · J9U (ENHE987007531493105171
  Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica