Buffers y dynamic arrays

Cuando escribes arr.append(x) en Python o arr.push(x) en JavaScript, la operación es O(1) amortizado. Pero adentro pasa mucho más de lo que parece.

Qué hay detrás de una "lista"

Una lista de Python o un Array de JS NO es una lista enlazada. Es un arreglo dinámico: un bloque contiguo de memoria que puede redimensionarse.

La estructura tiene tres campos invisibles:

1. Puntero al buffer: dirección del bloque de memoria.
2. Largo: cuántos elementos efectivos hay.
3. Capacidad: cuántos elementos podrían caber sin redimensionar.

Cuando haces append, normalmente solo aumenta el largo en 1 y asigna el elemento en buffer[largo]. Eso es O(1) puro.

El problema aparece cuando el largo iguala la capacidad: no hay espacio. Ahí pasa lo costoso.

Redimensionado

Cuando el buffer se llena, el lenguaje:

1. Pide al sistema operativo un buffer nuevo, más grande (típicamente al doble).
2. Copia todos los elementos del viejo al nuevo. Esto es O(n).
3. Libera el buffer viejo.
4. Apunta buffer al nuevo.

Una vez hecho, los próximos appends vuelven a ser O(1) hasta llenar el nuevo buffer.

Por qué duplicar

Si la lista creciera de a 1 cada vez que se llena, el costo total de n appends sería 1 + 2 + 3 + ... + n ≈ n²/2 → O(n²) total. Cada append sería O(n) amortizado. Inaceptable.

Con duplicación, las copias suceden en los inserts 1, 2, 4, 8, ..., n. Total: 1 + 2 + 4 + ... + n ≈ 2n. El costo de n inserts es O(n), y cada uno es O(1) amortizado.

En Python específicamente

Python no duplica exactamente al doble. Usa una fórmula que añade ~12.5% del tamaño actual:

nueva_capacidad = (capacidad_actual >> 3) + (3 si chico, 6 si grande) + capacidad_actual

Resultado parecido: O(1) amortizado, con un poco más de eficiencia de memoria que duplicar puro.

En JavaScript

Distinto según motor (V8, JavaScriptCore, etc.) pero todos hacen una estrategia exponencial parecida a duplicar. V8 (Chrome, Node) duplica con un factor de aproximadamente 1.5.

Inserción en el medio

arr.insert(i, x) en Python (o arr.splice(i, 0, x) en JS) NO es O(1). Es O(n) en general.

Para insertar en la posición i, todos los elementos desde i hasta el final tienen que moverse una posición a la derecha. Eso es n - i operaciones.

arr = list(range(1000000))
arr.insert(0, -1)  # O(n) - mueve 1 millón de elementos
arr.insert(500000, x)  # O(n) - mueve 500.000
arr.append(x)  # O(1) amortizado - no mueve nada

Si vas a insertar muchas veces al principio, usa una collections.deque en Python o una estructura especializada. Las inserciones en ambos extremos son O(1) en deque.

Eliminación

arr.pop() (sin índice) elimina el último elemento. O(1).

arr.pop(0) o arr.shift() en JS elimina el primero. O(n) porque todos los siguientes se corren a la izquierda.

arr.pop(i) o arr.splice(i, 1) elimina del medio. O(n).

del arr[i] en Python también es O(n).

Si necesitas "cola" con remove al frente, usa deque. Si necesitas eliminar arbitrariamente, considerar set o dict según el caso.

Pre-asignar tamaño

Cuando sabes cuántos elementos vas a tener, conviene pre-asignar para evitar redimensionados:

# En vez de:
arr = []
for i in range(n):
    arr.append(i * 2)

# Haz:
arr = [0] * n
for i in range(n):
    arr[i] = i * 2

En la primera versión, Python redimensiona log(n) veces. En la segunda, asigna n posiciones de una vez. Diferencia de 2-3× en performance para n grandes.

En JS:

const arr = new Array(n);
for (let i = 0; i < n; i++) {
  arr[i] = i * 2;
}

Cuándo NO usar arrays dinámicos

Casos donde la estructura no es la mejor:

• Inserciones/borrados frecuentes en el medio: lista doblemente enlazada (collections.deque para muchos casos, o estructura propia).
• Búsqueda por valor frecuente: hash set.
• Mantener orden y consultas por rango: árbol balanceado (raro en problemas pero existe).
• Cola FIFO: deque, no lista.

Resumen práctico

Operación	Costo
arr[i]	O(1)
arr.append(x) / arr.push(x)	O(1) amortizado
arr.pop()	O(1)
arr.insert(i, x)	O(n)
arr.pop(0) / arr.shift()	O(n)
len(arr) / arr.length	O(1)
arr[i:j] (slice)	O(j - i)
x in arr	O(n)
arr.sort()	O(n log n)

Memorizar esta tabla mental te ahorra muchos bugs de complejidad en entrevistas. Si tu código hace arr.insert(0, ...) dentro de un loop, ya sabes que es O(n²).