La lección anterior dejó dos preguntas pendientes: ¿por qué acceder a lista[i] cuesta O(1), y qué reorganización oculta hace que append sea O(1) solo amortizado? Para responderlas hay que bajar un nivel: entender cómo se organiza físicamente la memoria del ordenador y qué es un array, la estructura más elemental de todas y el cimiento sobre el que se construyen casi todas las demás. Al terminar sabrás exactamente qué hace la list de Python por dentro, qué operaciones de TaskFlow resuelve bien un array... y cuáles no, lo que nos abrirá la puerta del módulo 2.

1. La memoria como una hilera de casillas numeradas
2. Arrays estáticos: contigüidad y acceso O(1)
3. El precio de la contigüidad: insertar y borrar en medio
4. Arrays dinámicos y redimensionado amortizado
5. La list de Python por dentro (y una mención a array y NumPy)
6. TaskFlow: cuándo basta un array y cuándo se queda corto

Puedes imaginar la memoria RAM de un ordenador como una hilera gigantesca de casillas del mismo tamaño, numeradas consecutivamente. El número de cada casilla es su dirección de memoria, y el procesador puede leer o escribir cualquier casilla con solo conocer su dirección, tarde lo que tarde de encontrarse "lejos": ir a la casilla 4 y a la casilla 40.000.000 cuesta lo mismo. Por eso a esta memoria se la llama RAM: Random Access Memory, memoria de acceso aleatorio (directo).

Dos ideas clave de este modelo:

• Todo dato vive en alguna dirección. Cuando en Python escribes x = 42, en algún lugar de esa hilera queda almacenado el 42, y x es la forma humana de referirse a su dirección. Python te oculta las direcciones (en C se manejan a mano, con punteros), pero puedes asomarte con id(x), que devuelve un identificador basado en la dirección del objeto.
• Acceder por dirección es O(1). Es una operación de hardware: el procesador calcula la dirección y va. No hay búsqueda, no hay recorrido.

Sobre este modelo hay una decisión fundamental que separa dos mundos: guardar los datos contiguos (en casillas seguidas) o dispersos (cada uno donde haya sitio, conectados por referencias). Los arrays apuestan por la contigüidad; las listas enlazadas del módulo 2 apostarán por la dispersión. Toda la lección gira alrededor de las consecuencias de esa apuesta.

Un array estático es un bloque de casillas contiguas reservado de una vez, con un tamaño fijo, donde cada casilla ocupa lo mismo. Es la estructura nativa de lenguajes como C o Java.

La contigüidad tiene un premio enorme. Si el array empieza en la dirección 1000 y cada elemento ocupa 8 bytes, ¿dónde está el elemento de índice i? No hace falta buscarlo: se calcula.

Una multiplicación y una suma, sea i 3 o 3 millones: por eso el acceso por índice es O(1). Esta fórmula es la respuesta a la primera pregunta pendiente de la lección 01-04, y es de las ideas más importantes del curso: el array no busca el elemento i, calcula dónde tiene que estar.

Simulemos un array estático en Python para tocar sus límites (Python no los tiene nativos, así que imponemos las restricciones nosotros):

Puntos del código que merecen atención:

• [None] * capacidad reserva todas las casillas en el momento de la creación: eso es lo que significa "estático". La memoria queda comprometida aunque no se use.
• anadir es O(1)... hasta que el array se llena. Entonces no hay nada que hacer: OverflowError. Un array estático no crece.
• Distinguimos _capacidad (casillas reservadas) de _usados (casillas con datos reales). Esta distinción parece menor ahora, pero es la clave del apartado de arrays dinámicos.

Ventaja adicional de la contigüidad que conviene conocer: los procesadores modernos leen la memoria por bloques (caché), de modo que recorrer datos contiguos es aún más rápido en la práctica que recorrer datos dispersos: al leer el elemento 0, los siguientes ya vienen "de regalo" en el mismo bloque.

Todo lo que la contigüidad regala en el acceso lo cobra en las modificaciones. Piensa en una fila de asientos llenos en un cine: si alguien quiere sentarse en medio, todos los de un lado tienen que correrse un asiento.

Insertar en la posición i de un array exige desplazar una casilla a la derecha todos los elementos desde i hasta el final:

Borrar la posición i es el movimiento inverso: los elementos posteriores se desplazan a la izquierda para no dejar hueco (la contigüidad no admite agujeros).

El coste, con el vocabulario de la lección anterior:

Fíjate en la asimetría que define al array: espléndido leyendo y modificando por posición, caro reorganizando. Insertar al principio es el caso más doloroso: todos los elementos se mueven.

El array estático tiene un problema práctico evidente: hay que adivinar el tamaño por adelantado. ¿Cuántas tareas tendrá un usuario de TaskFlow? ¿100? ¿100.000? Quedarse corto es fatal (OverflowError) y pasarse desperdicia memoria.

El array dinámico resuelve el dilema con una estrategia elegante:

1. Empieza con un array estático de cierta capacidad.
2. Mantiene la cuenta de casillas usadas frente a capacidad total (nuestros _usados y _capacidad).
3. Cuando un append encuentra el array lleno: reserva un array nuevo más grande (típicamente el doble o similar), copia todos los elementos al nuevo y libera el viejo.

El paso de copia cuesta O(n), y aquí aparece la respuesta a la segunda pregunta pendiente de la lección 01-04. ¿Por qué append es O(1) amortizado y no O(n)? Por la política de duplicar la capacidad: tras una copia de n elementos, quedan n casillas libres, es decir, los siguientes n append serán O(1) garantizado. El coste O(n) de la copia, repartido entre esos n append baratos, sale a O(1) extra por operación.

Contémoslo con números para que no quede en palabras: partiendo de capacidad 1, hacer 8 append provoca copias de 1, 2 y 4 elementos (al llenar las capacidades 1, 2 y 4): 7 copias en total para 8 inserciones, menos de una copia por append. Con 1.024 append, las copias suman 1.023: sigue saliendo a ~1 por operación. El promedio no crece con n: eso es O(1) amortizado, exactamente la definición que dimos en la lección anterior.

La contrapartida honesta: un append concreto (el que dispara la copia) sí puede ser lento, y el array dinámico mantiene casillas de sobra reservadas (memoria extra de hasta el doble de lo usado). Flexibilidad a cambio de picos puntuales y algo de memoria: otro intercambio de los que ya sabes reconocer.

La gran revelación de esta lección: la list de Python es exactamente eso, un array dinámico. No es una "lista enlazada" pese a su nombre (ese será justo el tema del módulo 2, y la confusión de nombres es una trampa clásica). Ahora toda la tabla de costes que dimos en la lección 01-04 tiene explicación física:

Un matiz técnico que conviene conocer: como una list puede mezclar tipos y los objetos de Python tienen tamaños distintos, las casillas del array no contienen los objetos en sí, sino referencias (direcciones) a ellos, todas del mismo tamaño; por eso la fórmula del acceso sigue funcionando. Y la política de crecimiento de CPython no es duplicar exactamente, sino crecer ~1,125× con un margen adicional; el análisis amortizado se mantiene con cualquier crecimiento proporcional.

Podemos incluso observar el redimensionado desde fuera con sys.getsizeof, que da los bytes que ocupa el objeto:

Salida típica (varía según la versión de Python):

El tamaño no crece con cada append, sino a saltos: cada salto es una reserva de capacidad extra, y entre salto y salto los append no piden memoria. Es el redimensionado amortizado visto en directo.

Dos parientes de la list que conviene conocer, solo como mención:

• array.array (módulo de la biblioteca estándar): array dinámico homogéneo que guarda los números en sí (no referencias), ahorrando bastante memoria cuando tienes millones de valores del mismo tipo.
• NumPy (numpy.ndarray): la librería estándar del cálculo numérico; arrays homogéneos, compactos y con operaciones vectorizadas enormemente rápidas. Si algún día TaskFlow calculara estadísticas sobre millones de registros de tiempos, NumPy sería la herramienta. Queda fuera de este curso, pero debes saber que existe y que por dentro es... un array contiguo, como todo lo de esta lección.

Cerremos aplicando el criterio a nuestro proyecto. El tablero de TaskFlow, versión array (list):

Para estos tres usos —añadir al final, listar en orden, acceder por posición— la list es la elección correcta, y ninguna estructura del curso la superará en ellos. Que sea la primera opción por defecto en Python está justificado.

Pero mira lo que pasa con otros dos casos de uso reales de TaskFlow:

Con 50 tareas, nada de esto importa. Pero imagina la lista de actividad global de un TaskFlow corporativo con cientos de miles de entradas donde lo normal es insertar por delante y borrar por el medio: cada operación desplazaría cientos de miles de referencias. El diagnóstico, con el vocabulario que ya dominas:

¿Y si existiera una estructura donde insertar o borrar en medio no desplazara nada, porque los elementos no viven contiguos sino enlazados unos a otros, cada uno donde le haya tocado en memoria? Existe: es la lista enlazada, la otra gran apuesta —dispersión en lugar de contigüidad— y el tema del módulo 2. Como es de justicia, tendrá sus propios costes: al perder la contigüidad se pierde la fórmula mágica del acceso O(1). No hay almuerzo gratis; hay elecciones informadas.

• Creer que la list de Python es una lista enlazada. El nombre engaña: es un array dinámico. Este malentendido lleva a asumir que insertar al principio es barato, cuando es O(n). En el módulo 2 la comparación quedará cristalina.
• Usar lista.insert(0, x) o lista.pop(0) dentro de bucles. Es el O(n²) accidental más común de Python: n operaciones O(n). Si necesitas añadir y quitar por delante habitualmente, existe una estructura pensada para ello (collections.deque, que estudiaremos en el módulo 4).
• Alarmarse por el pico del redimensionado. Que un append ocasional cueste O(n) casi nunca es un problema real: el amortizado O(1) es lo que cuenta en la práctica. Solo en sistemas con restricciones estrictas de latencia importan los picos.
• Ignorar la memoria de reserva. Un array dinámico puede tener hasta el doble de casillas de las que usa. Con millones de elementos numéricos, array.array o NumPy reducen drásticamente el consumo frente a list.
• Consejo: ante cualquier estructura nueva, pregunta siempre "¿es contigua o dispersa por dentro?". La respuesta te dirá, sin mirar documentación, qué operaciones serán baratas (acceso si es contigua; reorganización si es dispersa) y cuáles caras.

Un array de enteros de 8 bytes comienza en la dirección 5000. (a) ¿En qué dirección está el elemento de índice 12? (b) Si un elemento está en la dirección 5096, ¿qué índice tiene? (c) Explica en una frase por qué esta fórmula deja de funcionar si los elementos ocuparan tamaños distintos.

Partiendo del array [10, 20, 30, 40, 50] (capacidad 8, 5 casillas usadas), indica cuántos elementos se desplazan en cada operación y el estado final del array tras aplicarlas en orden: (a) insert(0, 5); (b) append(60); (c) borrar el elemento de índice 2; (d) insert(3, 35).

Escribe un programa que compare con timeit construir una lista de 50.000 elementos de dos maneras: (a) con append (añadiendo al final) y (b) con insert(0, x) (añadiendo al principio). Predice antes de ejecutar cuál será más lenta y por qué, y comprueba si la diferencia crece al pasar a 100.000 elementos.

Solución 1:

• (a) 5000 + 12 × 8 = 5096.
• (b) (5096 − 5000) / 8 = 12: el mismo elemento del apartado anterior, calculado a la inversa.
• (c) La fórmula multiplica el índice por un tamaño fijo; con tamaños variables no se puede calcular dónde empieza el elemento i sin recorrer y sumar los tamaños de todos los anteriores (por eso la list de Python guarda referencias de tamaño fijo a los objetos, no los objetos en sí).

Solución 2:

• (a) insert(0, 5): se desplazan los 5 elementos → [5, 10, 20, 30, 40, 50].
• (b) append(60): se desplazan 0 (hay hueco libre, capacidad 8) → [5, 10, 20, 30, 40, 50, 60].
• (c) borrar índice 2 (el valor 20): se desplazan a la izquierda los 4 posteriores → [5, 10, 30, 40, 50, 60].
• (d) insert(3, 35): se desplazan los 3 elementos desde el índice 3 → [5, 10, 30, 35, 40, 50, 60].

Moral del ejercicio: el coste de cada operación depende de cuántos elementos quedan a la derecha del punto de modificación; por eso el peor caso es siempre el principio.

Solución 3:

Predicción: la versión (b) será mucho más lenta, porque cada insert(0, x) desplaza todos los elementos ya presentes: el coste total es 0 + 1 + 2 + ... + (n−1) ≈ n²/2 desplazamientos, es decir, O(n²); la versión (a) es n append de O(1) amortizado, o sea O(n) total.

Resultado típico: con 50.000 elementos, append tarda milésimas y insert(0, ...) del orden de segundos; al duplicar a 100.000, append se duplica (lineal) pero insert(0, ...) se cuadruplica (cuadrática), confirmando la predicción. Es la física del array —los desplazamientos— manifestándose exactamente como la teoría anuncia.

Has llegado al fondo del asunto: la memoria es una hilera de casillas numeradas de acceso directo, y el array —datos contiguos, casillas iguales— explota esa organización para ofrecer acceso por índice O(1) mediante una simple fórmula, pagándolo con desplazamientos O(n) al insertar o borrar en medio. Los arrays dinámicos añaden crecimiento automático con redimensionado proporcional, cuyo coste repartido da el famoso append O(1) amortizado; y la list de Python es exactamente eso, con array.array y NumPy como variantes compactas para datos numéricos masivos. Para TaskFlow, el array es perfecto como tablero que crece por el final y se lee en orden, y se queda corto cuando abundan las inserciones y borrados por delante o por el medio.

Con esto se cierra el módulo 1: ya sabes qué es una estructura de datos, por qué importa elegirla bien, qué familias existen, cómo medir su eficiencia con Big O y sobre qué base física se construye todo. En el módulo 2 empezamos a construir de verdad: la lista enlazada, la primera estructura que fabricaremos desde cero, que renuncia a la contigüidad precisamente para hacer baratas las operaciones donde el array flaquea, y que convertiremos en el tablero de tareas definitivo de TaskFlow.