* O(1) si se tiene referencia al nodo. BST: casos promedio, puede degradar a O(n) si no está balanceado.
📊 Array (arreglo o vector)
Acceso directo por índice
Una secuencia de elementos guardados uno detrás de otro en memoria. Como todos ocupan lo mismo y están contiguos, la posición de cualquiera se calcula con una suma: por eso leer el elemento 4.000 cuesta lo mismo que leer el primero.
Operaciones y coste
Operación
Coste
Por qué
Acceso por índice
O(1)
la dirección se calcula, no se recorre
Búsqueda de un valor
O(n)
hay que mirar elemento a elemento si no está ordenado
Insertar o eliminar en medio
O(n)
obliga a desplazar todo lo que viene detrás
Dónde se usa: tablas de píxeles de una imagen, matrices de un cálculo numérico, cualquier colección que se lee mucho por posición y cambia poco de tamaño.
📚 Pila (Stack): el principio LIFO
LIFO — Last In, First Out: el último en entrar es el primero en salir
Solo se toca un extremo: se apila encima (push) y se retira de encima (pop). Como una pila de platos, para llegar al de abajo hay que quitar los de arriba. Esa limitación es justo lo que la hace barata y predecible.
Operaciones y coste
Operación
Coste
Por qué
push (apilar)
O(1)
añade encima del todo
pop (desapilar)
O(1)
retira el elemento de encima
peek (mirar la cima)
O(1)
consulta sin retirar
Dónde se usa: la pila de llamadas de cualquier programa, el deshacer de un editor, la evaluación de expresiones con paréntesis y el recorrido en profundidad de un grafo (DFS).
🚶 Cola (Queue): el principio FIFO
FIFO — First In, First Out: el primero en entrar es el primero en salir
Se entra por un extremo (enqueue) y se sale por el contrario (dequeue), igual que la fila de una ventanilla. Nadie adelanta a nadie, así que el orden de llegada se respeta siempre: es la estructura del reparto justo.
Operaciones y coste
Operación
Coste
Por qué
enqueue (encolar)
O(1)
entra por el final
dequeue (desencolar)
O(1)
sale por el principio
Buscar un elemento
O(n)
hay que recorrerla; no es para eso
Dónde se usa: trabajos en espera de una impresora, el planificador de procesos de un sistema operativo, el recorrido en anchura de un grafo (BFS) y los búferes entre dos procesos con ritmos distintos.
🔗 Lista enlazada (Linked List)
Cada nodo guarda su valor y la dirección del siguiente
Los elementos no están contiguos en memoria: cada uno apunta al que le sigue. No hace falta reservar el espacio de golpe ni desplazar nada al insertar, pero se paga en el acceso, porque para llegar al elemento n hay que pasar por los n-1 anteriores.
Operaciones y coste
Operación
Coste
Por qué
Insertar o eliminar con el nodo en la mano
O(1)
basta con reenganchar dos punteros
Acceder a la posición n
O(n)
no hay atajo: se recorre desde la cabeza
Búsqueda de un valor
O(n)
igual que el array, pero sin poder saltar
Dónde se usa: listas que crecen y menguan mucho por el medio, implementación interna de pilas y colas, y estructuras donde reservar un bloque grande y contiguo no es posible.
🌳 Árbol binario de búsqueda (BST)
A la izquierda lo menor, a la derecha lo mayor
Cada nodo tiene como mucho dos hijos y cumple esa regla en todo el árbol. Buscar consiste en descender comparando: en cada paso se descarta la mitad de lo que queda, igual que en una búsqueda binaria. El matiz importante es que ese O(log n) es el caso promedio: si los datos entran ya ordenados el árbol degenera en una lista y vuelve a O(n), que es el problema que resuelven los árboles autobalanceados.
Operaciones y coste
Operación
Coste
Por qué
Buscar un valor
O(log n)
promedio; O(n) si el árbol está degenerado
Insertar
O(log n)
desciende hasta el hueco que le toca
Recorrido en orden (inorden)
O(n)
devuelve todos los valores ya ordenados
Dónde se usa: índices de bases de datos, diccionarios y conjuntos ordenados, autocompletado y cualquier caso donde haga falta consultar y mantener el orden a la vez.
📚¿Quieres aprender más sobre Estructuras de Datos?
Conceptos fundamentales para programadores
Tabla Comparativa de Estructuras de Datos
Estructura
Acceso
Búsqueda
Inserción
Eliminación
Memoria
Uso típico
Array
O(1)
O(n)
O(n)
O(n)
O(n) continua
Acceso por índice, cache-friendly
Lista Enlazada
O(n)
O(n)
O(1)*
O(1)*
O(n) + punteros
Inserciones/eliminaciones frecuentes
Pila (Stack)
O(n)
O(n)
O(1)
O(1)
O(n)
Deshacer, recursión, expresiones
Cola (Queue)
O(n)
O(n)
O(1)
O(1)
O(n)
BFS, procesamiento en orden
Árbol BST
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
Búsqueda ordenada, rangos
Hash Table
O(1) amort.
O(1) amort.
O(1) amort.
O(1) amort.
O(n) dispersa
Diccionarios, cachés, índices
Grafo
O(1)
O(V+E)
O(1)
O(V+E)
O(V+E)
Redes, rutas, relaciones
* O(1) si se tiene referencia directa al nodo. BST casos promedio; puede degradar a O(n) sin balanceo.
Escenarios Reales
🌐
Navegador web
El historial usa una Pila (Stack): cada página visitada se apila, el botón atrás hace pop. Las pestañas abiertas usan una lista doblemente enlazada.
Tip: Stack para historial, Queue para operaciones pendientes (descarga de imágenes).
🔍
Motor de búsqueda
Google usa tablas hash invertidas: palabra → lista de URLs. Con 50.000M páginas, la búsqueda es O(1) en lugar de O(n).
Tip: Hash Table cuando necesitas búsqueda O(1) y tienes una clave única.
🎮
Pathfinding en videojuegos
A* usa una Cola de Prioridad (heap). En un mapa 1000×1000 con obstáculos, encuentra el camino óptimo en <10ms.
Tip: Cola de prioridad para problemas donde siempre procesas el elemento más prioritario.
🗺️
GPS y redes sociales
Dijkstra sobre un grafo de 300M nodos (red de carreteras de Europa) encuentra la ruta óptima. LinkedIn representa conexiones como grafo no dirigido ponderado.
Tip: Grafo para relaciones complejas muchos-a-muchos con pesos.
Preguntas Frecuentes
¿Cuándo usar Array vs Lista Enlazada?
Array cuando: acceso por índice frecuente (cache-friendly), tamaño conocido, pocas inserciones en medio. Lista cuando: inserciones/eliminaciones frecuentes en cualquier posición, tamaño desconocido. En la práctica, los arrays casi siempre ganan por localidad de caché.
¿Por qué los Hash Tables tienen O(1) amortizado, no garantizado?
Con mala función hash, muchas claves colisionan en el mismo bucket → lista enlazada → O(n) en peor caso. Solución: rehashing cuando el factor de carga supera 0,75.
¿Qué es un árbol balanceado y por qué importa?
Un BST degenerado (insertar 1,2,3,4,5 en orden) se convierte en lista enlazada: O(n) búsqueda. AVL y Red-Black Trees garantizan O(log n) mediante rotaciones automáticas.
¿Diferencia entre Stack y Queue?
Stack: LIFO (Last In, First Out) — como una pila de platos. Queue: FIFO (First In, First Out) — como una cola del supermercado. Stack para llamadas de función, deshacer. Queue para procesamiento en orden, BFS.
¿Cuándo usar un Heap vs un BST?
Heap: cuando solo necesitas el máximo/mínimo rápidamente (O(1) peek, O(log n) insert/delete). BST: cuando necesitas búsqueda por valor arbitrario O(log n). Priority Queue implementa Heap.
¿Qué es la complejidad espacial y por qué importa?
El espacio de memoria que usa la estructura. Lista enlazada necesita O(n) nodos + punteros (overhead ×2 vs array). En sistemas embebidos o con millones de objetos, este overhead puede ser crítico.
¿BFS vs DFS en grafos?
BFS (Cola): encuentra el camino más corto en grafos no ponderados. Usa O(n) memoria (guarda nivel completo). DFS (Stack/Recursión): explora profundidad, usa menos memoria O(h) donde h es la altura. DFS para detectar ciclos, componentes conexos.
¿Qué es una tabla hash perfecta?
Una función hash sin colisiones para un conjunto conocido de claves. Posible cuando las claves son fijas (ej: palabras clave de un lenguaje de programación). gperf genera tablas hash perfectas mínimas.
Guía Paso a Paso: Cómo Elegir una Estructura
1
¿Cómo accedes a los datos?
Por índice → Array. Por clave → Hash Table. Secuencialmente → Lista. Jerárquicamente → Árbol.
Arrays son 5-10x más rápidos que listas enlazadas para iteración secuencial por localidad de caché. Prefiere arrays salvo que las inserciones en medio sean críticas.
📊
Factor de carga
Mantén el factor de carga de Hash Tables entre 0,6-0,75. Sobre 0,8, las colisiones degradan el rendimiento a O(n).
🌳
Árboles siempre balanceados
Nunca implementes BST sin balanceo en producción. Usa TreeMap (Java), SortedDict (Python sortedcontainers) o equivalente.
🔗
Listas doblemente enlazadas
Para eliminación O(1) cuando tienes el nodo (LRU Cache usa HashMap + Lista doblemente enlazada). Sola, la lista enlazada rara vez es óptima.
💡
Estructura compuesta
Los problemas reales usan combinaciones: HashMap<String, BST> para búsqueda de rango por clave, o Array of Linked Lists para hash table con chaining.
📏
Mide con tus datos reales
La complejidad teórica asume distribución uniforme. Mide con tus datos reales: un HashMap puede ser más lento que un Array pequeño por el overhead de hashing.
⚠️ Errores comunes con estructuras de datos
ArrayList con inserción frecuente en medio: O(n) por desplazamiento. Con 1M elementos y 1000 inserciones/s, usa LinkedList o deque.
HashMap sin hashCode() correcto: En Java/Python, si dos objetos iguales tienen distinto hashCode, tendrás duplicados y comportamiento indefinido.
BST sin balanceo con datos ordenados: Insertar 1..N en BST sin balancear → lista enlazada → O(n) búsqueda.
Stack overflow por DFS recursivo: En grafos con 100K+ nodos, la recursión puede exceder el stack. Convierte a DFS iterativo con stack explícito.
Hash Table con claves mutables: En Python, usar listas como claves de dict lanza TypeError. Los objetos mutables no pueden ser claves hash.
Ignorar el overhead de memoria: Lista enlazada con 1M nodos int: 8 bytes dato + 8 bytes puntero siguiente = 2x más memoria que array.