Array dinamico: differenze tra le versioni

sistemo un pò
(fix)
(sistemo un pò)
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
è 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 [[allocazione dinamica della memoria|allocato dinamicamente]],
il quale è un array di dimensione fissa la quale è fissata quando l'array è allocato; per maggiori informazioni su questo
quale è fissata quando l'array è allocato; 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 dalla 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
dividendolo in due parti: la prima memorizza gli elementi dell'array dinamico e
''dimensione logica'' o ''dimensione'', mentre la dimensione dell'array sottostante è chiamata la ''capacita'' dell'array dinamico, la quale è la massima dimensione logica possibile.
la seconda è riservata, o inutilizzata. A questo punto è possibile aggiungere o
rimuovere elementi dalla 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 ''dimensione'', mentre la dimensione dell'array
sottostante è chiamata la ''capacita'' dell'array dinamico, la quale è la
massima dimensione logica possibile.
 
Nelle applicazioni dove 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.
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 ==
l'inserimento o la rimozione dal mezzo dell'array.
 
L'[[Hashed array tree]] (HAT) è un algoritmo di array dinamico invetatoinventato da
Sitarski nel 1996.<ref name="sitarski96"> HATs: Hashed array trees.
[http://www.ddj.com/architect/184409965?pgno=5]</ref> L'Hashed Array Tree perde