Lista (informatica)

In informatica, una Lista (List) è una struttura dati astratta 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 fondamentali

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

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 ridimensionamendo dell'array) mentre su una LinkedList costerà sempre O(1).

Algoritmi di gestione (iterativi)

• 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 Nodi

  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)

• 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 Nodi

  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){
     if(list!=NULL){
        list->link = list_destroy(list->link);
        free(list);
        return NULL;
     }else
        return list;
  }

Tipi di lista

• Lista con puntatori
• Lista con array
• Lista Circolare

Voci correlate

• Comprensione di lista
• Struttura dati
• Costo computazionale
• Multiinsieme

Altri progetti

• Wikizionario

• Wikizionario contiene il lemma di dizionario «lista»