# Doubly Linked List Implementation in C++: Bidirectional Mastery ## Introduction Doubly linked lists extend singly linked lists by adding previous pointers, enabling bidirectional traversal. This implementation covers all fundamental operations with O(1) head/tail access. ## Core Structure ```cpp\nstruct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; Node* head = nullptr; Node* tail = nullptr; // Maintain tail pointer\n``` ### Key Operations: 1. **Insertion at End**: O(1) with tail pointer ```cpp\nvoid insertEnd(int value) { Node* newNode = new Node(value); if (!tail) { // Empty list head = tail = newNode; return; } tail->next = newNode; newNode->prev = tail; // Set backward pointer tail = newNode; // Update tail }\n``` 2. **Bidirectional Traversal** ```cpp\nvoid printForward() { Node* current = head; while (current) { cout << current->data << " "; current = current->next; } } void printBackward() { Node* current = tail; // Start from tail while (current) { cout << current->data << " "; current = current->prev; // Move backwards } }\n``` 3. **Delete by Value**: Handles edge cases ```cpp\nvoid deleteNode(int value) { if (!head) return; Node* current = head; while (current && current->data != value) { current = current->next; } if (!current) return; // Not found if (current == head) head = head->next; if (current == tail) tail = tail->prev; // Update neighbor pointers if (current->prev) current->prev->next = current->next; if (current->next) current->next->prev = current->prev; delete current; // Free memory }\n``` ### Advantages Over Singly Linked Lists 1. Reverse traversal capability 2. O(1) deletions at head/tail 3. Simplified node removal 4. Efficient access to predecessors ### Complexity Analysis | Operation | Complexity | |-----------|------------| | Insert Head/Tail | O(1) | | Delete Head/Tail | O(1) | | Random Access | O(n) | | Search | O(n) | ## Applications - Browser history navigation - Music player track lists - Undo/Redo functionality - Cache implementations