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.