STRUTTURA DATI

Una struttura dati è un'entità usata per organizzare un insieme di dati all'interno della memoria del computer, ed eventualmente per memorizzarli in una memoria di massa. Per gestire una struttura dati è necessario utilizzare opportuni algoritmi, a tal proposito, solitamente si utilizza il concetto unificato di Algoritmi e Strutture Dati. La scelta della struttura dati influirà inevitabilmente sull'efficienza degli algoritmi da utilizzare.La struttura dati è un metodo di organizzazione dei dati, quindi prescinde dai dati effettivamente contenuti. Ciascun linguaggio di programmazione offre strumenti, più o meno sofisticati, per definire strutture dati, ovvero aggregare dati di tipo omogeneo o eterogeneo. Questi strumenti sono tipicamente componibili.
Più formalmente, i linguaggi forniscono un insieme predefinito di tipi di dato elementari, e le strutture dati sono strumenti per costruire tipi di dati aggregati più complessi.L'operazione di costruire una variabile di un tipo di dato complesso è detta "istanziazione", e può avvenire sia all'inizio dell'esecuzione del programma (compile time) sia durante la sua esecuzione (runtime).
Le strutture di dati si differenziano prima di tutto in base alle operazioni che si possono effettuare su di esse e alle prestazioni offerte. Questo permette di creare un'astrazione dall'implementazione, dando vita al concetto di Struttura di dati astratta o Abstract Data Structure (ADS).
Pila o stack
Una pila è una struttura dati di tipo LIFO (Last In First Out). Viene tipicamente realizzata con array o liste.
Lista
Una lista è 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 è possibile accedere a tutti i nodi della lista. Conoscendo un nodo interno alla lista, è possibile accedere ai nodi successivi, ma non a quelli precedenti.
Il costo di accesso ad un nodo della lista cresce con la dimensione della lista. Conoscendo il nodo precedente ad un nodo N, è possibile rimuovere N dalla lista, o inserire un elemento prima di lui in un tempo costante.
Array o vettore
Un array è una struttura dati omogenea, che contiene un numero finito di elementi 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.