Lista (informatica)
# Lista (informatica)

In informatica, una Lista (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
