Implementación de Listas Enlazadas en C: Inserción Ordenada y Eliminación de Nodos

Ejercicio Práctico 1: Gestión de Listas Enlazadas con Inserción al Final y Eliminación Específica

Este primer ejercicio demuestra la creación de una lista enlazada simple, la inserción de nodos al final de la misma y la posterior eliminación de un nodo específico. Se presta especial atención a la manipulación de punteros para mantener la integridad de la lista.

1.1. Definición de la Estructura y Variables Globales

Se define la estructura básica de un nodo de lista enlazada y se declaran los punteros globales necesarios para su manipulación.

#include <stdio.h>
#include <stdlib.h>

typedef struct nodo
{
    int info;
    struct nodo *sig;
} Nodo;

Nodo *nuevo, *primero, *ultimo, *auxiliar, *P, *nodo; // 'nodo' es un nombre de variable confuso, se recomienda evitarlo.

1.2. Función Principal y Creación de la Lista (Inserción al Final)

La función main inicializa la lista y procede a insertar 7 nodos. Es importante notar que, aunque el comentario original sugiere "ingresando nodos en orden", la implementación actual realiza una inserción al final de la lista.

int main()
{
    int dato, i;
    char r; // Variable 'r' no utilizada en este bloque, pero declarada.

    primero = NULL;
    ultimo = primero; // Ambos apuntan a NULL inicialmente.

    for (i = 0; i < 7; i++)
    {
        printf("\nIngrese dato: ");
        scanf("%d", &dato);

        nuevo = (Nodo*)malloc(sizeof(Nodo));
        if (nuevo == NULL) {
            printf("Error: No se pudo asignar memoria para el nuevo nodo.\n");
            exit(EXIT_FAILURE);
        }
        nuevo->info = dato;
        nuevo->sig = NULL;

        if (primero == NULL)
        {
            primero = nuevo;
            ultimo = nuevo;
        }
        else
        {
            ultimo->sig = nuevo;
            ultimo = nuevo;
        }
    }
    P = primero; // 'P' se establece como el puntero al inicio de la lista.

1.3. Visualización de los Elementos de la Lista

Este segmento de código recorre la lista desde el inicio (apuntado por P) y muestra el valor de cada nodo.

    auxiliar = primero;
    i = 0; // 'i' se reutiliza para contar elementos.

    printf("\n\nMostrar elementos de la lista:");
    while (auxiliar != NULL)
    {
        printf("\nInfo: %d", auxiliar->info);
        auxiliar = auxiliar->sig;
        i++;
    }

    if (i == 0)
        printf("\nLa lista está vacía.");

1.4. Eliminación de un Nodo Específico

Esta sección implementa la lógica para eliminar un nodo cuyo valor coincide con el dato ingresado por el usuario. La implementación busca el nodo a eliminar y su predecesor para realizar la desconexión y liberación de memoria.

    printf("\n\nIngrese dato a eliminar: ");
    scanf("%d", &dato);
    printf("\nIngreso de dato: %d", dato);

    primero = P; // 'primero' se restablece al inicio de la lista.
    ultimo = primero; // 'ultimo' también se restablece.
    P = primero; // 'P' ya apunta al inicio, esta línea es redundante.

    // Búsqueda del nodo a eliminar y su predecesor
    while (ultimo != NULL && ultimo->info < dato)
    {
        primero = ultimo; // 'primero' se convierte en el predecesor.
        ultimo = ultimo->sig; // 'ultimo' avanza al siguiente nodo.
    }

    // Lógica de eliminación
    // ATENCIÓN: La condición original 'ultimo == NULL && ultimo->info == dato' es lógicamente incorrecta.
    // Si 'ultimo' es NULL, 'ultimo->info' causaría un error de segmentación.
    // Se corrige la condición para evitar el error y se mejora la lógica para el caso de eliminación del primer nodo.
    if (ultimo != NULL && ultimo->info == dato) // Corrección: 'ultimo != NULL' debe ir primero.
    {
        if (primero == ultimo) { // Caso: el nodo a eliminar es el primero de la lista
            P = ultimo->sig; // La nueva cabeza es el siguiente nodo
        } else { // Caso: el nodo a eliminar no es el primero
            primero->sig = ultimo->sig;
        }
        nodo = ultimo; // 'nodo' apunta al nodo a liberar.
        r = nodo->info; // Se guarda la información del nodo eliminado.
    }
    else // Si el dato no se encuentra o 'ultimo' es NULL
    {
        // La lógica original en este 'else' era confusa y podría no ser la intención.
        // Si el dato no se encuentra, no se debería modificar la lista ni liberar memoria.
        printf("\nEl dato %d no se encontró en la lista o no se pudo eliminar correctamente.", dato);
        nodo = NULL; // Asegurarse de no liberar un puntero no válido.
    }

    if (nodo != NULL) {
        free(nodo); // Libera la memoria del nodo eliminado.
        printf("\nNodo con info %d eliminado correctamente.", r);
    }

1.5. Visualización de la Lista Después de la Eliminación

Se muestra el estado final de la lista después de la operación de eliminación.

    auxiliar = P; // Se usa 'P' para recorrer la lista desde la posible nueva cabeza.
    i = 0;

    printf("\n\nMostrar elementos de la lista (después de la eliminación):");
    while (auxiliar != NULL)
    {
        printf("\nInfo: %d", auxiliar->info);
        auxiliar = auxiliar->sig;
        i++;
    }

    if (i == 0)
        printf("\nLa lista está vacía.");
    // Fin del primer programa
}

Ejercicio Práctico 2: Gestión de Listas Enlazadas con Inserción Ordenada y Eliminación

Este segundo ejercicio aborda la inserción de nodos en una lista enlazada de forma ordenada, manteniendo la lista siempre clasificada. Posteriormente, se realiza una operación de eliminación similar a la del primer ejercicio.

2.1. Definición de la Estructura y Variables Globales

Se reutiliza la misma definición de estructura de nodo y variables globales que en el ejercicio anterior.

#include <stdio.h>
#include <stdlib.h>

typedef struct nodo
{
    int info;
    struct nodo *sig;
} Nodo;

Nodo *nuevo, *primero, *ultimo, *auxiliar, *P, *nodo;

2.2. Función Principal y Creación de la Lista (Inserción Ordenada)

La función main inicializa la lista y permite la inserción de 5 nodos, asegurando que cada nuevo nodo se inserte en la posición correcta para mantener la lista ordenada.

int main()
{
    int dato, i;
    char r;

    primero = NULL;
    ultimo = primero; // Ambos apuntan a NULL inicialmente.
    P = NULL; // Inicializar P para evitar comportamiento indefinido al inicio.

    for (i = 0; i < 5; i++)
    {
        printf("\nIngrese dato a insertar: ");
        scanf("%d", &dato);

        // Restablecer 'primero' y 'ultimo' para la búsqueda de inserción.
        // 'P' debe ser la cabeza de la lista. Si 'P' es NULL, 'primero' y 'ultimo' también serán NULL.
        // Si 'P' ya tiene un valor, 'primero' y 'ultimo' deben empezar desde 'P'.
        primero = P;
        ultimo = P;

        // Búsqueda de la posición de inserción
        while (ultimo != NULL && ultimo->info < dato)
        {
            primero = ultimo;
            ultimo = ultimo->sig;
        }

        nuevo = (Nodo*)malloc(sizeof(Nodo));
        if (nuevo == NULL) {
            printf("Error: No se pudo asignar memoria para el nuevo nodo.\n");
            exit(EXIT_FAILURE);
        }
        nuevo->info = dato;

        // Lógica de inserción ordenada
        if (P == NULL || primero == P) // Si la lista está vacía o se inserta al principio
        {
            nuevo->sig = P; // El nuevo nodo apunta a la antigua cabeza (o NULL si vacía)
            P = nuevo; // El nuevo nodo se convierte en la nueva cabeza
        }
        else // Inserción en medio o al final
        {
            nuevo->sig = ultimo; // El nuevo nodo apunta al nodo que 'ultimo' estaba apuntando
            primero->sig = nuevo; // El predecesor apunta al nuevo nodo
        }
    }

2.3. Visualización de los Elementos de la Lista

Se muestra el contenido de la lista después de todas las inserciones ordenadas.

    auxiliar = P; // Se usa 'P' como la cabeza de la lista.
    i = 0;

    printf("\n\nMostrar elementos de la lista:");
    while (auxiliar != NULL)
    {
        printf("\nInfo: %d", auxiliar->info);
        auxiliar = auxiliar->sig;
        i++;
    }

    if (i == 0)
        printf("\nLa lista está vacía.");

2.4. Eliminación de un Nodo Específico

Esta sección replica la lógica de eliminación del primer ejercicio, buscando y eliminando un nodo por su valor.

    printf("\n\nIngrese dato a eliminar: ");
    scanf("%d", &dato);

    primero = P; // Restablecer 'primero' al inicio de la lista.
    ultimo = P; // Restablecer 'ultimo' al inicio de la lista.
    // P = primero; // Esta línea es redundante si 'primero' ya es 'P'.

    // Búsqueda del nodo a eliminar y su predecesor
    while (ultimo != NULL && ultimo->info < dato)
    {
        primero = ultimo;
        ultimo = ultimo->sig;
    }

    // Lógica de eliminación (similar al Ejercicio 1)
    if (ultimo != NULL && ultimo->info == dato) // Corrección: 'ultimo != NULL' debe ir primero.
    {
        if (primero == ultimo) { // Caso: el nodo a eliminar es el primero de la lista
            P = ultimo->sig; // La nueva cabeza es el siguiente nodo
        } else { // Caso: el nodo a eliminar no es el primero
            primero->sig = ultimo->sig;
        }
        nodo = ultimo; // 'nodo' apunta al nodo a liberar.
        r = nodo->info; // Se guarda la información del nodo eliminado.
    }
    else
    {
        printf("\nEl dato %d no se encontró en la lista o no se pudo eliminar correctamente.", dato);
        nodo = NULL;
    }

    if (nodo != NULL) {
        free(nodo); // Libera la memoria del nodo eliminado.
        printf("\nNodo con info %d eliminado correctamente.", r);
    }

2.5. Visualización de la Lista Después de la Eliminación

Finalmente, se muestra el estado de la lista después de la operación de eliminación.

    auxiliar = P;
    i = 0;

    printf("\n\nMostrar elementos de la lista (después de la eliminación):");
    while (auxiliar != NULL)
    {
        printf("\nInfo: %d", auxiliar->info);
        auxiliar = auxiliar->sig;
        i++;
    }

    if (i == 0)
        printf("\nLa lista está vacía.");
}