b'\n_START_ARTICLE_\nStruttura dati\n_START_SECTION_\nArray o vettore\n_START_PARAGRAPH_\nUn array \xc3\xa8 una struttura dati omogenea, che contiene un numero finito di elementi tutti dello stesso tipo, ad esempio un vettore di 10 interi. Questi elementi sono individuati attraverso un indice numerico, che tipicamente va da 0 al numero massimo di elementi meno uno. La dimensione del vettore deve essere dichiarata al momento della sua creazione. Vettori di dimensione diversa costituiscono tipi di dati diversi. L\'accesso ad un elemento di un array ha un costo computazionale costante, mentre l\'aggiunta o la rimozione di elementi in posizione casuale possono essere piuttosto onerose, tipicamente appannaggio degli array dinamici.\n_START_SECTION_\nRecord o struttura\n_START_PARAGRAPH_\nUn record \xc3\xa8 una struttura dati che pu\xc3\xb2 essere eterogenea o omogenea. Nel primo caso contiene una combinazione di elementi che possono essere di diverso tipo, ad esempio un intero, un numero in virgola mobile e un carattere testuale. Gli elementi che lo compongono sono detti anche campi, e sono identificati da un nome.\n_START_SECTION_\nClasse\n_START_PARAGRAPH_\nUna classe \xc3\xa8 un costrutto tipico dei linguaggi orientati agli oggetti, e consiste in un record a cui sono associate anche delle operazioni o metodi.\n_START_SECTION_\nComposizione di costruttori\n_START_PARAGRAPH_\nQuesti costruttori possono essere liberamente combinati per dare luogo a strutture pi\xc3\xb9 complesse._NEWLINE_Per esempio, \xc3\xa8 possibile rappresentare una matrice bidimensionale di taglia  come un vettore di dimensione  avente come elementi dei vettori di lunghezza . Ancora, si pu\xc3\xb2 definire un array di cinquecento elementi, ognuno dei quali \xc3\xa8 un record composto da quattro stringhe e due vettori, ciascuno contenente quattro vettori di tre caratteri._NEWLINE_Le strutture dati ottenute mediante la composizione di questi costruttori sono dette anche "statiche", in quanto la loro occupazione di memoria \xc3\xa8 definita al momento della compilazione, o al pi\xc3\xb9 al momento dell\'istanziazione. Ad esempio: il programma decide che ha bisogno di un array di 100 elementi per processare i suoi dati, e lo alloca, ovvero impegna la memoria necessaria. Da questo momento, l\'array avr\xc3\xa0 dimensione fissa cio\xc3\xa8 sar\xc3\xa0 sempre composto di 100 elementi, e terr\xc3\xa0 impegnata la memoria necessaria fino alla terminazione del programma o a quando non sar\xc3\xa0 distrutto. Cambiare la lunghezza dell\'array \xc3\xa8 possibile, ma molto costoso in termini di risorse di calcolo ed \xc3\xa8 quindi un\'operazione evitata per quanto possibile (vedi array dinamici)._NEWLINE_Il limite delle strutture dati statiche \xc3\xa8 che mal si adattano a problemi in cui la numerosit\xc3\xa0 dei dati da trattare non \xc3\xa8 nota a priori e/o varia sensibilmente durante l\'esecuzione del programma.\n_START_SECTION_\nStrutture dati dinamiche\n_START_PARAGRAPH_\nLe strutture dati dinamiche sono basate sull\'uso di dati di tipo puntatore, e sull\'allocazione dinamica della memoria. Gli elementi possono essere allocati (e deallocati) man mano che servono, collegati tra loro in modi diversi, e questi collegamenti possono a loro volta mutare durante l\'esecuzione del programma. Lo spazio di memoria necessario per allocare i puntatori, e le operazioni necessarie alla loro manutenzione costituiscono il costo aggiuntivo delle strutture dati dinamiche._NEWLINE_In assenza dei puntatori, \xc3\xa8 anche possibile costruire strutture dati dinamiche utilizzando gli array, rinunciando per\xc3\xb2 alla flessibilit\xc3\xa0 nell\'uso della memoria: viene allocato un array di dimensioni sufficienti a contenere tutti gli elementi che si pensa di dover gestire, e al posto dei puntatori si usano indici nell\'array._NEWLINE_Le strutture dati dinamiche possono adattarsi a rappresentare qualsiasi situazione. Qui vengono illustrati i tipi pi\xc3\xb9 comuni.\n_START_SECTION_\nLista\n_START_PARAGRAPH_\nUna lista \xc3\xa8 un insieme di "nodi" collegati linearmente. I nodi sono dei record che contengono un "carico utile" di dati, ed un puntatore all\'elemento successivo della lista. L\'ordine con cui sono collegati i nodi definisce un ordinamento tra di loro. Un nodo funge da testa della lista, e da questo \xc3\xa8 possibile accedere a tutti i nodi della lista. Conoscendo un nodo interno alla lista, \xc3\xa8 possibile accedere ai nodi successivi, ma non a quelli precedenti._NEWLINE_Il costo di accesso ad un nodo della lista cresce con la dimensione della lista. Conoscendo il nodo precedente ad un nodo N, \xc3\xa8 possibile rimuovere N dalla lista, o inserire un elemento prima di lui, in un tempo costante.\n_START_SECTION_\nLista bidirezionale o doppiamente concatenata\n_START_PARAGRAPH_\nIn questo caso i nodi contengono un puntatore sia al nodo precedente che al successivo. Usando la sintassi del linguaggio C, dato un nodo N il suo successore \xc3\xa8 N->succ, e il suo precedente \xc3\xa8 N->prec. Deve sempre essere vero che N->succ->prec == N. Ogni nodo permette di accedere a tutti gli elementi della lista. Gli elementi "strutturali" di questa struttura dati, ovvero i due puntatori contenuti in ogni nodo, sono ridondanti.\n_START_SECTION_\nAlbero\n_START_PARAGRAPH_\nUn albero \xc3\xa8 una rappresentazione dell\'albero in teoria dei grafi._NEWLINE_Ogni nodo contiene due (o pi\xc3\xb9) puntatori ad altri nodi che sono detti suoi "figli". Continuando nella metafora, dato un nodo, \xc3\xa8 possibile accedere a tutti i suoi discendenti. Un albero deve essere privo di cicli, ovvero un nodo non pu\xc3\xb2 essere discendente di s\xc3\xa9 stesso, ovvero non deve essere possibile partire da un nodo, seguire i puntatori ai figli e ritornare al nodo di partenza. Inoltre ciascun nodo deve essere figlio di un solo padre._NEWLINE_In alcune implementazioni, ogni nodo contiene anche un collegamento al suo "padre", chiaramente distinto da quelli ai suoi figli._NEWLINE_Tra i figli di un nodo esiste normalmente una relazione d\'ordine, definita dall\'ordine dei puntatori nel padre._NEWLINE_In molte implementazioni, ogni nodo ha un numero fissato di figli, ad esempio due o tre. Si parla in questo caso di alberi binari o ternari. In altri casi, il numero di figli di un nodo \xc3\xa8 arbitrario; questo pu\xc3\xb2 essere gestito memorizzando i figli di un nodo in una lista di uno dei tipi descritti sopra._NEWLINE_Ciascun nodo, oltre ai puntatori ai nodi figli, ha normalmente un "carico utile", ovvero un dato associato al nodo, utile per il problema applicativo da risolvere._NEWLINE_Gli alberi si prestano molto bene a rappresentare le formule matematiche.\n_START_SECTION_\nGrafo\n_START_PARAGRAPH_\nIl grafo \xc3\xa8 una generalizzazione dell\'albero. Ogni nodo ha un numero arbitrario di nodi "vicini", e pu\xc3\xb2 contenere cicli. In generale, pu\xc3\xb2 essere associato un carico utile sia ai nodi che ai collegamenti tra di loro.\n_START_SECTION_\nTabella hash\n_START_PARAGRAPH_\nUna tabella hash \xc3\xa8 una struttura dati utile per cercare velocemente un elemento all\'interno di un insieme sulla base di una chiave, ovvero di un sottoinsieme dalle caratteristiche dell\'elemento. Di ciascun elemento da memorizzare viene calcolato un hash della chiave. Viene poi costruito un array, che ha come indice il valore dell\'hash, come elementi puntatori a liste di nodi che corrispondono a quel valore dell\'hash. Se la funzione di hash \xc3\xa8 ben scelta, statisticamente le liste avranno lunghezze equilibrate._NEWLINE_Per cercare un elemento, si calcola il suo valore di hash, si seleziona l\'elemento dell\'array corrispondente e si percorre la lista fino a quando non lo si trova.\n_START_SECTION_\nContenitori\n_START_PARAGRAPH_\nLe strutture dati sopra esposte possono essere utilizzate per realizzare alcuni tipi di contenitori di utilizzo frequente, che possono forzare una particolare modalit\xc3\xa0 di accesso ai dati.\n_START_SECTION_\nPila o stack\n_START_PARAGRAPH_\nUna pila \xc3\xa8 una struttura dati di tipo LIFO (Last In First Out). Viene tipicamente realizzata con array o liste.\n_START_SECTION_\nCoda\n_START_PARAGRAPH_\nUna coda \xc3\xa8 una struttura dati di tipo FIFO (First In First Out). Viene tipicamente realizzata con array o liste.\n_START_SECTION_\nArray associativo\n_START_PARAGRAPH_\n\xc3\x88 una struttura dati presente in molti linguaggi di scripting. Consiste in un array, i cui elementi sono per\xc3\xb2 identificati da una chiave di tipo arbitrario invece che da un indice numerico. Per accedere ad un elemento, si mette tipicamente la sua chiave tra parentesi quadre, al posto dell\'indice. Se non esiste un elemento con quella chiave, si ottiene un errore oppure un valore convenzionale.\n_START_SECTION_\nTemplate di strutture dati\n_START_PARAGRAPH_\nL\'implementazione manuale di strutture dati dinamiche \xc3\xa8 un compito ripetitivo, a rischio di errori. Per questa ragione, sono stati usati vari metodi per separare la definizione delle strutture dati dal loro utilizzo in algoritmi._NEWLINE_Alcuni linguaggi mettono a disposizione lo strumento dei template, che permette di scrivere funzioni o classi parametriche rispetto al tipo degli argomenti o di alcuni membri della classe che pu\xc3\xb2 essere utilizzata normalmente._NEWLINE_Un template viene istanziato specificando il tipo degli argomenti di funzione o dei membri di classe non specificati nella definizione, costruendo una funzione o una classe._NEWLINE_In questo modo, \xc3\xa8 possibile scrivere una classe lista generica rispetto al contenuto, con i metodi necessari a manipolare una lista, e poi usarla sia per gestire liste di interi che liste di oggetti complessi.\n_START_SECTION_\nSTL e Generics\n_START_PARAGRAPH_\nUn importante sforzo per costruire una libreria di strutture dati generiche rispetto al tipo dei dati immagazzinati \xc3\xa8 la Standard Template Library (vedi STL su sito SGI), basata sul concetto di fornire uno strumento per comporre in modo ortogonale dati, contenitori (strutture dati) ed algoritmi. In STL, un importante strumento per collegare in modo generico strutture dati ed algoritmi sono gli iteratori, una generalizzazione dei puntatori._NEWLINE_STL \xc3\xa8 una libreria di classi in linguaggio C++._NEWLINE_Il linguaggio Java presenta, invece, due modalit\xc3\xa0 per gestire le strutture dati fondamentali presenti nel linguaggio._NEWLINE_Fino alla versione 1.4 la gestione dei contenitori \xc3\xa8 stata realizzata con l\'ereditariet\xc3\xa0 invece che con i template. I contenitori contengono quindi oggetti di tipo "Object", un tipo da cui discendono tutte le classi definite in Java; di conseguenza, in Java non \xc3\xa8 altrettanto facile assicurarsi che tutti gli oggetti inseriti in un contenitore appartengano ad un dato tipo._NEWLINE_Dalla versione 1.5 sono stati introdotti i generics, che si comportano in modo molto simile ai template C++ e risolvono molti dei problemi relativi all\'upper casting dei "vecchi" contenitori.'