Fundamentos de Programación: Estructuras de Datos y Algoritmos Eficientes

¡Domina las estructuras de datos y algoritmos eficientes! En este tutorial avanzado te guiaré paso a paso para que aprendas a elegir y implementar las estructuras de datos correctas, junto con algoritmos eficientes para resolver problemas comunes.

Objetivo: Aprender estructuras de datos fundamentales (arrays, listas enlazadas, pilas, colas, árboles, grafos), algoritmos de ordenamiento y búsqueda eficientes, y análisis de complejidad algorítmica para escribir código de alto rendimiento.

Paso 1: ¿Qué son las estructuras de datos?

Las estructuras de datos son formas específicas de organizar y almacenar datos para que puedan ser utilizados de manera eficiente. Piensa en ellas como diferentes tipos de muebles de almacenamiento: cajones, estantes, armarios... cada uno optimizado para diferentes necesidades.

# Analogía: Diferentes estructuras para diferentes propósitos
"""
Array → Estante fijo: Acceso rápido pero tamaño fijo
Lista → Estante expandible: Flexible pero un poco más lento
Pila → Pila de platos: Último en entrar, primero en salir (LIFO)
Cola → Fila del banco: Primero en entrar, primero en salir (FIFO)
Diccionario → Guía telefónica: Acceso rápido por clave
Set → Colección de sellos: Sin duplicados, búsqueda rápida
"""

Paso 2: Arrays vs listas enlazadas

Arrays (vectores)

# Arrays en Python (usamos listas, pero entendiendo el concepto)
class MiArray:
    def __init__(self, capacidad):
        self.capacidad = capacidad
        self.longitud = 0
        self.datos = [None] * capacidad

    def __getitem__(self, indice):
        if indice < 0 or indice >= self.longitud:
            raise IndexError("Índice fuera de rango")
        return self.datos[indice]

    def __setitem__(self, indice, valor):
        if indice < 0 or indice >= self.longitud:
            raise IndexError("Índice fuera de rango")
        self.datos[indice] = valor

    def append(self, valor):
        if self.longitud >= self.capacidad:
            self._redimensionar()
        self.datos[self.longitud] = valor
        self.longitud += 1

    def _redimensionar(self):
        nueva_capacidad = self.capacidad * 2
        nuevos_datos = [None] * nueva_capacidad
        for i in range(self.longitud):
            nuevos_datos[i] = self.datos[i]
        self.datos = nuevos_datos
        self.capacidad = nueva_capacidad

# Uso del array personalizado
arr = MiArray(3)
arr.append(10)
arr.append(20)
arr.append(30)
arr.append(40)  # Se redimensiona automáticamente
print(f"Array: {[arr[i] for i in range(arr.longitud)]}")

Listas enlazadas

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

class ListaEnlazada:
    def __init__(self):
        self.cabeza = None
        self.longitud = 0

    def append(self, valor):
        nuevo_nodo = Nodo(valor)
        if not self.cabeza:
            self.cabeza = nuevo_nodo
        else:
            actual = self.cabeza
            while actual.siguiente:
                actual = actual.siguiente
            actual.siguiente = nuevo_nodo
        self.longitud += 1

    def __getitem__(self, indice):
        if indice < 0 or indice >= self.longitud:
            raise IndexError("Índice fuera de rango")

        actual = self.cabeza
        for _ in range(indice):
            actual = actual.siguiente
        return actual.valor

    def insert(self, indice, valor):
        if indice < 0 or indice > self.longitud:
            raise IndexError("Índice fuera de rango")

        nuevo_nodo = Nodo(valor)

        if indice == 0:
            nuevo_nodo.siguiente = self.cabeza
            self.cabeza = nuevo_nodo
        else:
            actual = self.cabeza
            for _ in range(indice - 1):
                actual = actual.siguiente
            nuevo_nodo.siguiente = actual.siguiente
            actual.siguiente = nuevo_nodo

        self.longitud += 1

# Uso de lista enlazada
lista = ListaEnlazada()
lista.append(10)
lista.append(20)
lista.append(30)
lista.insert(1, 15)
print(f"Lista enlazada: {[lista[i] for i in range(lista.longitud)]}")

Paso 3: Pilas y colas

Pilas (LIFO - Last In, First Out)

class Pila:
    def __init__(self):
        self.datos = []

    def push(self, elemento):
        self.datos.append(elemento)

    def pop(self):
        if self.esta_vacia():
            raise Exception("Pila vacía")
        return self.datos.pop()

    def peek(self):
        if self.esta_vacia():
            raise Exception("Pila vacía")
        return self.datos[-1]

    def esta_vacia(self):
        return len(self.datos) == 0

    def __len__(self):
        return len(self.datos)

# Uso de pila - Ejemplo: Revertir cadena
def revertir_cadena(cadena):
    pila = Pila()
    for char in cadena:
        pila.push(char)

    resultado = []
    while not pila.esta_vacia():
        resultado.append(pila.pop())

    return ''.join(resultado)

print(f"Python revertido: {revertir_cadena('Python')}")

Colas (FIFO - First In, First Out)

from collections import deque

class Cola:
    def __init__(self):
        self.datos = deque()

    def enqueue(self, elemento):
        self.datos.append(elemento)

    def dequeue(self):
        if self.esta_vacia():
            raise Exception("Cola vacía")
        return self.datos.popleft()

    def front(self):
        if self.esta_vacia():
            raise Exception("Cola vacía")
        return self.datos[0]

    def esta_vacia(self):
        return len(self.datos) == 0

    def __len__(self):
        return len(self.datos)

# Uso de cola - Ejemplo: Sistema de tickets
sistema_tickets = Cola()
sistema_tickets.enqueue("Ticket #001")
sistema_tickets.enqueue("Ticket #002")
sistema_tickets.enqueue("Ticket #003")

print("Atendiendo tickets:")
while not sistema_tickets.esta_vacia():
    print(f"Atendiendo: {sistema_tickets.dequeue()}")

Paso 4: Árboles y grafos

Árbol binario

class NodoArbol:
    def __init__(self, valor):
        self.valor = valor
        self.izquierda = None
        self.derecha = None

class ArbolBinario:
    def __init__(self):
        self.raiz = None

    def insertar(self, valor):
        if self.raiz is None:
            self.raiz = NodoArbol(valor)
        else:
            self._insertar_recursivo(self.raiz, valor)

    def _insertar_recursivo(self, nodo, valor):
        if valor < nodo.valor:
            if nodo.izquierda is None:
                nodo.izquierda = NodoArbol(valor)
            else:
                self._insertar_recursivo(nodo.izquierda, valor)
        else:
            if nodo.derecha is None:
                nodo.derecha = NodoArbol(valor)
            else:
                self._insertar_recursivo(nodo.derecha, valor)

    def inorden(self):
        return self._inorden_recursivo(self.raiz, [])

    def _inorden_recursivo(self, nodo, resultado):
        if nodo:
            self._inorden_recursivo(nodo.izquierda, resultado)
            resultado.append(nodo.valor)
            self._inorden_recursivo(nodo.derecha, resultado)
        return resultado

# Uso del árbol binario
arbol = ArbolBinario()
for valor in [50, 30, 70, 20, 40, 60, 80]:
    arbol.insertar(valor)

print(f"Recorrido inorden: {arbol.inorden()}")

Grafos

class Grafo:
    def __init__(self):
        self.adyacencia = {}

    def agregar_vertice(self, vertice):
        if vertice not in self.adyacencia:
            self.adyacencia[vertice] = []

    def agregar_arista(self, vertice1, vertice2):
        if vertice1 in self.adyacencia and vertice2 in self.adyacencia:
            self.adyacencia[vertice1].append(vertice2)
            self.adyacencia[vertice2].append(vertice1)

    def bfs(self, inicio):
        visitados = set()
        cola = [inicio]
        resultado = []

        while cola:
            vertice = cola.pop(0)
            if vertice not in visitados:
                visitados.add(vertice)
                resultado.append(vertice)
                cola.extend(self.adyacencia[vertice])

        return resultado

    def dfs(self, inicio):
        visitados = set()
        return self._dfs_recursivo(inicio, visitados, [])

    def _dfs_recursivo(self, vertice, visitados, resultado):
        if vertice not in visitados:
            visitados.add(vertice)
            resultado.append(vertice)
            for vecino in self.adyacencia[vertice]:
                self._dfs_recursivo(vecino, visitados, resultado)
        return resultado

# Uso del grafo
grafo = Grafo()
for ciudad in ["Madrid", "Barcelona", "Valencia", "Sevilla"]:
    grafo.agregar_vertice(ciudad)

grafo.agregar_arista("Madrid", "Barcelona")
grafo.agregar_arista("Madrid", "Valencia")
grafo.agregar_arista("Barcelona", "Valencia")
grafo.agregar_arista("Valencia", "Sevilla")

print(f"BFS desde Madrid: {grafo.bfs('Madrid')}")
print(f"DFS desde Madrid: {grafo.dfs('Madrid')}")

Paso 5: Tablas hash y diccionarios

Implementación de tabla hash

class TablaHash:
    def __init__(self, capacidad=10):
        self.capacidad = capacidad
        self.tabla = [[] for _ in range(capacidad)]
        self.tamaño = 0

    def _hash(self, clave):
        return hash(clave) % self.capacidad

    def insertar(self, clave, valor):
        indice = self._hash(clave)
        for i, (k, v) in enumerate(self.tabla[indice]):
            if k == clave:
                self.tabla[indice][i] = (clave, valor)
                return
        self.tabla[indice].append((clave, valor))
        self.tamaño += 1

        # Redimensionar si el factor de carga es alto
        if self.tamaño / self.capacidad > 0.7:
            self._redimensionar()

    def obtener(self, clave):
        indice = self._hash(clave)
        for k, v in self.tabla[indice]:
            if k == clave:
                return v
        raise KeyError(f"Clave no encontrada: {clave}")

    def _redimensionar(self):
        nueva_capacidad = self.capacidad * 2
        nueva_tabla = [[] for _ in range(nueva_capacidad)]

        for cubeta in self.tabla:
            for clave, valor in cubeta:
                nuevo_indice = hash(clave) % nueva_capacidad
                nueva_tabla[nuevo_indice].append((clave, valor))

        self.tabla = nueva_tabla
        self.capacidad = nueva_capacidad

# Uso de tabla hash
th = TablaHash()
th.insertar("nombre", "Ana")
th.insertar("edad", 25)
th.insertar("ciudad", "Madrid")

print(f"Nombre: {th.obtener('nombre')}")
print(f"Edad: {th.obtener('edad')}")

Paso 6: Algoritmos de ordenamiento eficientes

QuickSort

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivote = arr[len(arr) // 2]
    izquierda = [x for x in arr if x < pivote]
    medio = [x for x in arr if x == pivote]
    derecha = [x for x in arr if x > pivote]

    return quicksort(izquierda) + medio + quicksort(derecha)

# Versión in-place (más eficiente en memoria)
def quicksort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low < high:
        pi = _particion(arr, low, high)
        quicksort_inplace(arr, low, pi - 1)
        quicksort_inplace(arr, pi + 1, high)

def _particion(arr, low, high):
    pivote = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivote:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Prueba
numeros = [64, 34, 25, 12, 22, 11, 90]
quicksort_inplace(numeros)
print(f"QuickSort: {numeros}")

MergeSort

def mergesort(arr):
    if len(arr) <= 1:
        return arr

    medio = len(arr) // 2
    izquierda = mergesort(arr[:medio])
    derecha = mergesort(arr[medio:])

    return _merge(izquierda, derecha)

def _merge(izquierda, derecha):
    resultado = []
    i = j = 0

    while i < len(izquierda) and j < len(derecha):
        if izquierda[i] <= derecha[j]:
            resultado.append(izquierda[i])
            i += 1
        else:
            resultado.append(derecha[j])
            j += 1

    resultado.extend(izquierda[i:])
    resultado.extend(derecha[j:])
    return resultado

# Prueba
numeros = [64, 34, 25, 12, 22, 11, 90]
ordenado = mergesort(numeros)
print(f"MergeSort: {ordenado}")

Paso 7: Análisis de complejidad

Comparativa de estructuras de datos

# Complejidades Big O comunes
complejidades = {
    "Array": {
        "Acceso": "O(1)",
        "Búsqueda": "O(n)",
        "Inserción": "O(n)",
        "Eliminación": "O(n)"
    },
    "Lista Enlazada": {
        "Acceso": "O(n)",
        "Búsqueda": "O(n)",
        "Inserción": "O(1)",
        "Eliminación": "O(1)"
    },
    "Tabla Hash": {
        "Acceso": "O(1)",
        "Búsqueda": "O(1)",
        "Inserción": "O(1)",
        "Eliminación": "O(1)"
    },
    "Árbol Binario Balanceado": {
        "Acceso": "O(log n)",
        "Búsqueda": "O(log n)",
        "Inserción": "O(log n)",
        "Eliminación": "O(log n)"
    }
}

print("Complejidades Big O:")
for estructura, ops in complejidades.items():
    print(f"\n{estructura}:")
    for operacion, complejidad in ops.items():
        print(f"  {operacion}: {complejidad}")

Algoritmos de ordenamiento

complejidades_ordenamiento = {
    "Bubble Sort": {
        "Mejor caso": "O(n)",
        "Caso promedio": "O(n²)",
        "Peor caso": "O(n²)",
        "Espacio": "O(1)"
    },
    "QuickSort": {
        "Mejor caso": "O(n log n)",
        "Caso promedio": "O(n log n)",
        "Peor caso": "O(n²)",
        "Espacio": "O(log n)"
    },
    "MergeSort": {
        "Mejor caso": "O(n log n)",
        "Caso promedio": "O(n log n)",
        "Peor caso": "O(n log n)",
        "Espacio": "O(n)"
    },
    "HeapSort": {
        "Mejor caso": "O(n log n)",
        "Caso promedio": "O(n log n)",
        "Peor caso": "O(n log n)",
        "Espacio": "O(1)"
    }
}

print("\nComplejidades de Ordenamiento:")
for algoritmo, comp in complejidades_ordenamiento.items():
    print(f"\n{algoritmo}:")
    for caso, complejidad in comp.items():
        print(f"  {caso}: {complejidad}")

Paso 8: Proyecto completo - sistema de recomendación simple

class SistemaRecomendacion:
    def __init__(self):
        self.usuarios = {}  # {user_id: {item_id: rating}}
        self.items = {}     # {item_id: {feature: value}}

    def agregar_calificacion(self, usuario_id, item_id, calificacion):
        if usuario_id not in self.usuarios:
            self.usuarios[usuario_id] = {}
        self.usuarios[usuario_id][item_id] = calificacion

    def agregar_item(self, item_id, caracteristicas):
        self.items[item_id] = caracteristicas

    def similitud_coseno(self, vector_a, vector_b):
        # Calcular similitud del coseno entre dos vectores
        dot_product = sum(a * b for a, b in zip(vector_a, vector_b))
        norm_a = sum(a ** 2 for a in vector_a) ** 0.5
        norm_b = sum(b ** 2 for b in vector_b) ** 0.5

        if norm_a == 0 or norm_b == 0:
            return 0
        return dot_product / (norm_a * norm_b)

    def recomendar(self, usuario_id, n_recomendaciones=5):
        if usuario_id not in self.usuarios:
            return []

        # Obtener calificaciones del usuario
        calificaciones_usuario = self.usuarios[usuario_id]

        # Calcular similitud con otros usuarios
        similitudes = {}
        for otro_usuario in self.usuarios:
            if otro_usuario == usuario_id:
                continue

            # Crear vectores de calificaciones
            vector_actual = []
            vector_otro = []

            for item_id in set(calificaciones_usuario.keys()) | set(self.usuarios[otro_usuario].keys()):
                rating_actual = calificaciones_usuario.get(item_id, 0)
                rating_otro = self.usuarios[otro_usuario].get(item_id, 0)

                if rating_actual != 0 and rating_otro != 0:
                    vector_actual.append(rating_actual)
                    vector_otro.append(rating_otro)

            if vector_actual and vector_otro:
                similitud = self.similitud_coseno(vector_actual, vector_otro)
                similitudes[otro_usuario] = similitud

        # Ordenar usuarios por similitud
        usuarios_similares = sorted(similitudes.items(), key=lambda x: x[1], reverse=True)

        # Generar recomendaciones
        recomendaciones = {}
        for usuario_similar, similitud in usuarios_similares[:3]:  # Top 3 usuarios similares
            for item_id, rating in self.usuarios[usuario_similar].items():
                if item_id not in calificaciones_usuario:  # No recomendar items ya vistos
                    if item_id not in recomendaciones:
                        recomendaciones[item_id] = 0
                    recomendaciones[item_id] += rating * similitud

        return sorted(recomendaciones.items(), key=lambda x: x[1], reverse=True)[:n_recomendaciones]

# Uso del sistema de recomendación
sistema = SistemaRecomendacion()

# Agregar items (películas con características numéricas)
sistema.agregar_item("matrix", {"accion": 0.9, "drama": 0.3, "comedia": 0.1})
sistema.agregar_item("toy_story", {"accion": 0.2, "drama": 0.1, "comedia": 0.9})
sistema.agregar_item("inception", {"accion": 0.8, "drama": 0.6, "comedia": 0.1})

# Agregar calificaciones de usuarios
sistema.agregar_calificacion("ana", "matrix", 5.0)
sistema.agregar_calificacion("ana", "toy_story", 4.5)
sistema.agregar_calificacion("carlos", "matrix", 4.0)
sistema.agregar_calificacion("carlos", "inception", 5.0)

# Obtener recomendaciones
recomendaciones_ana = sistema.recomendar("ana")
print(f"Recomendaciones para Ana: {recomendaciones_ana}")

Paso 9: Ejercicios de práctica

# Ejercicio 1: Implementar un Heap (Montículo)
class MinHeap:
    def __init__(self):
        self.heap = []

    def insertar(self, valor):
        self.heap.append(valor)
        self._flotar(len(self.heap) - 1)

    def extraer_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._hundir(0)
        return min_val

    def _flotar(self, indice):
        padre = (indice - 1) // 2
        while indice > 0 and self.heap[indice] < self.heap[padre]:
            self.heap[indice], self.heap[padre] = self.heap[padre], self.heap[indice]
            indice = padre
            padre = (indice - 1) // 2

    def _hundir(self, indice):
        tamaño = len(self.heap)
        while True:
            izquierdo = 2 * indice + 1
            derecho = 2 * indice + 2
            menor = indice

            if izquierdo < tamaño and self.heap[izquierdo] < self.heap[menor]:
                menor = izquierdo
            if derecho < tamaño and self.heap[derecho] < self.heap[menor]:
                menor = derecho

            if menor == indice:
                break

            self.heap[indice], self.heap[menor] = self.heap[menor], self.heap[indice]
            indice = menor

# Ejercicio 2: Encontrar el camino más corto (BFS)
def camino_mas_corto(grafo, inicio, fin):
    from collections import deque
    cola = deque([(inicio, [inicio])])
    visitados = set([inicio])

    while cola:
        vertice, camino = cola.popleft()
        if vertice == fin:
            return camino

        for vecino in grafo.adyacencia.get(vertice, []):
            if vecino not in visitados:
                visitados.add(vecino)
                cola.append((vecino, camino + [vecino]))

    return None

# Probamos el camino más corto
grafo_ejemplo = Grafo()
for ciudad in ["A", "B", "C", "D", "E"]:
    grafo_ejemplo.agregar_vertice(ciudad)

grafo_ejemplo.agregar_arista("A", "B")
grafo_ejemplo.agregar_arista("A", "C")
grafo_ejemplo.agregar_arista("B", "D")
grafo_ejemplo.agregar_arista("C", "D")
grafo_ejemplo.agregar_arista("D", "E")

print(f"Camino más corto de A a E: {camino_mas_corto(grafo_ejemplo.adyacencia, 'A', 'E')}")

Paso 10: Próximos pasos en estructuras de datos

Temas para profundizar:

• Estructuras de datos avanzadas: Árboles AVL, B-Trees, Grafos dirigidos
• Algoritmos de búsqueda: Binary search, Interpolation search
• Estructuras persistentes: Versiones inmutables de estructuras de datos
• Estructuras de datos probabilísticas: Bloom filters, Skip lists

Paso 11: Recursos y herramientas

Recursos para aprender más:

• Introduction to Algorithms: Cormen, Leiserson, Rivest, Stein
• Data Structures and Algorithms in Python: Goodrich, Tamassia, Goldwasser
• Algorithm Design Manual: Steven Skiena

Plataformas de práctica:

• LeetCode: Problemas de algoritmos
• HackerRank: Desafíos de estructuras de datos
• CodeSignal: Evaluaciones de habilidades
• VisuAlgo: Visualizaciones de algoritmos

Proyectos para implementar:

• Motor de búsqueda simple
• Sistema de caching con LRU
• Compresor de archivos básico
• Juego de puzzle con pathfinding

Conclusión

¡Felicidades! Has explorado el fascinante mundo de las estructuras de datos y algoritmos. Practica estos conceptos en proyectos reales y mide el impacto de cada técnica de optimización.

Para más tutoriales sobre algoritmos y estructuras de datos avanzadas, visita nuestra sección de tutoriales.

¡Con estos conocimientos ya puedes escribir código eficiente y escalable!

💡 Tip Importante

📝 Mejores Prácticas para Estructuras de Datos y Algoritmos

Para elegir e implementar estructuras de datos eficientes, considera estos consejos esenciales:

• Analiza los patrones de acceso: ¿Necesitas acceso rápido por índice, búsqueda frecuente, o inserciones/elimininaciones rápidas?
• Considera la complejidad: Evalúa Big O para tiempo y espacio antes de elegir una estructura
• Empieza simple: Usa arrays y listas para casos simples, estructuras avanzadas solo cuando sea necesario
• Mide el rendimiento: Benchmarkea diferentes opciones con datos reales de tu aplicación
• Documenta tus decisiones: Explica por qué elegiste una estructura específica en tu código
• Mantén la consistencia: Usa las mismas estructuras de datos en partes similares de tu aplicación
• Considera la concurrencia: Piensa en acceso concurrente si múltiples hilos usarán la estructura
• Revisa y refactoriza: Mejora las estructuras de datos a medida que cambian los requerimientos

📚 Documentación: Revisa recursos sobre algoritmos en GeeksforGeeks y LeetCode

¡Estos consejos te ayudarán a elegir las estructuras de datos correctas para cada problema!