En aplicaciones donde el tamaño lógico es conocido, las estructuras de tamaño fijo son las más eficientes, como es evidente, por lo que es mejor usar en estos casos arrays asignados dinámicamente, cuyo tamaño sea un parámetro de la ejecución, que pueda aumentarse cuando se detecta que se alcanzan los límites, optimizando el espacio ocupado.
Los arrays dinámicos son un ejemplo común en la enseñanza del coste y la amortización.
Por lo general tienen solo una pequeña sobrecarga fija adicional para almacenar información sobre tamaño y capacidad.
En comparación con las listas enlazadas, los arreglos dinámicos tienen indexación más rápida (tiempo constante frente a tiempo lineal) y la iteración es típicamente más rápida debido a la localización por referencia, sin embargo, los arreglos estáticos y los dinámicos requieren de un tiempo lineal para insertar o eliminar en una ubicación arbitraria, ya que todos los elementos siguientes deben ser movidos, mientras que las listas enlazadas se puede hacer esto en tiempo constante.
Un árbol equilibrado puede almacenar una lista, además de proporcionar las operaciones posibles en arrays dinámicos y en listas enlazadas, de forma razonablemente eficiente, pero tanto la inserción al final como la iteración sobre la lista son más lentos que para los arrays dinámicos, tanto en la teoría como en la práctica, debido a la falta de almacenamiento contiguo y las manipulaciones transversales en el recorrido del árbol.
Goodrich[6] presentó un algoritmo para arrays dinámicos al que llamó Vectores por niveles (Tiered Vectors), que proveían una Θ(n1/2) en el rendimiento de las inserciones o borrados al preservar el orden de mitad del array.
Además, presentan una variante donde crece y encoge el buffer tiene no solo tiempo amortizado, sino tiempo constante en el peor de los casos.
Bagwell[8] presenta en 2002 el algoritmo VList, que puede ser adaptado para implementar un array dinámico.