¿Cómo elige la estructura de datos correcta para un problema?

Question

Accepted Answer

Elija la estructura cuyas **operaciones más frecuentes sean más baratas** para su patrón de acceso. Comience haciendo una lista de las operaciones que realizará, estime su frecuencia y luego asócielas con las fortalezas de la estructura.

## Lista de verificación de decisión

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Hacer coincidir operaciones con complejidad

| Necesidad | Mejor estructura | Costo de operación clave |
|---|---|---|
| Acceso aleatorio por índice | dynamic array | O(1) |
| Búsqueda por clave | hash map | O(1) avg |
| Ordenado + consultas de rango | balanced BST | O(log n) |
| Min/max repetidamente | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Búsqueda de prefijo | trie | O(L) |

## Ejemplo de razonamiento

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Por qué es importante

Elegir correctamente a menudo es la diferencia entre una solución O(n) y una O(n²) — la palanca más grande en el rendimiento.

Los entrevistadores prueban exactamente este razonamiento: quieren ver cómo asigna requisitos a costos de operación, no solo memorizar estructuras.

Necesidad	Mejor estructura	Costo de operación clave
Acceso aleatorio por índice	dynamic array	O(1)
Búsqueda por clave	hash map	O(1) avg
Ordenado + consultas de rango	balanced BST	O(log n)
Min/max repetidamente	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Búsqueda de prefijo	trie	O(L)