El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Cómo Elegir la Estructura de Datos Adecuada

Siguiente ►
►

Al final del módulo anterior dimos el curso por completo en cuanto a estructuras: TaskFlow ya tiene tablero (arrays y listas), deshacer (pilas), notificaciones (colas y montículos), índices (tablas hash), jerarquías (árboles) y dependencias (grafos). Ahora toca el paso que separa a quien "conoce estructuras" de quien "diseña con estructuras": aprender a elegir. En esta lección construiremos un método de decisión en forma de preguntas, reuniremos toda la materia en una gran tabla comparativa y razonaremos en voz alta varios casos prácticos tipo entrevista. La estructura perfecta no existe; existe la estructura adecuada para tus operaciones dominantes.

Contenido

  1. El método: elegir por operaciones, no por datos
  2. Las siete preguntas clave
  3. Árbol de decisión
  4. La gran tabla del curso
  5. Casos prácticos resueltos
  6. Errores de elección típicos y sus síntomas
  7. Combinar estructuras: el patrón que usa TaskFlow

El método: elegir por operaciones, no por datos

El error más habitual del desarrollador junior es preguntarse "¿qué estructura le pega a estos datos?". La pregunta correcta es otra:

¿Qué operaciones voy a hacer con más frecuencia, y qué coste puedo permitirme en cada una?

Los mismos datos (las tareas de TaskFlow, que son dict con id, titulo, prioridad, estado...) han vivido en el curso dentro de listas, pilas, colas, montículos, tablas hash, árboles y grafos. El dato no cambió; cambió la operación dominante:

  • Para buscar por id: tabla hash (dict), O(1) medio.
  • Para deshacer la última acción: pila, O(1) en el extremo.
  • Para atender la más prioritaria: montículo, O(log n).
  • Para pedir "prioridad entre 1 y 3": ABB/AVL, O(log n + k).
  • Para ordenar por dependencias: grafo + orden topológico, O(V + E).

El procedimiento, siempre el mismo:

  1. Lista las operaciones del problema (insertar, buscar, borrar, recorrer, mínimo, rango...).
  2. Estima la frecuencia de cada una (¿millones de búsquedas y pocas inserciones, o al revés?).
  3. Consulta los costes (la gran tabla de más abajo) y elige la estructura que abarata las operaciones frecuentes, aceptando encarecer las raras.
  4. Si dudas entre dos, mide con timeit (módulo 1): los datos reales mandan.

Las siete preguntas clave

Hazte estas preguntas en orden. La primera que respondas con un "sí" rotundo suele señalar la estructura.

# Pregunta Si la respuesta es sí... Ejemplo en TaskFlow
1 ¿Accedo por clave exacta (id, nombre, email)? Tabla hash: dict / set tareas_por_id[42]
2 ¿Necesito mantener un orden total y hacer consultas por rango ("entre X e Y", "el siguiente a...")? ABB/AVL (o bisect sobre lista ordenada estable) "tareas con prioridad entre 1 y 3"
3 ¿Solo trabajo por los extremos? ¿LIFO o FIFO? LIFO → pila; FIFO → cola; ambos extremos → deque deshacer (LIFO), notificaciones (FIFO)
4 ¿Solo me interesa el más prioritario en cada momento, no el orden completo? Montículo (heapq) BandejaUrgencias
5 ¿Los datos tienen jerarquía (padre-hijos, contención)? Árbol general proyectos → tareas → subtareas
6 ¿Hay relaciones muchos-a-muchos (dependencias, redes, caminos)? Grafo DAG de dependencias entre tareas
7 ¿Nada de lo anterior: solo secuencia con acceso por posición o recorridos completos? list (array dinámico); lista enlazada si hay muchas inserciones/borrados en medio con referencia al nodo el tablero, listados en pantalla

Dos matices importantes:

  • Las preguntas no son excluyentes: un problema real suele responder "sí" a varias. Ahí entra la sección de combinar estructuras.
  • La pregunta 2 y la 1 se confunden a menudo. El hash responde "¿existe la clave 42?" en O(1), pero no puede responder "¿qué claves hay entre 1 y 3?" sin recorrerlo todo — fue el límite del hash que vimos al final del módulo 5, y la puerta por la que entraron los árboles.

Árbol de decisión

El mismo método, en forma de diagrama. Léelo de arriba abajo y detente en la primera hoja que encaje:

flowchart TD
    A[¿Qué operación domina?] --> B{¿Buscar por<br/>clave exacta?}
    B -- Sí --> B1{¿Necesito también<br/>rangos u orden?}
    B1 -- No --> H[Tabla hash: dict / set<br/>O 1 medio]
    B1 -- Sí --> T[ABB / AVL<br/>O log n]
    B -- No --> C{¿Trabajo solo<br/>por extremos?}
    C -- LIFO --> P[Pila<br/>O 1]
    C -- FIFO --> Q[Cola / deque<br/>O 1]
    C -- Ambos extremos --> D[deque<br/>O 1 en los dos]
    C -- No --> E{¿Solo el más<br/>prioritario?}
    E -- Sí --> M[Montículo heapq<br/>O log n]
    E -- No --> F{¿Jerarquía<br/>padre-hijos?}
    F -- Sí --> AR[Árbol general<br/>recorridos O n]
    F -- No --> G{¿Relaciones<br/>muchos a muchos?}
    G -- Sí --> GR[Grafo<br/>BFS/DFS O V+E]
    G -- No --> L{¿Muchas inserciones<br/>en medio con nodo<br/>en la mano?}
    L -- Sí --> LE[Lista enlazada<br/>O 1 con referencia]
    L -- No --> LI[list de Python<br/>acceso O 1 por índice]

Este árbol es una brújula, no una ley: cuando el volumen de datos es pequeño (decenas de elementos), casi cualquier estructura sirve y gana la más simple, que casi siempre es list o dict.

La gran tabla del curso

Todas las estructuras que hemos construido o usado, con sus operaciones clave, cuándo brillan y cuándo son una trampa.

Estructura Operaciones clave (Big O) Cuándo usarla Cuándo NO Ejemplo en TaskFlow
Array / list acceso por índice O(1); append/pop final O(1) amortizado; insert/pop(0) O(n); búsqueda O(n) Secuencias con acceso por posición, recorridos, tamaño moderado Muchas inserciones/borrados al principio o en medio; búsquedas frecuentes por valor Listado de tareas en pantalla
Lista enlazada simple insertar/borrar en cabeza O(1); acceso por posición O(n) Inserciones/borrados frecuentes en cabeza; construir pilas y colas encima Necesitas acceso por índice o recorrido hacia atrás Primer tablero (ListaEnlazada, módulo 2)
Lista doblemente enlazada insertar/borrar con referencia al nodo O(1); navegar en ambos sentidos O(1) por paso Navegación adelante/atrás; borrar un nodo que ya tienes localizado Cuando list o deque cubren el caso con menos código HistorialTareas navegable
Lista circular avanzar "al siguiente" indefinidamente O(1) Turnos rotatorios, round-robin Casi cualquier otro caso RepartidorTareas
Pila push/pop/peek O(1) Lo último que entra es lo primero que importa: deshacer, backtracking, parsing Necesitas acceso al fondo o a posiciones intermedias GestorDeshacerRehacer (dos pilas)
Cola encolar/desencolar O(1) Orden de llegada justo: turnos, mensajería, BFS El orden de atención no es el de llegada (→ prioridad) ColaNotificaciones
Cola circular (ring buffer) encolar/desencolar O(1), memoria fija Buffers de tamaño acotado: los últimos N eventos El tamaño no está acotado RegistroEventos
Cola de prioridad / montículo insertar O(log n); extraer mínimo O(log n); ver mínimo O(1) "Dame siempre el más urgente"; top-k; planificadores Necesitas buscar elementos arbitrarios o recorrer en orden completo a menudo BandejaUrgencias con heapq
deque append/pop en ambos extremos O(1); acceso en medio O(n) Colas, historiales con límite (maxlen), ventanas deslizantes Acceso por índice en medio frecuente HistorialConLimite, VentanaProductividad
Tabla hash / dict / set insertar/buscar/borrar O(1) medio; sin orden ni rangos Acceso por clave exacta, contar, agrupar, memoizar, deduplicar Rangos, orden, "el siguiente mayor que..."; claves no hashables tareas_por_id, índice etiqueta→ids
ABB (sin equilibrar) insertar/buscar O(log n) medio, O(n) peor (degenerado); rango O(log n + k) Prototipos, datos de llegada aleatoria Datos que llegan ordenados (degenera en lista) Primera versión de búsqueda por rango
AVL insertar/buscar/borrar O(log n) garantizado; recorrido inorden O(n) ordenado Orden + rangos + rendimiento predecible Solo buscas por clave exacta (el hash es más simple y rápido) "Prioridad entre 1 y 3" en producción
Árbol B / B+ búsqueda/rango O(log n) con nodos anchos, optimizado para disco Índices en disco, bases de datos Estructuras en memoria (AVL/hash bastan) El índice SQLite donde TaskFlow persistiría
Grafo BFS/DFS O(V+E); Dijkstra O((V+E) log V); orden topológico O(V+E) Dependencias, redes, caminos, alcanzabilidad Los datos son una simple secuencia o jerarquía estricta DAG de dependencias, planificador

Consejo de lectura: no memorices la tabla; memoriza las filas que te sorprenden. Que insert(0) en una list es O(n) y que un dict no sabe responder rangos son los dos datos de esta tabla que más errores evitan en el mundo real.

Casos prácticos resueltos

Razonemos cuatro escenarios como se plantearían en una entrevista técnica. Fíjate en que el razonamiento siempre sigue el método: operaciones → frecuencias → costes.

Caso 1: "Diseña la función autocompletar"

Al escribir "reun" en el buscador de TaskFlow deben aparecer los títulos que empiezan por ese prefijo.

  • Operación dominante: búsqueda por prefijo, no por clave exacta. La pregunta 1 (hash) falla: dict solo encuentra claves completas.
  • La pregunta 2 (orden) sí encaja: en una colección ordenada alfabéticamente, todos los títulos que empiezan por "reun" son contiguos. Con una list ordenada y bisect localizamos el primer candidato en O(log n) y recorremos mientras el prefijo coincida.
  • Alternativa con lo que sabemos de hash: un dict prefijo→lista de ids, precalculado (para cada título guardamos sus prefijos). Consulta O(1), a cambio de mucha memoria. La estructura especializada en esto es el trie, que asomará en la lección de recursos.
import bisect

def autocompletar(titulos_ordenados, prefijo, limite=10):
    """titulos_ordenados: list ordenada alfabéticamente."""
    i = bisect.bisect_left(titulos_ordenados, prefijo)  # O(log n)
    resultado = []
    while i < len(titulos_ordenados) and titulos_ordenados[i].startswith(prefijo):
        resultado.append(titulos_ordenados[i])
        if len(resultado) == limite:
            break
        i += 1
    return resultado

bisect_left hace una búsqueda binaria (la misma idea que el ABB, sobre un array): encuentra dónde empezaría el prefijo. Después solo avanzamos mientras haya coincidencia: O(log n + k) con k resultados.

Caso 2: "Los 10 eventos más recientes"

TaskFlow debe mostrar los últimos 10 eventos de actividad, descartando los antiguos.

  • Operaciones: añadir por un extremo, descartar por el otro, tamaño fijo. Pregunta 3: extremos, FIFO con límite.
  • Es exactamente un ring buffer, y en Python ya lo tenemos hecho: deque(maxlen=10). Añadir es O(1) y el descarte del más antiguo es automático.
from collections import deque

eventos = deque(maxlen=10)
eventos.append({"tipo": "crear", "tarea_id": 7})   # O(1); si hay 10, expulsa el más viejo

Elegir aquí una list con pop(0) funcionaría... a O(n) por descarte: el síntoma sería una app que se ralentiza a medida que crece el registro histórico.

Caso 3: "Detecta si el proyecto tiene dependencias circulares"

Antes de planificar, TaskFlow debe avisar si A depende de B, B de C y C de A.

  • "Depende de" es una relación muchos-a-muchos: pregunta 6, grafo. Un ciclo en el grafo de dependencias hace imposible el orden topológico.
  • Solución del módulo 7: DFS con tres colores (blanco/gris/negro). Encontrar una arista hacia un nodo gris (aún en la pila de recursión) delata el ciclo. Coste O(V + E). Alternativa equivalente: si Kahn no consigue procesar todos los vértices, hay ciclo.
  • El error típico es intentar resolverlo con listas y bucles anidados "siguiendo cadenas de dependencias": acaba en O(n²) o en bucles infinitos. Cuando veas relaciones cruzadas, modela el grafo explícitamente.

Caso 4: "Busca por id" frente a "lista ordenada por prioridad"

TaskFlow necesita (a) abrir una tarea por su id al instante y (b) mostrar el backlog ordenado por prioridad.

  • Son dos operaciones dominantes distintas y ninguna estructura gana en ambas:
Necesidad dict por id list ordenada por prioridad AVL por prioridad
Buscar por id O(1) O(n) O(n) (¡la clave es la prioridad, no el id!)
Listar por prioridad O(n log n) (ordenar cada vez) O(n) (ya ordenada) O(n) inorden
Insertar O(1) O(n) (hueco) O(log n)
  • Respuesta madura: las dos. Un dict id→tarea como almacén principal, y una estructura ordenada (montículo si solo atiendes la más urgente; AVL o lista+bisect si listas rangos) que guarda referencias. Eso nos lleva directos a la última sección.

Errores de elección típicos y sus síntomas

Cada mala elección tiene una firma de rendimiento reconocible. Aprende a leerla:

Error Síntoma Diagnóstico Remedio
Buscar por valor en una list dentro de un bucle Todo va bien con 100 elementos y se arrastra con 100 000 x in lista es O(n) → el bucle es O(n²) set o dict: x in conjunto es O(1)
insert(0) / pop(0) sobre list Encolar se vuelve lento al crecer la cola Desplaza todos los elementos: O(n) deque (módulo 4)
Ordenar la lista entera "para sacar el mínimo" sort() en cada iteración: O(n log n) por operación Solo necesitas el extremo, no el orden total heapq: O(log n)
ABB con datos que llegan ya ordenados Rendimiento "logarítmico" que se comporta como lineal El árbol degeneró en una lista AVL, o barajar/usar bisect
dict cuando necesitas rangos Código lleno de for k in d: if a <= k <= b El hash destruye el orden a propósito AVL / lista ordenada + bisect
Grafo "simulado" con listas de listas y búsquedas cruzadas Bucles anidados frágiles, ciclos que cuelgan el programa Relaciones muchos-a-muchos sin modelar Grafo con lista de adyacencia + BFS/DFS
Optimizar sin medir Días perdidos en una estructura exótica para 50 elementos n minúsculo: las constantes dominan timeit primero; simple por defecto

Combinar estructuras: el patrón que usa TaskFlow

Las aplicaciones reales casi nunca usan una estructura: usan varias coordinadas, cada una pagando la operación que mejor sabe hacer. TaskFlow es el ejemplo que hemos construido durante ocho módulos:

import heapq

class NucleoTaskFlow:
    """Esqueleto de cómo TaskFlow combina estructuras (versión mínima)."""

    def __init__(self):
        self.tareas = {}            # dict id -> tarea         : buscar por id O(1)
        self.por_etiqueta = {}      # dict etiqueta -> set ids : índice invertido O(1)
        self.urgencias = []         # heap (prioridad, contador, id) : más urgente O(log n)
        self._contador = 0          # desempate estable en el montículo

    def crear(self, tarea):
        self.tareas[tarea["id"]] = tarea                       # O(1)
        for etiqueta in tarea.get("etiquetas", []):
            self.por_etiqueta.setdefault(etiqueta, set()).add(tarea["id"])  # O(1)
        self._contador += 1
        heapq.heappush(self.urgencias, (tarea["prioridad"], self._contador, tarea["id"]))  # O(log n)

    def mas_urgente(self):
        while self.urgencias:
            prioridad, _, id_ = self.urgencias[0]
            tarea = self.tareas.get(id_)
            # Entrada obsoleta: la tarea se borró o cambió de prioridad
            if tarea is None or tarea["prioridad"] != prioridad:
                heapq.heappop(self.urgencias)   # la descartamos y seguimos
                continue
            return tarea
        return None

Puntos que conviene entender bien de este patrón:

  • El dict es el almacén canónico: la única fuente de verdad. Las demás estructuras guardan solo ids (referencias baratas), nunca copias de la tarea.
  • El montículo usa la tupla (prioridad, contador, id) del módulo 4: el contador desempata prioridades iguales manteniendo orden de llegada y evita comparar dicts.
  • Borrado perezoso: borrar del medio de un montículo es incómodo, así que no borramos; al consultar, descartamos entradas cuya tarea ya no existe o cambió. Es un truco estándar en planificadores reales.
  • El precio de combinar es la coherencia: cada escritura toca varias estructuras. Centraliza las modificaciones en métodos (crear, borrar...) para que ninguna estructura se quede desincronizada.

Ejercicios

Ejercicio 1

Para cada necesidad de TaskFlow, elige estructura y justifica con su Big O: (a) comprobar en O(1) si un email ya está registrado; (b) mostrar las tareas con horas entre 2 y 5; (c) procesar acciones de "deshacer" del usuario; (d) repartir tareas entre 3 personas por turnos rotatorios; (e) media móvil de horas trabajadas en los últimos 7 días.

Ejercicio 2

Este código busca las tareas urgentes sin asignar. Identifica los dos problemas de elección de estructura y reescríbelo:

def urgentes_sin_asignar(tareas, asignadas):   # tareas: list de dicts; asignadas: list de ids
    resultado = []
    for t in tareas:
        if t["prioridad"] == 1 and t["id"] not in asignadas:
            resultado.append(t)
    resultado.sort(key=lambda t: t["horas"])
    return resultado[:3]

Ejercicio 3

Diseña (solo el diseño: estructuras y coste de cada operación, sin código) el "modo repaso" de TaskFlow: guarda las últimas 50 tareas visitadas sin duplicados; si visitas una que ya estaba, sube a la posición más reciente; consultar si una tarea está en el historial debe ser O(1). Pista: es el mismo compromiso que una caché LRU.

Soluciones

Ejercicio 1. (a) set — pertenencia O(1); (b) AVL con clave horas (o list ordenada + bisect si hay pocas escrituras) — rango O(log n + k); (c) pila — LIFO puro, O(1); (d) lista circular (RepartidorTareas) — "siguiente" O(1) sin fin; (e) deque(maxlen=7) con suma incremental — O(1) por día, como la VentanaProductividad del módulo 4.

Ejercicio 2. Problema 1: t["id"] not in asignadas sobre una list es O(n), lo que hace el bucle O(n·m); conviértela una sola vez en set → O(1) por consulta. Problema 2: ordenar todo para quedarte con 3 es O(k log k); para un top-k pequeño usa heapq.nsmallest, O(k log 3):

import heapq

def urgentes_sin_asignar(tareas, asignadas):
    ids_asignadas = set(asignadas)                       # O(m), una vez
    candidatas = [t for t in tareas
                  if t["prioridad"] == 1 and t["id"] not in ids_asignadas]  # O(n)
    return heapq.nsmallest(3, candidatas, key=lambda t: t["horas"])         # O(n log 3)

Ejercicio 3. Combina dos estructuras coordinadas: una lista doblemente enlazada con el orden de visita (el más reciente en la cabeza) y un dict id→nodo. Visitar una tarea nueva: crear nodo en cabeza + entrada en el dict, O(1); si supera 50, quitar el nodo de la cola y su entrada del dict, O(1). Visitar una existente: el dict localiza su nodo en O(1) y, al ser doblemente enlazada, se desengancha y se mueve a cabeza en O(1) — justo la operación que una list no sabe hacer barata. Consultar pertenencia: id in dict, O(1). Ninguna de las dos estructuras por separado lo consigue; juntas, todo es O(1).

Conclusión

Ya tienes el criterio que perseguía todo el curso: primero las operaciones, luego la estructura, y ante la duda, medir. Las siete preguntas y el árbol de decisión te llevan a la candidata; la gran tabla te da sus costes; los síntomas de rendimiento te avisan cuando te equivocaste; y el patrón de combinación (almacén dict + índices y montículos auxiliares) te enseña cómo lo hacen las aplicaciones reales, TaskFlow incluida. En la próxima lección haremos el viaje inverso: repasaremos módulo a módulo todo lo construido, para consolidar el mapa completo antes de los proyectos finales.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados