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[modifica | modifica wikitesto]
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 wikitesto]
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)[modifica | modifica wikitesto]
- 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)[modifica | modifica wikitesto]
- 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[modifica | modifica wikitesto]
Voci correlate[modifica | modifica wikitesto]
Altri progetti[modifica | modifica wikitesto]
Wikizionario contiene il lemma di dizionario «lista»
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) list, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, List, su MathWorld, Wolfram Research.
| Controllo di autorità | LCCN (EN) sh85077455 · GND (DE) 4783888-7 · J9U (EN, HE) 987007531493105171 |
|---|
