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.^[1]

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

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

• 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;
      }
  }
  

• 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;
  }
  

• Lista con puntatori
• Lista con array
• Lista Circolare

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

• Wikizionario contiene il lemma di dizionario «lista»

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