Array dinámico

En programación, un array dinámico, más apropiadamente llamado arreglo dinámico, también llamado inapropiadamente matriz dinámica o tabla dinámica, es un arreglo de elementos que crece o mengua dinámicamente conforme los elementos se agregan o se eliminan. Se suministra como librerías estándar en muchos lenguajes modernos de programación.

Un arreglo dinámico no es lo mismo que un arreglo asignado dinámicamente, que es un arreglo de tamaño fijo, pero cuyo tamaño se fija cuando se asigna por primera vez.​

Arreglos de tamaño predefinido y capacidad limitada

La forma más sencilla de construir un arreglo dinámico es la asignación de espacio de tamaño fijo dividido en dos partes: la primera es la parte ocupada de del arreglo y la segunda está libre para su crecimiento. Es sencillo así añadir o eliminar elementos en el extremo del arreglo en tiempo constante usando el espacio reservado, hasta que este espacio se consume completamente. El número de elementos usados ​​por el contenido del arreglo dinámico es su tamaño lógico o simplemente tamaño, mientras que el tamaño del arreglo subyacente se denomina la capacidad dinámica, que es el tamaño máximo posible sin reubicación de datos.

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 arreglos 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.

Expansión y coste

Cambiar el tamaño del arreglo subyacente es una tarea costosa, implicando típicamente copiar el contenido del arreglo a una nueva zona más grande de memoria, y liberar el espacio del arreglo anterior, lo que puede generar muchos espacios libres en memoria, que pueden ser o no reutilizados, en función de si es el programa o el recolector de basura el encargado de hacerlo.

Para evitar incurrir en el costo del tiempo de cambio de tamaño, muchos arreglos dinámicos cambian el tamaño en una cantidad mayor a la necesaria, por ejemplo duplica su tamaño, dejando así espacio reservado para futuras ampliaciones. La operación de añadir un elemento al final podría funcionar de la siguiente manera:

function insertarAlFinal(dynamicarray a, elemento e)
    // Si es necesario, duplicar el tamaño del arreglo
    if (a.tamaño = a.capacidad)
        a.capacidad ← a.capacidad * 2
    // Copiar el elemento a la ubicación de memoria 
    a[a.tamaño] ← e
    a.tamaño ← a.tamaño + 1

Cuando se intertan n elemento, la capacidad lo hace en progresión geométrica. La expansión del arreglo en cualquier proporción constante asegura que la inserción de elementos de n toma O(n) de tiempo total, lo que significa que cada inserción se amortiza en un tiempo constante. El valor de esta proporción a conduce a una solución del compromiso espacio-tiempo: el tiempo medio por operación de inserción es aproximadamente a/(a−1), mientras que la memoria desaprobechada está limitada superiormente por (a−1)n. La elección de a depende de la librería de funciones usada: algunos libros de texto utilizar a = 2,​​ pero la implementación en Java de un ArrayList utiliza a = 3/2,​ y la implementación en C de la estructura de datos para las listas en Python utiliza a = 9/8.​

Muchos arreglos dinámicos también desasignan parte de su almacenamiento subyacente si su tamaño disminuye por debajo de un cierto umbral, tal como el 30% de la capacidad. Este umbral debe ser estrictamente menor que 1/a con el fin de que las secuencias mixtas de inserciones y eliminaciones tengan un coste constante.

Los arreglos dinámicos son un ejemplo común en la enseñanza del coste y la amortización.​​

Rendimiento y comparación con otras estructuras

Los arreglos dinámicos tienen un rendimiento similar a una arreglo estático, con la adición de nuevas operaciones para añadir y eliminar elementos al final:

• Al obtener o establecer el valor de un índice en particular: Θ(1) (tiempo constante)
• Recorrer sus elementos en orden: Θ(n) (tiempo lineal, buen uso del caché de lectura)
• Insertar o eliminar un elemento no al final del arreglo: Θ(n) (tiempo lineal)
• Insertar o eliminar un elemento al final del arreglo: Θ(1) (tiempo constante amortizado)
• Espacio desperdiciado: Θ(n)​

Los arreglos dinámicos se benefician de muchas de las ventajas de los arreglos estáticos, incluido buena localización por referencia y uso de caché de datos, tamaño reducido (bajo uso de memoria) y capacidad de acceso aleatorio. Por lo general tienen solo una pequeña sobrecarga fija adicional para almacenar información sobre tamaño y capacidad. Esto hace de los areglos dinámicos una herramienta atractiva para la construcción de estructuras de datos amigables y sencillas de usar.

En comparación con las listas enlazadas, los areglos 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 areglos 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. Esta desventaja se ve mitigado usando un gap buffer (buffer de huecos), y variantes escalonadas vectoriales. También, en una región de memoria muy fragmentada, puede ser costoso o imposible encontrar espacio contiguo para ampliar un arreglo dinámico grande, mientras que las listas enlazadas no requieren que la estructura de datos completa se almacene de forma contigua.

Un árbol equilibrado puede almacenar una lista, además de proporcionar las operaciones posibles en arrais 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 arreglos 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.

Variantes

Los Buffers Gap o buffer de huecos, usados sobre todo en procesadores de texto, son similares a los arreglos dinámicos, pero permiten la inserción y eliminación más eficiente en cualquier ubicación arbitraria Algunas implemtaciones de la cola doblemente terminada (en inglés conocidas como DEQUE) utilizan arreglos, lo que permiten un tiempo constante amortizado de inserción/borrado en ambos extremos, en lugar de solo uno de los extremos.

Goodrich​ presentó un algoritmo para arreglos dinámicos al que llamó Vectores por niveles (Tiered Vectors), que proveían una O(n^1/2) en el rendimiento de las inserciones o borrados al preservar el orden de mitad del arreglo.

El árbol hash de arreglos (en inglés Hashed Array Tree o HAT) es un algoritmo de arreglo dinámico publicado por Sitarski en 1996.​ El HAT provee una O(n^1/2) en la cantidad de espacio de almacenamiento, donde n es el número de elementos en el arreglo. El algoritmo tiene O(1) de rendimiento amortizado se añaden una serie de objetos al final de un HAT.

Brodnik y otros, en su documento de 1999​ describen un arreglo dinámico escalonado como estructura de datos, que gasta solo O(n^1/2) de espacio para n elementos en cualquier momento, y demuestran un límite inferior que demuestra que cualquier arreglo dinámico debemos desperdiciar mucho espacio si las operaciones han de permanecer en un tiempo constante amortizado. 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​ presenta en 2002 el algoritmo VList, que puede ser adaptado para implementar un arreglo dinámico.

Implementación en varios lenguajes

• En C++ se usa std::vector, que contiene una implementación de los arreglos dinámicos.
• En Java se usa la clase ArrayList.​
• En .NET Framework se usa la clase ArrayList, la clase genérica List<> suministra con la versión 2.0 del .NET Framework se ejecuta también con arreglos dinámicos.
• En Smalltalk OrderedCollection es un arreglo dinámico, con comienzo y final con índice dinámico, haciendo la eliminación del primer elemento también del O(1).
• En Python el tipo de datos list usa una implementación de datos con un arreglo dinámico.
• En Delphi y [[D (lenguaje de programación)|D] se implementan los arreglos dinámicos en el núcleo del lenguaje.
• En Ada el paquete Ada.Containers.Vectors proporciona una implementación genérica de un arreglo dinámico para un subtipo determinado.
• Muchos lenguajes de script como Perl y Rubí ofrece arreglos dinámicos como tipo de datos primitivo incorporado.
• Varios framework de plataformas cruzadas proporcionar implementaciones de arreglos dinámicos en C, como CFArray y CFMutableArray en Core Fundación para Mac OS X e iOS, o GArray y GPtrArray en GLib para GTK+.

Ejemplos en Java

Para este tipo datos que crecen y decrecen se podría utilizar la clase Vector, pero es más apropiado utilizar la clase Arraylist implementada en el paquete java.util. ArrayList es una de las muchas clases del Collection Framework, que proporciona un conjunto de interfaces y clases bien-diseñados para almacenar y manipular grupos de datos como una sola unidad, una colección.

Existen varios constructores para los Arraylist, que podemos usar dependiendo de como queramos utilizarlo, aunque basicámente se emplean dos:

• ArrayList() construye un ArrayList con capacidad cero por defecto, pero crecerá según le vayamos añadiendo:

ArrayList al = new ArrayList();

• ArrayList(int CapacidadInicial) construye un ArrayList vacío con una capacidad inicial especificada:

ArrayList al2 = new ArrayList(5);

Para insertar un objeto al ArrayList debemos llamar a sus métodos con el operador punto:

 al.add("El manual de Java");    // Añade una cadena
 al.add(new Double(40.00));      // Añade un dato de tipo double de una clase envoltorio (wrapper class)
 System.out.println(al.size());  // Presenta el tamaño del arreglo

Para navegar por los elementos del ArrayList se utiliza la clase Iterator y sus métodos hasNext y next:

 Iterator alIt = al.iterator();
 while (alIt.hasNext()) {
    System.out.println(alIt.next() + " ");
 }