Semana 8 - Listas Doblemente Enlazadas

 Listas Doblemente Enlazadas

Esta semana evolucionamos nuestra estructura de lista un paso más allá. En una lista simplemente enlazada (Semanas 4-7), la navegación es unidireccional: solo podemos avanzar (.sig). En una lista doblemente enlazada, cada nodo se vuelve más complejo y contiene dos punteros: sig (para el siguiente nodo) y ant (para el nodo anterior). Esto nos da el poder de recorrer la lista en ambas direcciones (hacia adelante y hacia atrás), resolviendo problemas donde necesitamos acceder al predecesor de un nodo.

El desafío de esta semana fue manejar la complejidad adicional de los punteros. El costo es obvio: más memoria por cada nodo (para el puntero ant) y operaciones de inserción y borrado más delicadas, ya que hay más "cables" que conectar y desconectar. La estructura del nodo ahora es: (Nodo ant, int info, Nodo sig). El puntero raiz sigue apuntando al inicio. El primer nodo tiene ant = null y el último nodo tiene sig = null.

La operación de insertar(pos, x) en medio de la lista es el ejemplo perfecto de esta complejidad. Si queremos insertar nuevo entre reco y siguiente (donde reco es el nodo en pos-2 y siguiente = reco.sig):

• En una lista simple, solo actualizábamos 2 punteros (reco.sig = nuevo y nuevo.sig = siguiente).

• En una lista doble, debemos actualizar 4 punteros para mantener la integridad de la cadena en ambas direcciones:

  1. reco.sig = nuevo (El anterior apunta hacia adelante al nuevo).

  2. nuevo.ant = reco (El nuevo apunta hacia atrás al anterior).

  3. nuevo.sig = siguiente (El nuevo apunta hacia adelante al siguiente).

  4. siguiente.ant = nuevo (El siguiente apunta hacia atrás al nuevo).

De manera similar, la operación borrar(pos) en medio (borrar prox) requiere "puentear" en ambas direcciones. Se debe encontrar el nodo anterior (reco) y el nodo siguiente (siguiente = prox.sig):

1. reco.sig = siguiente (El anterior "salta" al siguiente).

2. if (siguiente != null) siguiente.ant = reco (El siguiente "salta" hacia atrás al anterior).

Conclusión 

La lista doblemente enlazada es otro ejemplo perfecto de un balance (trade-off). El costo es claro: cada nodo ocupa más memoria (porque tiene dos punteros, ant y sig) y la lógica para insertar y borrar es más compleja (hay que reconectar 4 enlaces en lugar de 2), lo que aumenta el riesgo de errores. El beneficio es una flexibilidad inmensa. Como estudiante, veo su valor en aplicaciones que uso todos los días: el botón "Atrás" de un navegador web (que necesita ir al nodo anterior), el botón "Canción Anterior" en un reproductor de música, o un editor de texto donde puedes mover el cursor en ambas direcciones. Me enseña que a veces vale la pena pagar un costo en memoria y complejidad para ganar una funcionalidad que es crucial para el usuario.

Semana 7 - Listas Genéricas Ordenadas

 Listas Genéricas Ordenadas

 Esta semana añadimos una restricción o "regla de negocio" directamente en nuestra estructura de datos: la lista debe permanecer ordenada (de menor a mayor) en todo momento. Esto cambia fundamentalmente la lógica de inserción. Ya no le preguntamos al usuario dónde insertar (la pos); el usuario solo nos da el dato (x), y la estructura de datos es responsable de encontrar la posición correcta para mantener el orden.

El método insertar(int x) se convierte en el núcleo de esta estructura. Ya no recibe un parámetro pos. La lógica debe analizar la información del nuevo elemento x y compararla con los nodos existentes para encontrar su lugar:

• Caso 1: Lista Vacía. Si raiz == null, el nuevo nodo se convierte en la raiz.
• Caso 2: x es el menor de todos. Si x < raiz.info, el nuevo nodo debe ir al inicio. La lógica es idéntica a un push de Pila: nuevo.sig = raiz, raiz = nuevo.

• Caso 3: x va en medio o al final. Este es el caso más complejo, y la diapositiva muestra una técnica de punteros clásica. Necesitamos recorrer la lista para encontrar el punto de inserción. Para ello, usamos dos punteros:

  Nodo reco = raiz;
• Nodo atras = raiz; Iniciamos un bucle while que avanza siempre que x sea mayor o igual al nodo actual (x >= reco.info) y no hayamos llegado al final (reco.sig != null). Dentro del bucle, atras siempre se mueve a la posición de reco antes de que reco avance: atras = reco; reco = reco.sig;. Cuando el bucle se detiene, atras apunta al nodo anterior al punto de inserción y reco al nodo siguiente.
• Sub-caso A (Insertar al final): Si el bucle terminó y x >= reco.info, significa que x es el mayor de todos y se inserta al final: reco.sig = nuevo;.
• Sub-caso B (Insertar en medio): Si el bucle terminó porque x < reco.info, encontramos el punto de inserción. Debemos insertar nuevo entre atras y reco. Hacemos: nuevo.sig = reco; y atras.sig = nuevo;.

Conclusión 

Esta semana fue una lección importante de diseño de software. Es el claro ejemplo de un "trade-off" (un balance). Hacemos que la operación de insertar sea más lenta (ahora es O(n), porque en el peor caso debemos recorrer toda la lista para buscar la posición). ¿Cuál es el beneficio? Que la lista siempre está ordenada. Esto significa que la lógica del resto de mi programa se vuelve mucho más simple. Si quiero mostrar una lista de "mejores puntuaciones", no necesito llamar a un método sort() cada vez; simplemente imprimo la lista. Encontrar el valor mínimo es instantáneo (O(1)), solo tengo que ver raiz.info. Esto me enseña como ingeniero a tomar decisiones: a veces, es mejor hacer una operación más costosa para garantizar que los datos siempre estén consistentes y sean fáciles de usar.

Semana 6 - Listas Genéricas (Simplemente Enlazadas)

Listas Genéricas (Simplemente Enlazadas)

Después de estudiar las Pilas y Colas, que son estructuras con reglas restrictivas sobre dónde se insertan y eliminan datos (solo en los extremos), pasamos a la estructura más flexible: la Lista Genérica. Como vimos en la diapositiva, en esta estructura "las inserciones y extracciones se realizan en cualquier parte de la lista". El usuario tiene control total y puede insertar, extraer o eliminar nodos en cualquier posición de la lista, ya sea al inicio, al final o en medio.

El objetivo fue construir una lista genérica simplemente enlazada desde cero, implementando métodos que reciben la posición (pos) como parámetro. La operación más compleja e instructiva fue insertar(int pos, int x). Para implementarla correctamente, debimos manejar tres casos distintos:

• Insertar al inicio (si pos == 1): La lógica es idéntica a un push en una Pila. El nuevo nodo apunta a la raiz actual, y la raiz se actualiza para apuntar al nuevo nodo. Es una operación O(1).
• Insertar al final (si pos == cantidad() + 1): No tenemos un puntero fondo. Por lo tanto, debemos recorrer toda la lista hasta encontrar el último nodo (aquel cuyo reco.sig == null). Usamos un puntero reco que avanza con reco = reco.sig. Una vez encontrado, enlazamos ese último nodo con el nuevo (reco.sig = nuevo). Esta es una operación O(n).
• Insertar en medio (el caso else): Este es el caso más delicado. Para insertar en la posición pos, debemos iterar hasta la posición anterior a la deseada. La diapositiva muestra un for que itera hasta pos - 2. Usamos un puntero reco para llegar a ese nodo. Una vez en el nodo anterior al punto de inserción, realizamos dos enlaces: 
• a. Guardamos la referencia al nodo siguiente: Nodo siguiente = reco.sig. 
• b. Enlazamos el nodo anterior (reco) al nuevo: reco.sig = nuevo.
•  c. Enlazamos el nuevo nodo al resto de la lista: nuevo.sig = siguiente. La lógica para borrar(pos) es muy similar: debemos avanzar hasta el nodo anterior al que queremos borrar (pos - 2) y "puentearlo", haciendo que reco.sig apunte a reco.sig.sig (al nodo prox.sig según la diapositiva).

Conclusión 

 Implementar una lista genérica desde cero es un rito de paso para un programador. Es la primera vez que realmente tengo que "manejar la memoria" y los punteros (referencias) manualmente. Aunque en el futuro usaré las implementaciones de las librerías (como LinkedList en Java), haberla construido yo mismo me permite entender qué está pasando "bajo el capó". Me enseña a depurar errores complejos (como un NullPointerException porque un enlace .sig se rompió). Sobre todo, me enseña el costo real de las operaciones: ahora entiendo por qué insertar en medio de un arreglo es lento (hay que mover todos los elementos a la derecha), mientras que en una lista enlazada es rápido (solo se reconectan dos punteros).

Semana 5 - Listas Tipo Cola (FIFO)

 Listas Tipo Cola (FIFO)

Continuando con las estructuras lineales, esta semana exploramos las Colas (Queues). A diferencia de las pilas, las colas operan bajo el principio FIFO (First In, First Out): el primer elemento que entra es el primero que sale. Replican exactamente el comportamiento de una fila de espera en la vida real: el primero en llegar es el primero en ser atendido.

La implementación de una cola es un desafío de diseño interesante. Necesita dos operaciones rápidas: insertar (al final de la fila) y extraer (desde el inicio de la fila). Si usáramos solo el puntero raiz (como en la pila), extraer() sería O(1), pero insertar() al final requeriría recorrer toda la lista hasta el último nodo, convirtiéndolo en una operación lenta O(n). La solución, como vimos en las diapositivas, es usar dos punteros externos  :

raiz: Apunta al frente de la cola (por donde salen los elementos).
fondo: Apunta al final de la cola (por donde entran los elementos).

Con este diseño, ambas operaciones se vuelven O(1):

• insertar(int info) (Enqueue):

  Se crea el nuevo nodo (nuevo = new Nodo(), nuevo.sig = null). 

Caso 1: Cola vacía (if (vacia())). Si está vacía, raiz y fondo deben apuntar al mismo (y único) nodo: raiz = nuevo; fondo = nuevo;.

 

Caso 2: Cola con elementos. Solo necesitamos interactuar con el puntero fondo: a. Enlazamos el nodo que era el último con el nuevo: fondo.sig = nuevo. b. Movemos el puntero fondo para que apunte al nuevo último: fondo = nuevo.

 

• extraer() (Dequeue):

  (Verificamos que no esté vacía).
• Guardamos la información: int informacion = raiz.info.
• Caso especial: Queda un solo nodo. Si raiz == fondo, significa que estamos extrayendo el último elemento. Debemos resetear la cola: raiz = null; fondo = null;.
• Caso normal: Simplemente avanzamos raiz al siguiente: raiz = raiz.sig.
• Retornamos la informacion.

Las colas son esenciales para la gestión de tareas y recursos. Como Ingeniero de Software, las usaré para administrar trabajos de impresión, manejar solicitudes en servidores web (para que sean atendidas en orden), procesar datos de forma asíncrona (colas de mensajes), o implementar algoritmos de búsqueda en grafos (BFS - Búsqueda en Anchura). Saber construir una cola eficiente (con inserción y extracción en O(1)) es vital para crear sistemas justos, ordenados y responsivos.

SEMANA 4 - Listas Colas y Pilas

 Listas Colas y Pilas

Esta semana dimos el salto de las estructuras estáticas (arreglos) a las dinámicas. Una lista enlazada es una estructura de datos lineal que resuelve el problema de la rigidez de los arreglos. No almacena datos en bloques contiguos de memoria, sino que utiliza nodos. Cada nodo es un objeto que contiene (según las diapositivas) dos partes: info (el dato) y sig (un puntero o referencia al siguiente nodo). Esta cadena de nodos permite que la estructura crezca y decrezca dinámicamente.

Lista tipo Cola

Lista tipo Pila

Nos enfocamos en un tipo específico de lista: la Pila (Stack). Esta es una estructura de datos que obedece al principio LIFO (Last In, First Out): el último elemento que entra es el primero que sale. La analogía perfecta es una pila de platos: solo puedes añadir o quitar platos desde arriba (el "tope"). Implementamos la Pila usando una lista enlazada simple. 

La clave es tener un solo puntero externo, raiz (o top), que siempre apunta al primer nodo (el "tope" de la pila).

• insertar(int x) (Push): Esta operación añade un elemento al tope. La lógica es simple y muy rápida (O(1)):

  1. Se crea un nuevo nodo (nuevo = new Nodo()).

  2. Se asigna la información (nuevo.info = x).

  3. Se enlaza el nuevo nodo al resto de la lista: nuevo.sig = raiz. (El nuevo nodo apunta al antiguo tope).

  4. Se actualiza el tope: raiz = nuevo. (La raiz ahora apunta al nuevo nodo).

• extraer() (Pop): Esta operación elimina el elemento del tope y devuelve su valor. También es O(1):

  1. Verificamos que la pila no esté vacía (if (raiz != null)).

  2. Guardamos la información del tope en una variable temporal (int informacion = raiz.info).

  3. Avanzamos la raiz al siguiente nodo: raiz = raiz.sig. (El segundo nodo se convierte en el nuevo tope).

  4. Se retorna la informacion. El nodo que era el tope queda sin referencias y el recolector de basura de Java lo elimina.

Conclusión

  Las pilas son una de las estructuras más útiles y comunes en el software. Como estudiante de ingeniería, el ejemplo más claro que puedo ver es la función "Deshacer" (Ctrl+Z) en cualquier programa (un editor de texto, un programa de dibujo, etc.). Cada vez que realizas una acción (como escribir una palabra), esa acción se "apila" (push) en una pila. Cuando presionas "Deshacer", el programa simplemente "desapila" (pop) la última acción y la revierte.

De forma interna, los lenguajes de programación usan pilas constantemente para funcionar. Cuando un programa llama a una función, y esa función llama a otra, el sistema "apila" la información de dónde debe regresar. Cuando una función termina, "desapila" la última instrucción y sabe exactamente a qué línea de código anterior debe volver. Es la forma en que el programa gestiona su propio orden. Entender este principio LIFO (Último en Entrar, Primero en Salir) es crucial porque nos da una herramienta poderosa para manejar tareas y datos que deben ser procesados en orden inverso.

Semana 3 - Complejidad Algorítmica y Notación Big O

 Complejidad Algorítmica y Notación Big O

Un algoritmo es una secuencia finita y precisa de pasos para resolver un problema. Esta semana aprendimos que no todos los algoritmos son iguales. La complejidad algorítmica es el estudio de cuántos recursos (principalmente tiempo de ejecución y espacio en memoria) consume un algoritmo en función del tamaño de sus datos de entrada, que representamos como "n". El objetivo es poder comparar dos algoritmos de forma objetiva y determinar cuál es más eficiente.

Medir la eficiencia con un cronómetro es inútil, ya que depende de la velocidad del procesador, el lenguaje, etc. Por ello, utilizamos la Notación Big O (Gran O). Esta notación describe cómo se comporta un algoritmo en el peor escenario posible, a medida que el tamaño de la entrada n crece. Nos permite ignorar constantes (ej. 2n vs 5n) y enfocarnos en el orden de crecimiento. Las clases de complejidad clave son:

• O(1) (Constante): El tiempo es el mismo sin importar n. (Ej: Acceder a un índice de un arreglo array[5]).
• O(log n) (Logarítmico): El tiempo aumenta muy lentamente. El algoritmo divide el problema en cada paso. (Ej: Búsqueda binaria).
• O(n) (Lineal): El tiempo es directamente proporcional a n. Si n se duplica, el tiempo se duplica. (Ej: Un solo bucle for que recorre un arreglo).
• O(n²) (Cuadrático): El tiempo aumenta exponencialmente. Si n se duplica, el tiempo se cuadruplica. (Ej: Dos bucles for anidados).
• O(2^n), O(n!) (Exponencial/Factorial): Crecimiento explosivo. Son algoritmos que se vuelven inviables muy rápidamente con n pequeños.

Las diapositivas nos mostraron un ejemplo claro con la búsqueda secuencial:

• Mejor Caso (Omega - Ω): Encontrar el elemento en la primera posición. Complejidad: Ω(1).
• Peor Caso (Big O - O): Encontrar el elemento en la última posición, o no encontrarlo. El bucle se ejecuta n veces. Complejidad: O(n).

 

Conclusión

 Este es, para mí, uno de los temas más cruciales. Escribir código que funciona para n=10 es fácil. Escribir código que escala y sigue funcionando eficientemente para n=1,000,000 es el verdadero desafío de la ingeniería. La notación Big O es el lenguaje profesional que usamos para analizar y predecir el rendimiento. Me permite identificar cuellos de botella en un sistema antes de que falle en producción y justificar por qué una solución aparentemente más compleja (como un algoritmo O(n log n)) es superior a una más simple (O(n²)).

Semana 2 - Introducción y Clasificación de las Estructuras de Datos

 Introducción y Clasificación de las Estructuras de Datos

Una estructura de datos es, formalmente, una forma especializada de organizar, almacenar y gestionar datos en la memoria de una computadora. La elección de la estructura de datos es crucial porque no solo almacena datos, sino que también define la eficiencia con la que podemos realizar operaciones sobre ellos (como insertar, buscar o eliminar). No existe una "estructura de datos universal"; cada una es una herramienta diseñada para un conjunto específico de problemas.

Las diapositivas de esta semana clasifican las estructuras de datos en un mapa claro basado en su organización y flexibilidad en memoria:

Estáticas

Son estructuras cuyo tamaño se define en tiempo de compilación y, una vez asignado, no puede cambiar. El ejemplo principal es el Arreglo (Array).

• Ventaja: Acceso a datos extremadamente rápido. El acceso por índice (ej. miArray[10]) es O(1) (constante), ya que la computadora puede calcular la dirección exacta en memoria con una simple aritmética de punteros.
• Desventaja: Rigidez total. Debemos saber de antemano cuántos datos guardaremos, lo que puede llevar a desperdiciar memoria o a que el programa falle si nos quedamos cortos.

Dinámicas

Son estructuras flexibles cuyo tamaño puede crecer o disminuir en tiempo de ejecución, adaptándose a las necesidades del programa. Lo logran usando "nodos" y "punteros" (referencias) para enlazar datos en la memoria. Se subdividen en:

• Lineales: Los elementos se organizan en una secuencia, uno después del otro. Los ejemplos clave son las Listas Enlazadas, las Pilas y las Colas.
• No Lineales: Los elementos no están en secuencia, sino que tienen relaciones más complejas, jerárquicas o de red. Los ejemplos principales son los Árboles (donde cada nodo tiene "hijos") y los Grafos (donde cualquier nodo puede estar conectado a cualquier otro).

Conclusión 

Esta clasificación es el "árbol de decisiones" de un ingeniero de software. Si necesito almacenar 50 valores fijos y acceder a ellos rápidamente por su posición, un arreglo estático es la elección obvia. Si estoy creando un historial de "Deshacer" donde no sé cuántas acciones realizará el usuario, necesito una estructura dinámica lineal como una Pila. Si estoy modelando una red social, necesito una estructura dinámica no lineal como un Grafo. Elegir la estructura incorrecta (ej. una Lista Enlazada cuando necesito acceso por índice constante) puede degradar el rendimiento de una aplicación de "instantánea" a "inusable".

Semana 1 - Tipo de Datos Abstractos (TDA)

 Tipos de Datos Abstractos

Esta semana exploramos el concepto más fundamental de la programación moderna: la abstracción. La abstracción es el proceso de simplificar una realidad compleja, capturando sus características esenciales e ignorando los detalles irrelevantes. 

Un Tipo de Dato Abstracto (TDA) es la materialización de este concepto en el software. Es un modelo (como una Clase en Java) que representa un objeto del mundo real (ej. "Empleado", "CuentaBancaria") y se define por dos componentes: los datos que almacena (atributos) y las operaciones que se pueden realizar sobre él (métodos). El TDA crea lo que se conoce como una barrera de abstracción, permitiéndonos usar el objeto sin necesidad de conocer su complejidad interna.

Un TDA se compone de dos partes estrictamente separadas:

La Interfaz (Pública): Es la "vista externa" del objeto. Define qué se puede hacer con el objeto. Es el conjunto de métodos públicos y, conceptualmente, es un contrato que le dice al resto del programa: "Yo sé cómo depositar(), retirar() y consultarSaldo()".

La Implementación (Privada): Es la "vista interna" u oculta. Define cómo el objeto realiza sus tareas. Es la lógica interna, los algoritmos y los atributos privados. Gracias al encapsulamiento, esta implementación está protegida y puede ser modificada sin afectar a los programas que usan el TDA, siempre y cuando la interfaz (el contrato) se respete.

El ciclo de vida de un TDA sigue un proceso de ingeniería formal:

• Especificación (Diseño): Es el "plano" del TDA. Se definen sus propiedades y las pre/post-condiciones de sus operaciones.
• Implementación (Codificación): Es la traducción de esos planos a un lenguaje de programación (ej. una clase de Java).
• Uso (Aplicación): Es la utilización o instanciación del TDA dentro de un programa más grande.

Conclusión 

Comprender los TDA es, en mi opinión, el pilar de la Ingeniería de Software y la Programación Orientada a Objetos. Como ingeniero, mi trabajo no es solo escribir código, sino construir sistemas que sean modulares, reutilizables y fáciles de mantener. Los TDA me permiten crear "cajas negras" confiables. Puedo construir un sistema financiero usando un TDA CuentaBancaria y confiar en que funciona, sin necesidad de saber cómo implementa internamente sus transacciones. Esto reduce la complejidad, facilita la detección de errores y permite que grandes equipos colaboren, ya que solo necesitamos conocer las interfaces de los componentes de los demás, no sus implementaciones.