Lista (informatica)

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.

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 ridimensionamento 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 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)

• 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

• Lista con puntatori
• Lista con array
• Lista Circolare

Voci correlate

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

Altri progetti

Altri progetti

• Wikizionario

• Wikizionario contiene il lemma di dizionario «lista»

Collegamenti esterni

• (EN) list, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, List, su MathWorld, Wolfram Research.