Lista (informatica)

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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

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

Note

Voci correlate

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

Altri progetti

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

V · D · M Algoritmi di ordinamento
Teoria	Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo
Algoritmi a scambio	Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort
Algoritmi di selezione	Selection sort · Heap sort · Smoothsort
Algoritmi ad inserimento	Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting
Algoritmi a fusione	Merge sort · Timsort
Algoritmi non comparativi	Radix sort · Bucket sort · Counting sort · Pigeonhole sort
Altri algoritmi	Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle
Algoritmi inefficienti	Stupid sort · Trippel sort

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica