Introducción a las Listas Enlazadas

Este artículo explora las operaciones fundamentales sobre listas enlazadas simples en C++. Nos enfocaremos en la creación de la lista, la inserción de nuevos elementos en posiciones específicas, la eliminación de nodos existentes y el recorrido de la lista para imprimir su contenido. Estas operaciones son cruciales para comprender cómo manipular estructuras de datos dinámicas.

Definición del Problema

Se solicita desarrollar un programa en C++ que gestione una lista enlazada simple de números enteros. La implementación debe cumplir con los siguientes requisitos:

1. Crear una estructura de datos personalizada para representar los nodos de la lista.
2. Implementar una función o método para construir la lista inicial a partir de una secuencia de enteros.
3. Diseñar una función o método que permita insertar un nuevo nodo con un valor dado en la posición n de la lista.
4. Diseñar una función o método que elimine el nodo ubicado en la posición m de la lista.
5. Implementar una función o método para imprimir todos los elementos de la lista en su orden actual.

La función principal del programa (main) deberá coordinar estas operaciones, primero construyendo una lista, luego procesando una serie de inserciones y finalmente una serie de eliminaciones, mostrando el estado de la lista después de cada cambio.

Formato de Entrada

La entrada se procesa en bloques:

1. La primera línea contiene un entero K, que indica la longitud inicial de la lista enlazada.
2. La segunda línea contiene K enteros, que son los valores para construir la lista inicial.
3. La tercera línea contiene un entero S, que representa el número de operaciones de inserción a seguir.
4. Las siguientes S líneas contienen dos enteros cada una: n (la posición de inserción) y x (el valor a insertar).
5. Después de las S operaciones de inserción, se lee un entero L, indicando el número de operaciones de eliminación.
6. Las siguientes L líneas contienen un entero cada una: m (la posición del nodo a eliminar).

Formato de Salida

La salida se estructura de la siguiente manera:

1. Después de la construcción inicial, se imprime la lista completa, con los elementos separados por espacios y sin un espacio final después del último elemento.
2. Por cada una de las S operaciones de inserción:
   • Si la posición de inserción n es inválida (menor o igual a 0, o mayor que la longitud actual de la lista), se imprime el mensaje "Insertion position is invalid."
   • Si la inserción es válida, se imprime la lista actualizada con el mismo formato.
3. Por cada una de las L operaciones de eliminación:
   • Si la posición de eliminación m es inválida (menor o igual a 0, o mayor que la longitud actual de la lista), se imprime el mensaje "Deletion position is invalid."
   • Si la eliminación es válida y la lista resultante no está vacía, se imprime la lista actualizada.
   • Si la eliminación es válida y la lista resultante queda vacía, no se imprime nada (ni siquiera un salto de línea para la lista).

Ejemplo de Entrada

5
1 2 3 4 5
3
4 3
3 4
9 8
2
1
0

Ejemplo de Salida

1 2 3 3 4 5
1 2 4 3 3 4 5
Insertion position is invalid.
2 4 3 3 4 5
Deletion position is invalid.

Nota Importante

Si la lista queda completamente vacía después de una operación de eliminación (su longitud es 0), no se debe imprimir ninguna representación de la lista.

Estrategias de Implementación

1. Inserción de un Nodo

Para insertar un nuevo nodo en la posición n de una lista enlazada, debemos localizra el nodo que precederá al nuevo elemento. Este es el nodo que se encuentra en la posición n-1. Si se desea insertar al principio (posición 1), el nodo precedente es el nodo centinela (o "dummy head").

El proceso general implica:

1. Crear el nuevo nodo (newNode) con el valor deseado.
2. Identificar el nodo que actualmente se encuentra en la posición n-1 (llamémosle previousNode).
3. Guardar una referencia al nodo que originalmente estaba en la posición n (es decir, previousNode->next), que llamaremos nodeAfterNew.
4. Reconfigurar el puntero next de previousNode para que apunte al newNode.
5. Reconfigurar el puntero next de newNode para que apunte a nodeAfterNew.

// 'previousNode' es el nodo en la posición n-1
// 'valorX' es el valor para el nuevo nodo
Node* nodeAfterNew = previousNode->next; // Guarda el nodo que será el siguiente del nuevo
Node* newNode = new Node(valorX);      // Crea el nuevo nodo
previousNode->next = newNode;          // Enlaza 'previousNode' con 'newNode'
newNode->next = nodeAfterNew;          // Enlaza 'newNode' con 'nodeAfterNew'

2. Eliminación de un Nodo

La eliminación de un nodo en la posición m requiere encontrar el nodo que le precede, es decir, el nodo en la posición m-1 (llamémosle previousNode). Una vez localizado este nodo, podemos "saltar" el nodo a eliminar.

Los pasos son:

1. Identificar el previousNode (el nodo en la posición m-1).
2. El nodo a eliminar es previousNode->next.
3. El puntero next de previousNode se debe reasignar para que apunte al nodo que está inmediatamente después del nodo a eliminar (es decir, previousNode->next->next).

// 'previousNode' es el nodo que precede al que se desea eliminar
// El nodo a eliminar es 'previousNode->next'
Node* targetNode = previousNode->next; // Opcional, si se quiere liberar memoria con 'delete targetNode;'
previousNode->next = targetNode->next; // 'previousNode' ahora enlaza con el nodo siguiente al 'targetNode'
// Si se desea liberar la memoria del nodo eliminado: delete targetNode;

3. Recorrido e Impresión de la Lista

Para mostrar los elementos de la lista enlazada, se inicia un puntero de recorrido desde el primer nodo real (el que sigue al nodo centinela). Este puntero avanza de nodo en nodo hasta que alcanza el final de la lista (un puntero nulo).

Es crucial manejar correctamente los espacios para que no haya un espacio después del último elemento. Una forma es imprimir el valor del nodo y luego un espacio, pero solo si hay un nodo subsiguiente.

void imprimirLista(Node* nodoCentinela) {
    Node* current = nodoCentinela->next; // Inicia desde el primer nodo real
    if (current == nullptr) { // Si la lista está vacía (después del centinela), solo un salto de línea
        std::cout << std::endl;
        return;
    }
    while (current != nullptr) {
        std::cout << current->val;
        current = current->next;
        if (current != nullptr) { // Imprime un espacio solo si hay más elementos
            std::cout << " ";
        }
    }
    std::cout << std::endl; // Siempre termina con un salto de línea
}

Código Completo

#include <iostream> // Para std::cin, std::cout, std::endl

// Definición de la estructura del nodo de la lista enlazada
struct Node {
    int val;    // Valor del nodo
    Node* next; // Puntero al siguiente nodo
    // Constructor para inicializar un nodo
    Node(int x) : val(x), next(nullptr) {}
};

// Función para imprimir los elementos de la lista enlazada
// Recibe el nodo centinela (dummy head)
void imprimirLista(Node* headSentinel) {
    Node* current = headSentinel->next; // Empieza desde el primer nodo real
    if (current == nullptr) {           // Si la lista está vacía (después del centinela)
        std::cout << std::endl;         // Imprime solo un salto de línea
        return;
    }

    // Recorre y imprime los elementos
    while (current != nullptr) {
        std::cout << current->val; // Imprime el valor del nodo actual
        current = current->next;   // Avanza al siguiente nodo
        if (current != nullptr) {  // Si no es el último elemento, imprime un espacio
            std::cout << " ";
        }
    }
    std::cout << std::endl; // Siempre termina con un salto de línea
}

int main() {
    int initialCount, nodeValue;
    // Se crea un nodo centinela (dummy head) para simplificar operaciones en los extremos
    Node* headSentinel = new Node(0);
    int listLength = 0; // Lleva la cuenta de la longitud actual de la lista

    std::cin >> initialCount; // Lee la cantidad de elementos iniciales
    listLength = initialCount; // Inicializa la longitud de la lista

    Node* currentWalker = headSentinel; // Puntero para construir la lista inicial
    for (int i = 0; i < initialCount; ++i) {
        std::cin >> nodeValue;
        Node* freshNode = new Node(nodeValue); // Crea un nuevo nodo
        currentWalker->next = freshNode;       // Lo enlaza a la lista
        currentWalker = freshNode;             // Mueve el walker al nuevo nodo
    }

    // --- Operaciones de Inserción ---
    int insertOperationsCount, insertPosition, valueToInsert;
    std::cin >> insertOperationsCount; // Lee la cantidad de operaciones de inserción

    while (insertOperationsCount--) {
        std::cin >> insertPosition >> valueToInsert;

        // Valida la posición de inserción
        // Posición 1 es válida, hasta 'listLength' + 1 (para insertar al final)
        if (insertPosition <= 0 || insertPosition > listLength + 1) {
            std::cout << "Insertion position is invalid." << std::endl;
            continue; // Salta a la siguiente operación
        }

        currentWalker = headSentinel; // Reinicia el walker al centinela

        // Avanza el walker hasta el nodo que precederá al nuevo nodo
        // Si insertPosition es 1, el bucle no se ejecuta y currentWalker sigue en headSentinel
        for (int i = 1; i < insertPosition; ++i) {
            currentWalker = currentWalker->next;
        }

        // Realiza la inserción
        Node* newNode = new Node(valueToInsert); // Crea el nuevo nodo
        Node* nextSegment = currentWalker->next; // Guarda el nodo siguiente
        currentWalker->next = newNode;           // Enlaza el nodo anterior con el nuevo
        newNode->next = nextSegment;             // Enlaza el nuevo nodo con el siguiente

        listLength++; // Incrementa la longitud de la lista

        imprimirLista(headSentinel); // Imprime la lista después de la inserción
    }

    // --- Operaciones de Eliminación ---
    int deleteOperationsCount, deletePosition;
    std::cin >> deleteOperationsCount; // Lee la cantidad de operaciones de eliminación

    while (deleteOperationsCount--) {
        std::cin >> deletePosition;

        // Valida la posición de eliminación
        if (deletePosition <= 0 || deletePosition > listLength) {
            std::cout << "Deletion position is invalid." << std::endl;
            continue; // Salta a la siguiente operación
        }

        currentWalker = headSentinel; // Reinicia el walker al centinela

        // Avanza el walker hasta el nodo que precede al nodo a eliminar
        for (int i = 1; i < deletePosition; ++i) {
            currentWalker = currentWalker->next;
        }

        // Realiza la eliminación
        Node* nodeToDelete = currentWalker->next; // Nodo a eliminar
        currentWalker->next = nodeToDelete->next; // Salta el nodo a eliminar

        // Opcional: liberar la memoria del nodo eliminado
        // delete nodeToDelete;

        listLength--; // Decrementa la longitud de la lista

        // Imprime la lista solo si no está vacía
        if (listLength != 0) {
            imprimirLista(headSentinel);
        }
    }

    // Opcional: Liberar toda la memoria de la lista al final del programa
    currentWalker = headSentinel;
    while (currentWalker != nullptr) {
        Node* temp = currentWalker;
        currentWalker = currentWalker->next;
        delete temp;
    }

    return 0;
}