Lista (informatica)

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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 | modifica sorgente]

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)[modifica | modifica sorgente]

  • 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)[modifica | modifica sorgente]

  • 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[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]


Altri progetti[modifica | modifica sorgente]