#include class Node { public: int data; Node* next; Node(int data) { this->data = data; this->next = nullptr; } }; class Solution { private: Node* head; public: Solution() { head = nullptr; } // Insert at the end (O(n)) void insertAtEnd(int data) { Node* newNode = new Node(data); if (head == nullptr) { head = newNode; return; } Node* current = head; while (current->next != nullptr) { current = current->next; } current->next = newNode; } // Insert at the start (O(1)) void insertAtStart(int data) { Node* newNode = new Node(data); newNode->next = head; head = newNode; } // Search for an element (O(n)) bool search(int target) { Node* current = head; int index = 0; while (current != nullptr) { if (current->data == target) { std::cout << "Element " << target << " found at index " << index << std::endl; return true; } current = current->next; index++; } std::cout << "Element " << target << " not found." << std::endl; return false; } // Delete from the start (O(1)) void deleteFromStart() { if (head != nullptr) { Node* temp = head; head = head->next; delete temp; } } // Delete from the end (O(n)) void deleteFromEnd() { if (head == nullptr) return; // List is empty if (head->next == nullptr) { // Only one element in the list delete head; head = nullptr; return; } Node* current = head; while (current->next->next != nullptr) { current = current->next; } delete current->next; // Remove the last node current->next = nullptr; } // Print the linked list (O(n)) void printList() { Node* current = head; while (current != nullptr) { std::cout << current->data << " -> "; current = current->next; } std::cout << "null" << std::endl; } }; int main() { Solution list; // Insert at the end list.insertAtEnd(10); list.insertAtEnd(20); list.insertAtEnd(30); std::cout << "List after inserting elements at the end:" << std::endl; list.printList(); // Insert at the start list.insertAtStart(5); std::cout << "List after inserting element at the start:" << std::endl; list.printList(); // Search for an element list.search(20); // Delete from the start list.deleteFromStart(); std::cout << "List after deleting element from the start:" << std::endl; list.printList(); // Delete from the end list.deleteFromEnd(); std::cout << "List after deleting element from the end:" << std::endl; list.printList(); return 0; }