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