assignment_06.cpp (5244B)
1 /* Implement Circular Linked List. Include functions for insertion, deletion and search of a number, reverse the list. */ 2 3 #include <iostream> 4 using namespace std; 5 6 struct node { 7 int data; 8 node *next = nullptr; 9 }; 10 11 class CircularLinkedList { 12 private: 13 node *head = nullptr; 14 15 public: 16 void insertAtBegin(int val) { 17 node *newNode = new node{val}; 18 if (head == nullptr) { head = newNode; newNode->next = head; return; } 19 node *temp = head; 20 while (temp->next != head) temp = temp->next; 21 newNode->next = head; 22 temp->next = newNode; 23 head = newNode; 24 } 25 26 void insertAtEnd(int val) { 27 node *newNode = new node{val}; 28 if (head == nullptr) { head = newNode; newNode->next = head; return; } 29 node *temp = head; 30 while (temp->next != head) temp = temp->next; 31 temp->next = newNode; 32 newNode->next = head; 33 } 34 35 void insertAtPos(int pos, int val) { 36 if (pos < 1) { cout << "Invalid Position!\n"; return; } 37 if (pos == 1) { insertAtBegin(val); return; } 38 if (head == nullptr) { cout << "Out of range!\n"; return; } 39 node *temp = head; 40 for (int i = 1; i < pos - 1; i++) { 41 temp = temp->next; 42 if (temp == head) { cout << "Out of range!\n"; return; } 43 } 44 node *newNode = new node{val}; 45 newNode->next = temp->next; 46 temp->next = newNode; 47 } 48 49 void deleteAtBegin() { 50 if (head == nullptr) { cout << "List is empty!\n"; return; } 51 if (head->next == head) { delete head; head = nullptr; return; } 52 node *temp = head, *last = head; 53 while (last->next != head) last = last->next; 54 head = head->next; 55 last->next = head; 56 delete temp; 57 } 58 59 void deleteAtEnd() { 60 if (head == nullptr) { cout << "List is empty!\n"; return; } 61 if (head->next == head) { delete head; head = nullptr; return; } 62 node *temp = head; 63 while (temp->next->next != head) temp = temp->next; 64 node *delNode = temp->next; 65 temp->next = head; 66 delete delNode; 67 } 68 69 void deleteAtPos(int pos) { 70 if (head == nullptr || pos < 1) { cout << "Unable to process!\n"; return; } 71 if (pos == 1) { deleteAtBegin(); return; } 72 node *temp = head; 73 for (int i = 1; i < pos - 1; i++) { 74 temp = temp->next; 75 if (temp == head) { cout << "Out of range!\n"; return; } 76 } 77 if (temp->next == head) { cout << "Out of range!\n"; return; } 78 node *delNode = temp->next; 79 temp->next = delNode->next; 80 delete delNode; 81 } 82 83 int search(int key) { 84 if (head == nullptr) return -1; 85 node *temp = head; 86 int pos = 1; 87 do { 88 if (temp->data == key) return pos; 89 temp = temp->next; 90 pos++; 91 } while (temp != head); 92 return -1; 93 } 94 95 void reverse() { 96 if (head == nullptr || head->next == head) return; 97 node *prev = nullptr, *curr = head, *nxt = nullptr, *oldHead = head; 98 do { 99 nxt = curr->next; 100 curr->next = prev; 101 prev = curr; 102 curr = nxt; 103 } while (curr != head); 104 oldHead->next = prev; 105 head = prev; 106 } 107 108 void display() { 109 if (head == nullptr) { cout << "List is empty!\n"; return; } 110 node *temp = head; 111 cout << "List: "; 112 do { cout << temp->data << " -> "; temp = temp->next; } while (temp != head); 113 cout << "(head)\n"; 114 } 115 116 void printMenu() { 117 cout << "1.insertAtBegin 2.insertAtEnd 3.insertAtPos 4.deleteAtBegin 5.deleteAtEnd \n" 118 << "6.deleteAtPos 7.search 8.reverse 0.Display -1.Exit\n"; 119 } 120 121 ~CircularLinkedList() { 122 if (head == nullptr) return; 123 node *temp = head->next; 124 while (temp != head) { node *next = temp->next; delete temp; temp = next; } 125 delete head; 126 } 127 }; 128 129 int main() { 130 CircularLinkedList list; 131 int choice, val, pos; 132 133 while (true) { 134 list.printMenu(); 135 cout << "Enter your choice: "; 136 cin >> choice; 137 138 switch (choice) { 139 case 1: cout << "Enter value: "; cin >> val; list.insertAtBegin(val); break; 140 case 2: cout << "Enter value: "; cin >> val; list.insertAtEnd(val); break; 141 case 3: 142 cout << "Enter position: "; cin >> pos; 143 cout << "Enter value: "; cin >> val; 144 list.insertAtPos(pos, val); 145 break; 146 case 4: list.deleteAtBegin(); break; 147 case 5: list.deleteAtEnd(); break; 148 case 6: cout << "Enter position: "; cin >> pos; list.deleteAtPos(pos); break; 149 case 7: { 150 cout << "Enter value to search: "; cin >> val; 151 int res = list.search(val); 152 if (res != -1) cout << "Found at position " << res << ".\n"; 153 else cout << "Not found.\n"; 154 break; 155 } 156 case 8: list.reverse(); break; 157 case 0: list.display(); break; 158 case -1: cout << "Exiting...\n"; return 0; 159 default: cout << "Wrong choice. Try again.\n"; 160 } 161 } 162 }