apc_003.cpp (5973B)
1 /* Doubly linked list using template */ 2 3 #include <iostream> 4 using namespace std; 5 6 // Node class 7 template <class T> 8 class Node 9 { 10 public: 11 T data; 12 Node<T>* prev; 13 Node<T>* next; 14 15 // Constructor 16 Node(T value) 17 { 18 this->data = value; 19 this->prev = NULL; 20 this->next = NULL; 21 } 22 }; 23 24 25 // Doubly Linked List class 26 template <class T> 27 class DoublyLinkedList 28 { 29 private: 30 Node<T>* head; 31 32 public: 33 34 // Default Constructor 35 DoublyLinkedList() 36 { 37 head = NULL; 38 } 39 40 41 // Copy Constructor 42 DoublyLinkedList(const DoublyLinkedList<T>& other) 43 { 44 head = NULL; 45 46 Node<T>* temp = other.head; 47 48 while (temp != NULL) 49 { 50 insertAtEnd(temp->data); 51 temp = temp->next; 52 } 53 } 54 55 56 // Insert at beginning 57 void insertAtBeginning(T value) 58 { 59 Node<T>* newNode = new Node<T>(value); 60 61 if (head == NULL) 62 { 63 head = newNode; 64 } 65 else 66 { 67 newNode->next = head; 68 head->prev = newNode; 69 head = newNode; 70 } 71 } 72 73 74 // Insert at end 75 void insertAtEnd(T value) 76 { 77 Node<T>* newNode = new Node<T>(value); 78 79 if (head == NULL) 80 { 81 head = newNode; 82 return; 83 } 84 85 Node<T>* temp = head; 86 87 while (temp->next != NULL) 88 { 89 temp = temp->next; 90 } 91 92 temp->next = newNode; 93 newNode->prev = temp; 94 } 95 96 97 // Delete a value 98 void deleteNode(T value) 99 { 100 if (head == NULL) 101 { 102 cout << "List is empty.\n"; 103 return; 104 } 105 106 Node<T>* temp = head; 107 108 // Search for the value 109 while (temp != NULL && temp->data != value) 110 { 111 temp = temp->next; 112 } 113 114 // Value not found 115 if (temp == NULL) 116 { 117 cout << "Value not found.\n"; 118 return; 119 } 120 121 // Delete first node 122 if (temp == head) 123 { 124 head = head->next; 125 126 if (head != NULL) 127 head->prev = NULL; 128 } 129 else 130 { 131 temp->prev->next = temp->next; 132 133 if (temp->next != NULL) 134 temp->next->prev = temp->prev; 135 } 136 137 delete temp; 138 139 cout << "Value deleted successfully.\n"; 140 } 141 142 143 // Search 144 void search(T value) 145 { 146 Node<T>* temp = head; 147 int position = 1; 148 149 while (temp != NULL) 150 { 151 if (temp->data == value) 152 { 153 cout << "Value found at position " 154 << position << ".\n"; 155 return; 156 } 157 158 temp = temp->next; 159 position++; 160 } 161 162 cout << "Value not found.\n"; 163 } 164 165 166 // Display forward 167 void display() 168 { 169 if (head == NULL) 170 { 171 cout << "List is empty.\n"; 172 return; 173 } 174 175 Node<T>* temp = head; 176 177 cout << "List: "; 178 179 while (temp != NULL) 180 { 181 cout << temp->data << " <-> "; 182 temp = temp->next; 183 } 184 185 cout << "NULL\n"; 186 } 187 188 189 // Display backward 190 void displayReverse() 191 { 192 if (head == NULL) 193 { 194 cout << "List is empty.\n"; 195 return; 196 } 197 198 Node<T>* temp = head; 199 200 // Go to last node 201 while (temp->next != NULL) 202 { 203 temp = temp->next; 204 } 205 206 cout << "Reverse: "; 207 208 while (temp != NULL) 209 { 210 cout << temp->data << " <-> "; 211 temp = temp->prev; 212 } 213 214 cout << "NULL\n"; 215 } 216 217 218 // Reverse the linked list 219 void reverseList() 220 { 221 Node<T>* current = head; 222 Node<T>* temp = NULL; 223 224 while (current != NULL) 225 { 226 // Swap next and prev 227 temp = current->prev; 228 current->prev = current->next; 229 current->next = temp; 230 231 // Move to next node 232 current = current->prev; 233 } 234 235 if (temp != NULL) 236 { 237 head = temp->prev; 238 } 239 240 cout << "List reversed successfully.\n"; 241 } 242 }; 243 244 245 // Main function 246 int main() 247 { 248 DoublyLinkedList<int> list; 249 250 int choice; 251 int value; 252 253 do 254 { 255 cout << "\n========== DOUBLY LINKED LIST ==========\n"; 256 cout << "1. Insert at Beginning\n"; 257 cout << "2. Insert at End\n"; 258 cout << "3. Delete\n"; 259 cout << "4. Search\n"; 260 cout << "5. Display\n"; 261 cout << "6. Display Reverse\n"; 262 cout << "7. Reverse List\n"; 263 cout << "8. Copy List\n"; 264 cout << "9. Exit\n"; 265 266 cout << "Enter your choice: "; 267 cin >> choice; 268 269 switch (choice) 270 { 271 case 1: 272 cout << "Enter value: "; 273 cin >> value; 274 list.insertAtBeginning(value); 275 break; 276 277 case 2: 278 cout << "Enter value: "; 279 cin >> value; 280 list.insertAtEnd(value); 281 break; 282 283 case 3: 284 cout << "Enter value to delete: "; 285 cin >> value; 286 list.deleteNode(value); 287 break; 288 289 case 4: 290 cout << "Enter value to search: "; 291 cin >> value; 292 list.search(value); 293 break; 294 295 case 5: 296 list.display(); 297 break; 298 299 case 6: 300 list.displayReverse(); 301 break; 302 303 case 7: 304 list.reverseList(); 305 break; 306 307 case 8: 308 { 309 // Copy constructor is called 310 DoublyLinkedList<int> copy(list); 311 312 cout << "Copied List: "; 313 copy.display(); 314 315 break; 316 } 317 318 case 9: 319 cout << "Program terminated.\n"; 320 break; 321 322 default: 323 cout << "Invalid choice!\n"; 324 } 325 326 } while (choice != 9); 327 328 return 0; 329 }