Arrays: la estructura de datos más fundamental

El array es la estructura de datos más antigua, más simple y más usada de la programación. Casi cualquier otra estructura —listas, pilas, colas, tablas hash— se implementa por debajo usando arrays. Entender cómo funcionan por dentro es imprescindible, no solo para saber cuándo usarlos, sino para entender por qué muchas otras estructuras se comportan como se comportan.

Este artículo abre la Serie 2: Por dentro de las estructuras. Asumimos que ya tienes claros los conceptos de iteración, recursión y, sobre todo, stack vs heap que cubrimos en la serie anterior.

Explicación conceptual

Un array es una colección de elementos del mismo tipo almacenados de forma contigua en memoria. Cada elemento tiene una posición numérica (el índice) que va desde 0 hasta longitud - 1. El detalle clave es "contigua": los elementos viven uno tras otro en el mismo bloque de memoria, sin huecos.

Esa contigüidad habilita el superpoder del array: acceso por índice en O(1). Si sabes dónde empieza el array (la dirección base) y el tamaño de cada elemento, la dirección del índice i es simplemente:

dirección(arr[i]) = base + i * tamaño_elemento

El procesador hace una multiplicación y una suma. No importa si el array tiene 10 elementos o 10 millones: el acceso cuesta lo mismo.

Ejemplo gráfico

La imagen destacada ilustra la idea: cinco casillas consecutivas con índices de 0 a 4 y valores dentro. arr[2] se accede saltando directamente a la tercera casilla, sin recorrer las anteriores. Esa "aleatoriedad" en el acceso es lo que distingue al array de la lista enlazada que veremos en el siguiente artículo.

Implementación en PHP

PHP tiene una peculiaridad: lo que llamamos "array" en PHP es en realidad un hashmap ordenado bajo el capó. No es un array en el sentido estricto de C o Java. Pero para efectos prácticos, cuando usas índices numéricos enteros se comporta como un array clásico.

// Array indexado clásico
$nums = [10, 20, 30, 40, 50];

// Acceso O(1)
echo $nums[2]; // 30

// Iteración con índice
for ($i = 0; $i < count($nums); $i++) {
    echo $nums[$i] . "\n";
}

// Iteración con foreach
foreach ($nums as $valor) {
    echo $valor . "\n";
}

// Longitud
$n = count($nums);

// Agregar al final
$nums[] = 60;          // ahora [10, 20, 30, 40, 50, 60]
array_push($nums, 70); // equivalente

// Insertar en una posición
array_splice($nums, 2, 0, [99]); // inserta 99 en posición 2

Si necesitas un array "real" de tipo fijo, PHP ofrece la extensión SPL con SplFixedArray, que es más rápido y usa menos memoria que el array asociativo por defecto cuando manejas muchos datos.

$arr = new SplFixedArray(5);
$arr[0] = 10;
$arr[1] = 20;
// no acepta claves string, siempre índices enteros 0..n-1

Implementación en Java

En Java los arrays son ciudadanos de primera clase y siguen el modelo clásico: tamaño fijo al crearse, tipo homogéneo, acceso por índice.

// Declaración e inicialización
int[] nums = new int[5];          // crea un array de 5 enteros, todos 0
int[] inits = {10, 20, 30, 40, 50}; // con valores iniciales

// Acceso O(1)
System.out.println(nums[2]);

// Longitud (no es método, es atributo)
int n = nums.length;

// Iteración clásica
for (int i = 0; i < nums.length; i++) {
    nums[i] = i * 10;
}

// for-each (solo lectura)
for (int v : nums) {
    System.out.println(v);
}

Java también ofrece ArrayList, que es un array dinámico: internamente mantiene un array clásico, y cuando se llena lo recrea con mayor capacidad. Es lo que usas el 90% de las veces que necesitas "una lista de cosas".

List<Integer> lista = new ArrayList<>();
lista.add(10);
lista.add(20);
lista.add(30);
int x = lista.get(1); // 20

El ArrayList te ahorra la gestión manual del tamaño, al costo de un resize ocasional cuando se llena (detalles en la sección de complejidad).

Operaciones básicas

Inserción

• Al final: si hay espacio, O(1). Si es un ArrayList lleno, hay que redimensionar, que es O(n) puntual pero amortizado O(1).

• En una posición arbitraria: hay que desplazar todos los elementos posteriores una posición a la derecha. O(n).

// Insertar 99 en posición 2, ArrayList de 5 elementos
// Antes: [10, 20, 30, 40, 50]
lista.add(2, 99);
// Después: [10, 20, 99, 30, 40, 50] — 3 elementos se desplazaron

Búsqueda

• Si sabes el índice: O(1), acceso directo.

• Si buscas un valor (búsqueda lineal): O(n), recorrer uno por uno hasta encontrarlo.

• Si el array está ordenado (búsqueda binaria): O(log n). Veremos búsqueda binaria en el artículo dedicado de la Serie 3.

Eliminación

Similar a inserción: eliminar un elemento en posición i implica correr todos los posteriores una posición a la izquierda. O(n).

lista.remove(2); // elimina el elemento en posición 2
// elementos posteriores se desplazan a la izquierda

Eliminar el último elemento es O(1) porque no hay nada que desplazar.

Complejidad (Big-O)

OperaciónArray fijoArrayList dinámicoAcceso por índiceO(1)O(1)BúsquedaO(n)O(n)Inserción al final—O(1) amortizadoInserción en medio—O(n)Eliminación al final—O(1)Eliminación en medio—O(n)EspacioO(n)O(n)

"Amortizado" en la inserción al final significa que, aunque algunas inserciones individuales son O(n) (cuando hay que hacer resize), el promedio a lo largo de muchas inserciones es O(1). La heurística típica: cuando el array se llena, se crea uno nuevo con el doble de capacidad y se copian los elementos.

Ventajas y desventajas

Ventajas:

• Acceso aleatorio O(1) que ninguna otra estructura tan simple ofrece.

• Alta localidad de caché: elementos consecutivos viven cerca en RAM, lo que acelera mucho los recorridos en procesadores modernos.

• Consumo mínimo de memoria extra: no hay punteros ni overhead de estructura.

Desventajas:

• Inserción y eliminación en medio son O(n).

• Tamaño fijo en Java (los arrays primitivos). Para crecer necesitas un ArrayList y pagar el costo del resize ocasional.

• No se pueden insertar elementos a la izquierda eficientemente (también O(n)).

Casos de uso reales

• Cualquier lista de "cosas" donde el acceso aleatorio sea común y las inserciones en medio sean raras: una lista de productos, una colección de usuarios.

• Buffers de entrada/salida: leer N bytes de un archivo a un byte[].

• Implementación de otras estructuras: pilas y colas se implementan típicamente sobre arrays.

• Cálculo numérico y machine learning: arrays de double o float son la representación natural para vectores y matrices.

• Cacheline-friendly data: en código de alto rendimiento, un array de structs supera cualquier diseño con punteros porque minimiza los fallos de caché.

Cómo se recorre

Hay varias formas, con pequeños trade-offs entre ellas:

// 1. for clásico con índice: útil cuando necesitas el índice o modificar in-place
for (int i = 0; i < arr.length; i++) {
    arr[i] = transformar(arr[i]);
}

// 2. for-each: más limpio cuando solo lees
for (int v : arr) {
    procesar(v);
}

// 3. Streams: funcional, permite chaining y operaciones paralelas
Arrays.stream(arr).map(x -> x * 2).forEach(System.out::println);

En PHP:

// foreach simple
foreach ($nums as $v) { procesar($v); }

// foreach con índice
foreach ($nums as $i => $v) {
    echo "$i: $v\n";
}

// Funcional
$doblados = array_map(fn($x) => $x * 2, $nums);

Cómo se vería en memoria

Un array de int en Java de tamaño 5 ocupa en heap:

┌──────────────────────────────────────────────┐
│ header │ length=5 │ 10 │ 20 │ 30 │ 40 │ 50 │
└──────────────────────────────────────────────┘

El "header" incluye metadatos del objeto (tipo, lock, hash, etc.), seguido de la longitud, y luego los 5 enteros consecutivos (4 bytes cada uno). La referencia int[] arr que está en el stack apunta al inicio de este bloque.

Un array de Integer (boxed), en cambio, no guarda los enteros sino referencias a objetos Integer que viven en otras partes del heap:

stack: arr → heap: [ref0, ref1, ref2, ref3, ref4]
                    ↓     ↓     ↓     ↓     ↓
                 Integer  Integer ... (objetos en heap, dispersos)

Este patrón es mucho más lento que int[] porque pierde localidad de caché. En código crítico de rendimiento, prefiere siempre el primitivo.

En PHP, los arrays son una estructura más pesada (HashTable interna) que incluye una tabla de hash, un bucket por cada elemento y metadatos para mantener el orden de inserción. Es cómodo (clave o índice, mismo mecanismo) pero usa más memoria que un array de C.

Errores comunes

1. ArrayIndexOutOfBoundsException

En Java, acceder a arr[i] con i < 0 o i >= arr.length tira esta excepción. Típicamente causado por un off-by-one en el bucle.

En PHP, acceder a un índice inexistente no tira excepción sino que retorna null y genera un warning. Lo cual es aún peor, porque el bug se camufla.

2. Confundir array asociativo con array indexado en PHP

En PHP $arr = [] crea una estructura que puede funcionar como array o como diccionario. Si mezclas claves numéricas y strings, la indexación se vuelve impredecible:

$arr = [];
$arr[0] = "a";
$arr["uno"] = "b";
$arr[] = "c"; // ¿qué índice toma? (spoiler: 1)

Si necesitas estrictamente un array indexado, valida con array_is_list() (PHP 8.1+) o usa SplFixedArray.

3. Redimensionar un ArrayList en un bucle de inserciones

Cada resize copia todo el array. Si agregas 100,000 elementos sin pre-dimensionar, harás varios resizes innecesarios. Pasar la capacidad estimada al constructor ahorra trabajo:

List<Integer> lista = new ArrayList<>(100_000);

4. Usar arrays para búsquedas frecuentes

Si tu caso de uso es "insertar una vez, buscar muchas veces por valor", un array requiere O(n) por búsqueda. Una tabla hash haría O(1). Reconocer este patrón es clave para escalar.

5. Modificar un array mientras lo iteras

Como vimos en el artículo de iteración, eliminar o agregar elementos durante un for-each rompe la invariante del iterador. En Java tira ConcurrentModificationException; en PHP el comportamiento es impredecible. Si necesitas modificar, itera con índice clásico o construye una lista nueva.

Resumen

El array es la estructura de datos más básica: una secuencia contigua en memoria con acceso por índice en O(1). Su simplicidad y su excelente localidad de caché lo hacen insuperable para casos donde el acceso aleatorio domina.

En Java son tamaño fijo, pero ArrayList añade crecimiento dinámico con O(1) amortizado al insertar al final. En PHP, los "arrays" son en realidad tablas hash ordenadas con más overhead pero mayor flexibilidad.

Las operaciones en medio (inserción y eliminación) son O(n) porque requieren desplazar elementos. Si tu carga de trabajo hace muchas inserciones/eliminaciones en posiciones arbitrarias, el array no es la mejor elección. En el siguiente artículo vemos la alternativa: las listas enlazadas.