Untitled

#include <iostream>

struct Node {
    char data;
    Node* next;
};

// Head node (starting point of the linked list)
Node* head = nullptr;

// Function to insert at the front (beginning)
void insertFront(char data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

// Function to insert at the rear (end)
void insertRear(char data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = nullptr;

    if (head == nullptr) { // If list is empty
        head = newNode;
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Utility function to insert before a given node
void insertMiddle(Node* beforeNode, char data) {
    if (beforeNode == nullptr) return;

    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = beforeNode->next;
    beforeNode->next = newNode;
}

// Function to display the linked list
void displayList() {
    Node* temp = head;
    while (temp != nullptr) {
        std::cout << temp->data << " -> ";
        temp = temp->next;
    }
    std::cout << "NULL" << std::endl;
}

int main() {
    // Start by inserting 'M' at the rear
    insertRear('M');  // M

    // Insert 'I' at the front
    insertFront('I'); // I -> M

    // Get reference to the middle node
    Node* middle = head; // Initially pointing to 'I'

    // Insert 'L', 'H', 'A' using insertMiddle
    insertMiddle(middle, 'L'); // I -> L -> M
    insertMiddle(middle->next, 'H'); // I -> L -> H -> M
    insertMiddle(middle->next->next, 'A'); // I -> L -> H -> A -> M

    // Display final linked list
    displayList(); // Expected output: I -> L -> H -> A -> M -> NULL

    return 0;
}