# Singly Linked List Implementation in C++: Comprehensive Guide ## Introduction Linked lists are fundamental dynamic data structures that store elements in non-contiguous memory locations. Unlike arrays, linked lists provide efficient insertions/deletions without reallocation. This guide implements a complete singly linked list with all essential operations. ## Core Structure ```cpp\nstruct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} // Constructor }; Node* head = nullptr; // Global head pointer\n``` ### Key Operations Explained: 1. **Insertion at Head**: O(1) complexity ```cpp\nvoid insertFront(int value) { Node* newNode = new Node(value); newNode->next = head; // Point to current head head = newNode; // Update head }\n``` 2. **Insertion at Tail**: O(n) traversal ```cpp\nvoid insertEnd(int value) { Node* newNode = new Node(value); if (!head) { head = newNode; return; } Node* current = head; while (current->next) { current = current->next; } current->next = newNode; // Append to end }\n``` 3. **Deletion by Value**: Handles edge cases ```cpp\nvoid deleteNode(int value) { if (!head) return; // Special case: head deletion if (head->data == value) { Node* temp = head; head = head->next; delete temp; return; } Node* current = head; while (current->next && current->next->data != value) { current = current->next; } if (current->next) { Node* temp = current->next; current->next = temp->next; delete temp; // Free memory } }\n``` ### Advanced Operation: Value Partitioning ```cpp\nvoid partition(int x) { Node lessDummy(0), greaterDummy(0); // Dummy nodes Node *less = &lessDummy, *greater = &greaterDummy; while (head) { if (head->data < x) { less->next = head; less = less->next; } else { greater->next = head; greater = greater->next; } head = head->next; } // Connect partitions greater->next = nullptr; less->next = greaterDummy.next; head = lessDummy.next; // Update head }\n``` ### Time Complexity Analysis | Operation | Complexity | Description | |-----------|------------|-------------| | Insert Front | O(1) | Constant time prepend | | Insert End | O(n) | Traverse entire list | | Delete | O(n) | Worst-case traversal | | Search | O(n) | Linear search | ## Applications - Dynamic memory allocation - Undo/Redo functionality - Hash table collision handling - Polynomial representation ## Best Practices 1. Always initialize pointers to `nullptr` 2. Check for empty lists in operations 3. Use constructor for node initialization 4. Prevent memory leaks with proper `delete` 5. Handle head pointer updates carefully