Estructuras de datos

Una estructura de datos es una forma de organizar y almacenar datos para poder operarlos de forma eficiente. Elegir la estructura correcta es muchas veces la decisión que define si un sistema funciona o se cae: una búsqueda sobre un array de un millón de elementos puede tardar 10 ms… o 10 segundos, según la estructura.

El principio que ordena todo: cada estructura hace muy rápido algunas operaciones y muy lento otras. No hay una estructura perfecta; hay una correcta para cada necesidad.

Qué mirar en una estructura

Dos cosas determinan todo:

1. Operaciones: ¿qué quieres hacer? Insertar, buscar, eliminar, recorrer, acceder al máximo…
2. Complejidad (big-O): ¿cuánto cuesta cada operación cuando los datos crecen? Lo explico a fondo en Algoritmos.

💡 Regla mental: un array es lo mejor para acceder por índice; una lista enlazada para insertar/eliminar en el medio; un hash table para buscar por clave; un árbol para datos ordenados; un heap para el máximo/mínimo rápido; un grafo para relaciones.

Arrays

Un array es un bloque contiguo de memoria donde cada elemento ocupa el mismo tamaño y se accede por su índice (posición).

arr = [10, 20, 30, 40, 50]
print(arr[0])    # 10  → O(1): acceso por índice
arr[2] = 99      # actualización → O(1)

int arr[5] = {10, 20, 30, 40, 50};
printf("%d\n", arr[0]);   // 10

⚠️ Arrays dinámicos: en Python y la mayoría de lenguajes, los arrays crecen solos (cada vez que se llenan, se redimensionan duplicando tamaño → amortizado O(1) por inserción). En C el tamaño es fijo y tú gestionas todo.

La tabla mental del array

Índice:    0     1     2     3     4
          ┌─────┬─────┬─────┬─────┬─────┐
Valor:    │ 10  │ 20  │ 30  │ 40  │ 50  │
          └─────┴─────┴─────┴─────┴─────┘
Memoria:  0x100 0x104 0x108 0x10C 0x110   (si int = 4 bytes)

arr[2] = 0x100 + 2×4 = 0x108. Por eso el acceso es O(1): no hay que «buscar», se calcula.

Listas enlazadas (linked list)

Una lista enlazada guarda cada elemento con un puntero al siguiente. No hay bloques contiguos: los nodos están dispersos en memoria y se conectan por punteros.

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.siguiente = None   # puntero al siguiente

# Construir: 10 → 20 → 30
a = Nodo(10)
b = Nodo(20)
c = Nodo(30)
a.siguiente = b
b.siguiente = c

typedef struct Nodo {
    int valor;
    struct Nodo *siguiente;
} Nodo;

💡 La lista enlazada gana en inserción/eliminación, el array gana en acceso por índice. La memoria de una lista enlazada es peor (cada nodo lleva además el puntero), y los accesos son cache-unfriendly (los nodos no están juntos en RAM).

Tipos de listas enlazadas

• Simplemente enlazada: cada nodo → siguiente. Solo puedes recorrer hacia adelante.
• Doblemente enlazada: cada nodo → siguiente y anterior. Recorres en ambas direcciones (a costa de un puntero más por nodo).
• Circular: el último apunta al primero.

Pilas (stacks) y colas (queues)

Son las estructuras de la vida real: una pila es una torre de platos (sacas el de arriba), una cola es la fila del supermercado (el primero en llegar sale primero).

Pila (stack) — LIFO (Last In, First Out)

Último en entrar, primero en salir.

pila = []
pila.append(1)      # push
pila.append(2)
pila.append(3)
print(pila.pop())   # 3  → pop (sale el último)
print(pila.pop())   # 2

Usos: undo/redo de editores, evaluar expresiones, depth-first search, el stack de llamadas de la CPU (recursión), parsing de paréntesis.

# ¿Paréntesis balanceados? Clásico con una pila
def balanceado(s):
    pila = []
    pares = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            pila.append(c)
        elif c in ')]}':
            if not pila or pila.pop() != pares[c]:
                return False
    return not pila

print(balanceado("([{}])"))   # True
print(balanceado("([)]"))     # False

Cola (queue) — FIFO (First In, First Out)

Primero en entrar, primero en salir.

from collections import deque
cola = deque()
cola.append("ana")     # enqueue (llegar)
cola.append("luis")
cola.append("carlos")
print(cola.popleft())  # "ana"  → dequeue (atender al primero)

Usos: colas de mensajes, breadth-first search, colas de impresión, buffers, tareas pendientes.

⚠️ En Python, list.pop(0) es O(n): usar deque para colas reales.

Tablas hash (hash tables / diccionarios)

Una tabla hash guarda clave → valor. La clave se pasa por una función hash que la convierte en un índice de un array. Buscar precios["pera"] es O(1) promedio: no recorres nada, calculas el índice directo.

precios = {}
precios["manzana"] = 2.5
precios["pera"] = 3.0
print(precios["pera"])   # 3.0  → O(1)

print("mango" in precios)   # False → O(1)
precios.pop("manzana")      # eliminar → O(1)

Clave "pera" ──hash──▶ índice 3 ──▶ [ ][ ][ ]["pera":3.0][ ]

Colisiones

Si dos claves caen en el mismo índice, hay una colisión. Dos soluciones clásicas:

• Chaining: cada posición del array es una lista de pares (varios elementos en el mismo índice).
• Open addressing: buscas la siguiente posición libre.

Con colisiones, la búsqueda ya no es O(1) puro; por eso la tabla se redimensiona (duplica tamaño) cuando el factor de carga sube demasiado (típicamente > 0.75).

💡 En la práctica, Python (dict), Go (map), JS (Map/Object) y Java (HashMap) implementan tablas hash internamente. Cuando digas «diccionario», «mapa», «HashMap», «tabla hash»: es la misma estructura.

Buenas funciones hash

• Determinista: la misma entrada siempre da el mismo índice.
• Rápida de calcular.
• Distribuye bien: entradas parecidas dan índices muy distintos (evita agrupaciones).

⚠️ Seguridad: un atacante que conoce tu función hash puede fabricar claves que colisionan todas → DoS (la tabla degrada a O(n)). Por eso lenguajes modernos aleatorizan la semilla del hash (salting).

Árboles binarios de búsqueda (BST)

Un árbol binario tiene un nodo raíz y cada nodo tiene hasta dos hijos (izquierdo y derecho). Un árbol binario de búsqueda (BST) mantiene el orden: a la izquierda van los valores menores, a la derecha los mayores.

           50
         /    \
       30      70
      /  \    /  \
     20  40  60  80

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izq = None
        self.der = None

def insertar(raiz, valor):
    if raiz is None:
        return Nodo(valor)
    if valor < raiz.valor:
        raiz.izq = insertar(raiz.izq, valor)
    else:
        raiz.der = insertar(raiz.der, valor)
    return raiz

def buscar(raiz, valor):
    if raiz is None or raiz.valor == valor:
        return raiz
    if valor < raiz.valor:
        return buscar(raiz.izq, valor)
    return buscar(raiz.der, valor)

⚠️ El problema: si insertas valores ordenados (1,2,3,4…), el árbol se convierte en una lista enlazada (degenera) y todo pasa a O(n). La solución son los árboles balanceados: AVL y Red-Black (estos últimos usan PostgreSQL y los std::map de C++/Java). Se auto-equilibran con rotaciones.

Recorridos de un árbol

Heaps (montículos)

Un heap es un árbol binario casi completo con una propiedad especial: cada nodo es mayor (max-heap) o menor (min-heap) que sus hijos. El máximo (o mínimo) está siempre en la raíz.

Max-heap:
           90
         /    \
       72      60
      /  \    /  \
     50  40  30  20

Se implementan sobre un array (el padre del índice i está en (i-1)//2, los hijos en 2i+1 y 2i+2), sin punteros. Son la base del heap sort y de las colas de prioridad (tareas urgentes, Dijkstra, el planificador de tareas del SO).

import heapq

cola = []
heapq.heappush(cola, 5)   # insertar → O(log n)
heapq.heappush(cola, 1)
heapq.heappush(cola, 3)
print(heapq.heappop(cola))   # 1 → el mínimo sale primero

# En Python, heapq = min-heap. Para max-heap, guarda negativos.

Grafos

Un grafo es un conjunto de nodos (vértices) conectados por aristas (edges). Es la estructura de las relaciones: redes sociales (personas → amistad), rutas (ciudades → carreteras), dependencias (paquetes → requisitos), la web (páginas → enlaces).

       A ── B
       |    |
       C ── D ── E

Representaciones comunes:

# 1. Lista de adyacencia (la más usada)
grafo = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

# 2. Matriz de adyacencia (n×n, 1 si hay arista)
#    A B C D E
# A [0,1,1,0,0]
# B [1,0,0,1,0]
# ...

Grafos dirigidos y ponderados

• Dirigido: las aristas tienen dirección (A→B no es lo mismo que B→A). Ej: seguir a alguien en Twitter, enlaces de la web.
• Ponderado: las aristas tienen peso. Ej: distancia entre ciudades, costo de una tarea.
• Cíclico / acíclico: un ciclo es un camino que vuelve al inicio. Los DAG (Directed Acyclic Graph) ordenan tareas con dependencias (builds, pipelines).

Los algoritmos sobre grafos (DFS, BFS, Dijkstra, caminos mínimos, topológico) están en la página de Algoritmos.

Cuándo usar cada estructura

Cheatsheet de complejidades

* O(1) al final sin desplazamientos. † Si ya tienes el nodo. ‡ Solo el máximo/mínimo. § Solo el máximo/mínimo.

Práctica propuesta

1. Implementa una pila y una cola sobre un array y verifica su comportamiento.
2. Implementa una lista enlazada en C con insertar al inicio y al final.
3. Cuenta la frecuencia de palabras de un texto usando un diccionario.
4. Implementa un BST con insertar, buscar y recorrido in-order.
5. Implementa una cola de prioridad con un heap (o usa heapq).
6. Representa una red social como grafo y responde: ¿hay camino entre A y B? (DFS/BFS)

Para profundizar

• CS50 — Estructuras de datos: cómo se implementan en C, arrays vs listas, hash tables.
• CP-Algorithms: implementaciones y teoría de todas las estructuras.
• Visualgo: animaciones de estructuras y algoritmos.
• Big-O Cheatsheet: tabla completa de complejidades.
• Sigue con ⏱️ Algoritmos.