Array dinamico

In informatica, un vettore dinamico, vettore allargabile, vettore ridimensionabile, tabella dinamica, o lista di array è una struttura dati array che può essere ridimensionata e consente di aggiungere o rimuovere elementi. È fornita con la libreria standard in molti moderni linguaggi di programmazione principali.

Un array dinamico non è la stessa cosa di un array allocato dinamicamente: quest'ultimo è un array di dimensione fissata all'atto dell'allocazione o instanziazione dell'array stesso; per maggiori informazioni su questo tipo di array, vedere array.

Array dinamici di dimensione delimitata e capacità

L'array più semplice è costruito allocando un array di dimensione fissa e dividendolo in due parti: la prima memorizza gli elementi dell'array dinamico e la seconda è riservata, o inutilizzata. A questo punto è possibile aggiungere o rimuovere elementi alla fine dell'array dinamico in tempo costante utilizzando lo spazio riservato, finché questo spazio non viene completamente consumato. Il numero di elementi utilizzati per i contenuti dell'array dinamico è la sua dimensione logica (o, semplicemente, dimensione), mentre la dimensione dell'array sottostante è chiamata la capacita dell'array dinamico, che è la massima dimensione logica possibile.

Nelle applicazioni in cui la dimensione logica è delimitata (bounded), questa struttura dati è sufficiente. Il ridimensionamento dell'array sottostante è un'operazione dispendiosa, che tipicamente coinvolge la copia dell'intero contenuto dell'array.

Espansione geometrica e costo ammortizzato

Il ridimensionamento comporta un costo molto elevato, perché implica la costruzione di un altro array con dimensione aumentata e la successiva copia degli elementi dal "vecchio" al "nuovo" array. Per evitare di eseguire questo procedimento ogni volta che si aggiunge un nuovo elemento, gli array dinamici si ridimensionano raddoppiando le dimensioni (invece che di una sola unità). In questo modo si utilizza lo spazio riservato per espansioni future. L'operazione di aggiunta di un elemento alla fine potrebbe funzionare come segue:

funzione inserisciFine(arraydin a, elemento e)
    se (a.dimensione = a.capacità)
        // ridimensiona al doppio della sua capacità corrente:
        a.capacità ← a.capacità * 2  
        // (copia i coontenuti delle nuove locazioni qui)
    a[a.dimensione] ← e
    a.dimensione ← a.dimensione + 1

Man mano che gli n elementi vengono inseriti, le capacità formano una progressione geometrica. Espandere l'array di una qualsiasi proporzione costante assicura che l'inserimento di n elementi prende un tempo complessivo di O(n), ciò significa che ogni inserimento prende un tempo costante ammortizzato. Il valore di questa proporzione a porta a un compromesso spazio-tempo: il tempo medio per l'operazione di inserimento è circa a/(a-1), mentre il numero di celle perse è delimitata superiormente da (a-1)n. La scelta di a è indipendente dall'applicazione, ma un uso comune è a=2.

Molti array dinamici deallocano anche parte della memoria sottostante se la loro dimensione scende sotto una certa soglia (ad esempio, il 30% della capacità).

Gli array dinamici sono un esempio comune quando si insegna analisi ammortizzata.

Prestazioni

	Lista concatenata	Array	Array dinamico
Indicizzazione	Θ(n)	Θ(1)	Θ(1)
Visita in ordine	Θ(n)	Θ(n)	Θ(n)
Inserimento/rimozione alla fine	Θ(1)	N/A	Θ(1)
Inserimento/rimozione nel mezzo	Θ(1)	N/A	Θ(n)
Spazio perso (media)	Θ(n)	0	Θ(n)

L'array dinamico ha prestazioni simili all'array, con l'aggiunta delle nuove operazioni di aggiunta e rimozione di elementi dalla fine:

Ottenere o impostare il valore a un particolare indice (tempo costante)
Iterare attraverso gli elementi in ordine (tempo lineare, buone prestazioni di cache)
Inserire o rimuovere un elemento dal mezzo dell'array (tempo lineare)
Inserire o rimuovere un elemento alla fine dell'array (tempo costante ammortizzato)

Gli array dinamici beneficiano di molti vantaggi degli array, inclusa una buona località di riferimento e l'utilizzo di cache dati, compattezza (basso utilizzo di memoria), e accesso casuale. In genere hanno solo un piccolo sovraccarico addizionale (overhead) per memorizzare le informazioni su dimensione e capacità. Questo rende gli array dinamici uno strumento attraente per la costruzione di strutture dati cache-friendly.

Paragonati alle liste concatenate, gli array dinamici hanno un'indicizzazione più rapida (tempo costante contro tempo lineare) e tipicamente anche una più rapida iterazione grazie alla migliore località di riferimento; tuttavia, gli array dinamici richiedono un tempo lineare per inserire o cancellare su una locazione arbitraria, dal momento che tutti gli elementi seguenti devono essere spostati, mentre le liste concatenato possono farlo in tempo costante. Questo svantaggio è mitigato dal buffer gap e dalla variante vettore graduato discusso nel paragrafo Varianti più sotto. Inoltre, per una regione di memoria altamente frammentata, può essere dispendiosa o impossibile trovare uno spazio contiguo per un grosso array dinamico, mentre le liste concatenate non richiedono che l'intera struttura dati sia memorizzata in maniera contigua.

Varianti

I buffer gap sono simili agli array dinamici ma consentono un'efficiente operazione di inserimento e rimozione raggruppata vicino alla stessa locazione arbitraria. Alcune implementazioni di deque utilizzano gli array deque, i quali consentono tempo costante ammortizzato di inserimento/rimozione su entrambi gli estremi, anziché solo alla fine.

Goodrich^[1] ha presentato un algoritmo di array dinamici chiamato Tiered Vectors (vettore graduato) che consente prestazioni O(n^1/2) per preservare l'inserimento o la rimozione dal mezzo dell'array.

L'Hashed array tree (HAT) è un algoritmo di array dinamico inventato da Sitarski nel 1996.^[2] L'Hashed Array Tree perde una quantità di spazio di memorizzazione nell'ordine di n^1/2, dove n è il numero di elementi nell'array. L'algoritmo ha le prestazioni ammortizzate su O(1) quando aggiunge una serie di oggetti alla fine dell'Hashed Array Tree.

In una relazione del 1999 ^[3], Brodnik et al. descrivono una struttura dati array graduato dinamico, il quale perde solo n^1/2 di spazio per n elementi in qualsiasi punto nel tempo, e provano un limite più basso mostrando che gli array dinamici devono perdere questo spazio in più se le operazioni sono di rimanere ammortizzate nel tempo. In aggiunta, presentano una variante dove l'allargamento e lo restringimento del buffer non sono solo ammortizzati ma nel caso peggiore in tempo costante.

Bagwell (2002)^[4] ha presentato l'algoritmo VList, il quale può essere adottato per implementare un array dinamico.

Supporto nei linguaggio

Il tipo di dato std::vector in C++ è un'implementazione degli array dinamici, così come le classi ArrayList fornite con l'API Java e l'infrastruttura .NET. Anche la classe generica List<> fornita con la versione 2.0 dell'infrastruttura .NET è implementata con array dinamici. Il Delphi e il D implementano gli array dinamici nel nucleo (il cosiddetto core) del linguaggio. Molti linguaggi di scripting come il Perl e il PHP offrono gli array dinamici come tipo di dati primitivo built-in. Il Python invece oltre ad avere la possibilità di costruire array dinamici, può contenere liste miste di interi, script, e floting.