La frase 'array con valore variabile' NON VUOL DIRE quello che pensi.
Tu stai chiedendo se sia o meno possibile avere un array di DIMENSINE variabile.
OVVIAMENTE SI PUO' FARE a partire da array di dimensione prefissata.
Ad esempio in C++ c'e' std::vector.
Invece supponi di voler inserire un'UNICO valore all'indice 100000000000.
la struttura STANDARD degli arraiy prevede di allocare un vettore per contenere TUTTI gli elementi (un miliardo) quando a te ne basta giusto UNO.
In questo caso bisogna ragionare in termini di 'vettore sparso': e' una str\truttura dati che si comporta quasi come un vettore classico (puoi accedere agli elementi per indice) MA alloca spazio in modo decisamente piu' astuto. Si basa su 'dizionario'/'mappa.
Che cosa succede se vuoi accedere ad un elemento non esistente?
In questo specifico caso, puoi ritornare un valore di default, ad esempio 0
In pratica:
le strutture dati 'native' sono MOLTO semplici.
Nulla vieta al programmatore di inventarsi strutture dati infinitamente piu' complicate, a partire da quelle piu' semplici e sfruttando le possibilita' messe a disposizione dal linguaggio di programmazione (classi, interfacce, metodi virtuali, ...)