Esvdev Blog

¿Qué son los arrays?

Los arrays (arreglos) son una de las estructuras de datos más simples y más utilizadas. Es de tipo lineal, lo que quiere decir que sus elementos se encuentran ordenados de manera secuencial y adyacente (osea, uno al lado del otro). Son generalmente homogéneos, por lo que sus valores son del mismo tipo de dato. En algunos lenguajes, como JavaScript y Python, se permite la declaración de arrays con distintos tipos de datos. Sin embargo, esto no sucede en la mayoría de lenguajes de programación. Veamos un ejemplo en código:

// JavaScript
const listaNumeros = [4, 6, 77, 1, 0];
const listaTripulacion = ["Luffy", "Zoro", "Sanji"];

A cada elemento del array se le asigna un valor numérico positivo llamado “índice”, que nos permitirá acceder a cada valor almacenado ya que dicho índice se corresponde con la posición del elemento en el array. En otras palabras, el índice actúa como un identificador del elemento en cuestión. Para referirnos a dicho índice utilizamos la forma array[posición_índice].

console.log(listaTripulacion[0]); // Luffy
console.log(listaTripulacion[1]); // Zoro
console.log(listaTripulacion[2]); // Sanji

Si tomamos como ejemplo el array llamado “listaTripulacion” vemos que contiene 3 elementos. En la mayoría de lenguajes de programación se define el índice inicial con un 0. Por lo que si consultamos el índice 0, obtendremos el string “Luffy” (el futuro rey de los piratas). El índice 1 devolverá “Zoro” y el índice 2 nos dará como resultado “Sanji”.

💡 Para tener en mente: el primer elemento del array siempre tendrá 0 como índice. El último elemento siempre tendrá como índice la cantidad total de elementos del array menos 1. Es decir, un array con 5 elementos tendrá índices que van del 0 al 4.

Existen, a su vez, dos tipos de arreglos. Los arrays unidimensionales, también conocidos como vectores, y los arrays multidimensionales, también conocidos como matrices.

💡 Los strings, o cadena de caracteres, son un tipo particular de array ya que también son una colección ordenada de elementos, pero acotado a caracteres. Por ejemplo, la cadena “Hola” es una colección ordenada formada por los caracteres “H”, “o”, “l”, “a”. Es por esta razón que la forma de abordar arrays y strings generalmente será la misma. Los problemas que se presenten con ellos son casi siempre intercambiables.

Casos de uso

Los arrays son utilizados prácticamente en todas las situaciones donde se necesita organizar datos del mismo tipo, sean estos datos recibidos mediante una API o enviados a una base de datos. Los arrays también pueden ser enviados como argumento a una función o método. Otro ejemplo es el procesamiento de imágenes, donde se utilizan arrays bidimensionales (matrices). Adicionalmente, los arrays son utilizados para implementar otras estructuras de datos.

Uso de memoria

Saber qué ocurre en la memoria de nuestra computadora cuando estamos trabajando con arrays es un aspecto importante a tener presente, ya que mejora nuestra comprensión del funcionamiento interno de esta estructura de datos.

En lenguajes de alto nivel como JavaScript o Python no es necesario que nos encarguemos del manejo de memoria cuando trabajamos con un array ya que el lenguaje se encarga por nosotros. Esto es conocido como “abstracción”, ya que nos ahorra tener que lidiar con ese tipo de operaciones por nuestra cuenta.

A grandes rasgos, podríamos decir que la memoria es como un contenedor de datos dividido en regiones. En cada una de estas regiones pueden estar guardadas (temporalmente) las distintas actividades que la computadora está ejecutando al mismo tiempo. A medida que se vayan añadiendo elementos (osea, más actividades), la memoria los va guardando en las regiones que están libres.

Cuando creamos un array, lo primero que se necesita hacer es localizar y “separar” un espacio en memoria donde el array pueda vivir. Recordemos que estos espacios o regiones de memoria tienen que ser adyacentes o contiguos, no pueden estar separados o esparcidos.

A medida que el array crezca, más espacio en memoria ocupará. Pero incluso cuando creamos un array vacío, es necesario separar el espacio en memoria en base a la cantidad de elementos que tendrá el array cuando lo definimos. Por ejemplo, si definimos un array que tendrá 5 elementos en su interior, internamente en nuestra memoria ocurre algo como esto:

A continuación añadimos los numeros 1, 5 y 9 al array, ocupando 3 de sus 5 espacios que hemos separado en memoria. Como es obvio, a medida que añadamos más elementos iremos ocupando los espacios que quedan.

Ahora bien, ¿qué ocurre cuando añadimos un elemento al array después de haber ocupado todos los espacios que hemos separado en memoria? Hemos agotados los 5 espacios y no hay memoria adyacente/contigua para seguir guardando elementos.

He aquí la respuesta: para seguir expandiendo el array, el sistema operativo irá en búsqueda de una sección de memoria con espacios adyacentes hacia donde copiar/mover el array. Esta sección tendrá el mismo espacio disponible que ocupaba el array originalmente (5 espacios) y espacio de sobra en caso de necesitar expandir el array aún más.

Como es de suponer, esta operación no es barata ya que hay que mover todos los elementos a nuevas posiciones. Luego de esto, ahora sí que podemos añadir más elementos a nuestro array ya que contamos con una nueva sección de memoria disponible para hacerlo. La sección anterior queda liberada para que otros recursos/elementos puedan ocupar ese lugar.

Tal como se mencionó anteriormente, la mayoría de lenguajes de alto nivel nos ahorran todo este proceso, pero las implicaciones en cuanto a rendimiento cuando expandimos el array más allá de la sección de memoria separada son las mismas.

Complejidad algorítmica

A continuación veremos el tipo de complejidad algorítmica que tiene esta estructura de datos según la operación que se quiera realizar.

Si no te acordás muy bien el tema del Big O (o si nunca leíste al respecto), te comparto el post donde hablo de esta notación tan utilizada para medir la complejidad de un algoritmo.

Acceso
- Acceder a un elemento mediante índice: O(1) - tiempo constante. Esto se debe a que los elementos son almacenados en posiciones de memoria contiguas.
Inserción
- Insertar elemento al final del array: O(1) - tiempo constante. Añadir un elemento al final del array es sencillo y eficiente (particularmente cuando el array tiene suficiente capacidad de memoria adyacente), ya que el nuevo elemento obtiene el índice que sigue en la secuencia. Si un array tiene 5 elementos, el nuevo elemento será el sexto, y así sucesivamente.
- Insertar elemento al principio o mitad del array: O(n) - lineal. Para realizar esta operación es necesario ordenar el array primero, lo que lleva a dicha complejidad. O incluso si el array está ordenado, cuando se inserta un elemento al principio o a la mitad, es necesario reacomodar los elementos restantes y sus respectivos índices. A mayor cantidad de elementos a recomodar, más lenta la operación. Insertar un elemento al principio es el peor caso, ya que hay que reacomodar todos los elementos del array para "hacer espacio" al elemento que irá al principio.
Búsqueda
- Buscar elemento en array desordenado: O(n) - lineal. En el peor de los casos, será necesario recorrer todo el array hasta encontrar el elemento deseado.
- Buscar elemento en array ordenado: O(log n) - complejidad logarítmica. Si el array se encuentra ordenado (ya sea alfabéticamente, numéricamente, etc), puede aplicarse el algoritmo de búsqueda binaria. Dicho algoritmo posee la complejidad mencionada.
Eliminación
- Al igual que insertar elementos, la complejidad de eliminar elementos en un array estará determinada por la posición del elemento que deseamos eliminar. Eliminar un elemento al final del array tendrá una complejidad constante (O(1)), mientras que si el elemento está al principio o a la mitad del array, tendremos complejidad lineal (O(n)).

Recursos

En esta sección te comparto algunos recursos y ejercicios para que puedas profundizar sobre los arrays y sus diferentes particularidades.

Conclusión

Incluso si llevas poco tiempo aprendiendo programación, es más que probable que te hayas cruzado con esta estructura de datos. Sin embargo, ahora contás con un conocimiento más profundo sobre su funcionamiento, la complejidad de sus operaciones e incluso los distintos tipos de arrays con los que podés encontrarte. ¡Felicitaciones!

Espero que este breve resúmen haya aportado a tu conocimiento. Si encontraste este artículo en Google o te lo compartieron, te invito a pasarte por el "artículo central" sobre Estructuras de datos, ya que allí también encontrarás enlaces a futuros artículos que iré publicando al respecto.

Fuentes:

Estructuras de datos II - Arrays