recitaitionexam

#include <iostream>
using namespace std;

// Define a Node for the linked list
struct Node {
    int data;
    Node* next;
    
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Singly Linked List
class LinkedList {
private:
    Node* head;
    
public:
    LinkedList() {
        head = nullptr;
    }

    // Function to insert data into the linked list
    void insertData(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
        cout << "Inserted " << value << " into the list." << endl;
    }

    // Function to print the linked list
    void printList() {
        if (!head) {
            cout << "List is empty." << endl;
            return;
        }
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    // Function to perform insertion sort on the linked list
    void insertionSort() {
        if (!head || !head->next) return; // No need to sort if the list is empty or has one element

        Node* sorted = nullptr;
        Node* current = head;
        
        while (current != nullptr) {
            Node* next = current->next; // Store next for next iteration

            // Insert current in sorted linked list
            if (!sorted || sorted->data >= current->data) {
                current->next = sorted;
                sorted = current;
            } else {
                Node* temp = sorted;
                while (temp->next != nullptr && temp->next->data < current->data) {
                    temp = temp->next;
                }
                current->next = temp->next;
                temp->next = current;
            }
            current = next;
        }
        
        head = sorted; // Update head to point to the sorted list
    }
};

int main() {
    LinkedList list;
    int choice, value;

    cout << "Linked List Program - Please choose an option:\n";
    while (true) {
        cout << "1. Insert an integer\n";
        cout << "2. Print the current list (pre-sorted)\n";
        cout << "3. Sort the list using Insertion Sort\n";
        cout << "4. Print the sorted list\n";
        cout << "5. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;

        switch (choice) {
            case 1:
                cout << "Enter the integer to insert: ";
                cin >> value;
                list.insertData(value);
                break;
            case 2:
                cout << "Current list: ";
                list.printList();
                break;
            case 3:
                cout << "Sorting the list using Insertion Sort..." << endl;
                list.insertionSort();
                break;
            case 4:
                cout << "Sorted list: ";
                list.printList();
                break;
            case 5:
                cout << "Exiting..." << endl;
                return 0;
            default:
                cout << "Invalid choice. Please try again." << endl;
        }
    }

    return 0;
}