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 esn dos partes: la primera es la parte ocupada de del arreglo y la segunda está libre para au 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 arrglo subyacente es una tarea costosa, implicando típicamente copiar el contenido del arerglo 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 reutilziados, 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 sólo 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 las matrices dinámicas, pero permiten la inserción y eliminación mas eficiente en cualquier ubicación arbitraria Algunas implemtaciones de Cola doblemente terminadaCola 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 sólo uno de los extremos.

Goodrich ​ ​

​

presentó un algoritmo llamado matriz dinámica Vectores por niveles que proveían O (n 1/2) el rendimiento de las inserciones o deleciones de preservar el orden de la mitad de la matriz.

Árbol de matriz hash (HAT) es un algoritmo de matriz dinámica publicado por Sitarski en 1996. [10] Tree Hashed matriz de desechos orden n 1/2 la cantidad de espacio de almacenamiento, donde n es el número de elementos en la matriz. El algoritmo tiene O (1) el rendimiento amortizado cuando añadiendo una serie de objetos al final de un árbol de matriz Hashed.

En un documento de 1999, [8] Brodnik et al. describir una matriz dinámica con gradas estructura de datos, que gasta sólo n 1/2 espacio de n elementos en cualquier punto en el tiempo, y demuestran un límite inferior que muestra que cualquier matriz dinámica debemos desperdiciar tanto espacio si las operaciones han de permanecer constante de tiempo amortizado . Además, presentan una variante donde crece y encoge el tampón tiene no sólo el tiempo constante amortizado pero peor de los casos.

Bagwell (2002) [11] presenta la VList algoritmo, que puede ser adaptado para implementar una matriz dinámica.

En Java

Se utilizan los Arraylist. Para este tipo de grupos de datos que crecen y decrecen se podría utilizar la clase Vector, pero es más frecuente utilizar la clase Arraylist implementada en el paquete "java.util". La ventaja de un Arraylist es que contiene tantos objetos como el programador necesite.

Los constructores de un Arraylist son varios, siempre dependiendo de como queramos utilizar el Arraylist, aunque basicámente se utilizan dos:

• ArrayList() construye un ArrayList con capacidad cero por defecto, pero crecerá según le vayamos añadiendo:
  • ArrayList al = new ArrayList();
• ArrayList(int initialCapacity) 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("Java Technology Book"); //adds a String al.add(new Double(40.00)); //adds a double in a class wrapper System.out.println(al.size()); //prints the size of //the ArrayList

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() + " "); }

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.