¿Cómo eliges una estructura de datos?

Respuesta directa

Qué debe cubrir una buena respuesta

Cómo funciona

Elige la estructura según las operaciones que el código realiza con más frecuencia y los invariantes que debe mantener. Un hash map da búsqueda por clave en tiempo constante promedio sin orden; una estructura ordenada como un árbol balanceado o un array ordenado da consultas por rango e iteración ordenada a coste logarítmico; una cola o deque da inserción barata en los extremos; un heap da el mínimo o máximo rápido; un conjunto impone unicidad. La disposición en memoria importa tanto como la asintótica en la práctica: un array contiguo gana a una lista enlazada al iterar aunque la teoría diga lo contrario, por el comportamiento de la caché.

Ejemplo

Un rate limiter necesita encontrar el contador de un cliente y expirar entradas viejas; un hash map por cliente más un min-heap ordenado por tiempo de expiración soporta ambas operaciones en tiempo logarítmico. Un ranking que necesita el top diez y consultas de posición usa una estructura ordenada en lugar de reordenar un array de un millón de jugadores en cada lectura.

Errores frecuentes

• Usar una lista por defecto y recorrerla en cada búsqueda.
• Elegir una lista enlazada para insertar en medio sin medir que sea realmente más rápida que un array.
• Ignorar los requisitos de concurrencia y envolver una estructura insegura en un lock añadido a posteriori.

Una estructura útil para responder

Responde desde tu propia experiencia.

No memorices un guion: usa solo ejemplos que puedas explicar con honestidad en preguntas posteriores.